Google 2 phone interviews exposed + 求祝福# JobHunting - 待字闺中
P*i
1 楼
Phone 1:
:
What is “static” variable?
How can many instance share a resource
What is deadlock, how to prevent it?
Compare whether two strings s1, s2 are equal, inside a huge set of string.
Normal way is to compare each character one by one, but it is O( n ) time
complexity. What type of short circuit can u think?
One short circuit is to use the length, since s1.len <> s2. len , then
return false. Anything else you can think of in the similar way?
My answers:
Hashtable? No, need extra space
Binary search? No, worst case is O(n)
1) # of unique chars
2) Bit vector for each
I did not know KMP and Robin Karp at that time, i guess it is the desirable
solution for the interview :(
Given a perfect random generator Random(n) which can generate number between
[0,1], write a program to generate a random pair of (x, y) within a circle
of radius 1, and with (0,0) center with uniform distribution inside the
circle. What is the expect probability of values fall into the circle?
What is “static” variable?
How can many instance share a resource
What is deadlock, how to prevent it?
Compare whether two strings s1, s2 are equal, inside a huge set of string.
Normal way is to compare each character one by one, but it is O( n ) time
complexity. What type of short circuit can u think?
One short circuit is to use the length, since s1.len <> s2. len , then
return false. Anything else you can think of in the similar way?
My answers:
Hashtable? No, need extra space
Binary search? No, worst case is O(n)
1) # of unique chars
2) Bit vector for each
I did not know KMP and Robin Karp at that time, i guess it is the desirable
solution for the interview :(
Given a perfect random generator Random(n) which can generate number between
[0,1], write a program to generate a random pair of (x, y) within a circle
of radius 1, and with (0,0) center with uniform distribution inside the
circle. What is the expect probability of values fall into the circle?
