Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer at Google:
Dec 21, 2011
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (11)
1 of 1 people found this helpful
Jan 7, 2012
Since you know exactly where each entry needs to go, you will be able to sort the array in O(n) using k extra slots (since the array is only of size n - k) so you can do this in O(n) with O(k) space.
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
Jan 7, 2012
using hash table. it is 2*n loop
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
Jan 8, 2012
hash table is better
Helpful Answer?
Yes |
No
Inappropriate?
1 of 2 people found this helpful
Jan 15, 2012
sum all elements S1 and sum all squares of elements S2, then solve
x+y = (1+...+100)-S1
x^2+y^2 = (1^2+2^2+...+100^2)-S2
x+y = (1+...+100)-S1
x^2+y^2 = (1^2+2^2+...+100^2)-S2
Helpful Answer?
Yes |
No
Inappropriate?
0 of 2 people found this helpful
Feb 2, 2012
@vanship for the second squered sums you can't apply to each element, but the entire line:
(x + y ) ^ 2 = ( 1 + 2 .... + 100) ^2
Which essentially is same as original sum squared..
You need to copy array to a new 100 size array, where position N is number N in the array. Whichever spots are blank are the missing numbers. Loop once to find missing numbers - O(n)
(x + y ) ^ 2 = ( 1 + 2 .... + 100) ^2
Which essentially is same as original sum squared..
You need to copy array to a new 100 size array, where position N is number N in the array. Whichever spots are blank are the missing numbers. Loop once to find missing numbers - O(n)
Helpful Answer?
Yes |
No
Inappropriate?
0 of 1 people found this helpful
Feb 11, 2012
n=100;
(x+y) = (n+1)*n/2 - sum;
then find x from 1 to (x+y)/2;
it becomes question 1.
2O(n)
(x+y) = (n+1)*n/2 - sum;
then find x from 1 to (x+y)/2;
it becomes question 1.
2O(n)
Helpful Answer?
Yes |
No
Inappropriate?
3 of 3 people found this helpful
Feb 22, 2012
If one is missing
we know x = N(N+1)/2 -Sum
If two are missing
xy = N!/P where p is the product of all the numbers in the array.
and
x+y = (N+1)N/2 - S
Solve the two equations to get the answer, no need to use squares of numbers. Simple!!!
we know x = N(N+1)/2 -Sum
If two are missing
xy = N!/P where p is the product of all the numbers in the array.
and
x+y = (N+1)N/2 - S
Solve the two equations to get the answer, no need to use squares of numbers. Simple!!!
Helpful Answer?
Yes |
No
Inappropriate?
Apr 20, 2012
The best solution is definitely the one by Srikanth since in O(n) you can compute both s and p (sum and product of the numbers) and compute:
z = x+y = n*(n+1)/2-s
w = x*y = n!/p
then solve by using:
x = ( z +/- sqrt(z*z-4*w) )/2
Note that the above equation returns both x and y (substitute z and w to believe it)!
z = x+y = n*(n+1)/2-s
w = x*y = n!/p
then solve by using:
x = ( z +/- sqrt(z*z-4*w) )/2
Note that the above equation returns both x and y (substitute z and w to believe it)!
Helpful Answer?
Yes |
No
Inappropriate?
Apr 25, 2012
Almost verbatim from the previous two comments:
def find_missing_numbers(arr):
N = len(arr)+2
z = N * (N+1) / 2 - sum(arr) # x+y
w = math.factorial(N) / reduce(operator.mul, arr, 1) # x*y
return set([
int(( z + math.sqrt(z*z-4*w) )/2),
int(( z - math.sqrt(z*z-4*w) )/2),
])
Left the sum/prod/factorial in 3 separate loops for readability, but could be combined to one.
def find_missing_numbers(arr):
N = len(arr)+2
z = N * (N+1) / 2 - sum(arr) # x+y
w = math.factorial(N) / reduce(operator.mul, arr, 1) # x*y
return set([
int(( z + math.sqrt(z*z-4*w) )/2),
int(( z - math.sqrt(z*z-4*w) )/2),
])
Left the sum/prod/factorial in 3 separate loops for readability, but could be combined to one.
Helpful Answer?
Yes |
No
Inappropriate?
1 of 1 people found this helpful
Apr 25, 2012
I was confused about how you got the answer, but I figured it out, so let me explain it for others...
z = x+y = n*(n+1)/2-s
w = x*y = n!/p
We could simplify as something like:
z = x + y = 97
w = x * y = 1482
We eliminate one variable to make it solvable:
y = 97-x
So:
x * (97-x) = 1482
97x - x^2 = 1482
x^2 - 97x + 1482 = 0
Now just substitute the variables in place of the integers:
x^2 - zx + w = 0
And use the quadratic formula to solve for x:
(z +- sqrt(z**2 - 4*1*w)) / (2 * 1)
z = x+y = n*(n+1)/2-s
w = x*y = n!/p
We could simplify as something like:
z = x + y = 97
w = x * y = 1482
We eliminate one variable to make it solvable:
y = 97-x
So:
x * (97-x) = 1482
97x - x^2 = 1482
x^2 - 97x + 1482 = 0
Now just substitute the variables in place of the integers:
x^2 - zx + w = 0
And use the quadratic formula to solve for x:
(z +- sqrt(z**2 - 4*1*w)) / (2 * 1)
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Interview Questions, Google Interview
0 of 2 people found this helpful
by Anonymous: