Nervewreck
February 15th, 2006
Antabuse Online Buy Erythromycin Zyban Online Buy Soma Prednisone Online Buy Lotrisone Lipitor Online Buy Lipitor Erythromycin Online Buy CoumadinWhen you're [interviewing->googles-calling] you get asked tricky questions. When you're asked tricky questions you get nervous. When you're nervous you get stupid. When you're stupid it is exceptionally hard to answer tricky questions. When you can't answer tricky questions you don't do well on interviews. Bad circle.
After two and a half hour of interviewing I'm a nervewreck. Among other questions, I was asked how to compute median values in a distributed fashion, do binary search on cyclically sorted arrays, and to design a virtual piano. Answering all those questions while mentally being on the level of a three-year-old (which is what you get during a phone interview) is hard. *sigh*
Anyway, I'll hear from them in about a week. If I'm lucky, they'll give me an offer to move down to California and become a [noogler->http://www.google.com/search?q=What%27s+a+Noogler%3F], if not, well, then I don't.
Entry Filed under: Employment
10 Comments Add your own
1. Johan | February 15th, 2006 at 23:42
It seems that the distributed median question is one of Google’s standard questions. I found at least one other person who has been asked that question when I googled for “google interview questions” or something similar.
2. Henrik | February 16th, 2006 at 00:26
Yep, I noticed that as well. Too bad I never really spent any time thinking about that problem.
3. ano | February 17th, 2006 at 23:10
What does it mean for an array to be cyclically sorted?
4. Henrik | February 18th, 2006 at 00:59
Perhaps it’s not an established term, but what I ment was an array which is sorted and then shifted an arbitrary number of positions. Example: 12345 shifted two steps to the right becomes 45123.
5. ano | February 20th, 2006 at 12:14
binary search on cyclically sorted array - I can put the array back into sorted order using some rotations in linear time without extra memory but doing a binary search on a cyclically sorted array seems hard.
Let me take a shot at this. The only thing I could think of is .. let assume that we’re looking for 2. We first compare 2 with the first element in the array and last element in the array, since 2 is less than 3, we know it’s in the left of 3. We then do a binary search from the front to find an element that is less 2 (less_than_two_index). Not the normal binary search of course. If the element we’re looking at is larger than 3, we keep do the binary search on the right hand side ( I can see a flaw with this. What if we land on 3). But if we somehow can find this less_than_two_index, we just perform a normal binary search from there to the end of the array.
We can apply this method the other way around. Maybe!
Henrik, what’s your solution?
6. ano | February 20th, 2006 at 12:22
ok! I can solve cyclically sorted array.
let say that we search for 2. Again, we search starting from the back. This should be a normal binary search but what would happen if we land in 5. Everytime we do a comparison, we also comapre the current element to the last element which is 3. If it’s greater than 3, we know that the number we’re looking for is on the right. This would solve it.
7. ano | February 20th, 2006 at 12:25
median values in a distributed fashion - median is the number in the middle of the array if the array is sorted. Distributed fashion? Use mergesort and divide the work among computers?
8. Henrik | February 20th, 2006 at 13:50
About the binary search, restoring the original sorted order is not an option, since that would take O(n) time, whereas the binary search is supposed to only take O(log n).
Your second solution seems to be on track, although you have to look at both the first and the last element as it can be smaller than the first, or larger than the last.
About the median, yes, sort the numbers on each computer and use one computer to merge the numbers is one solution. Also, in some cases we can do better by not returning each number individually from every computer, but instead say e.g. “five ones, three twos, nine threes and four fours” which would require 4 numbers to be transfered instead of 21.
9. ano | February 20th, 2006 at 21:44
What if you have “twenty one 1 and three 2″. You can’t just return 2 numbers 1 and 2. Was this a phone or onsite interview? I hope you get the job!
10. Henrik | February 21st, 2006 at 10:36
I’m not sure what you mean, but if you have “21 times number 1, 3 times number 2″, you could return only “21 1 3 2″, or even just “21 3″ if you assume that there are no gaps in the sequence.
It was a phone interview. Thanks!
Leave a Comment
You must be logged in to post a comment.
Trackback this post | Subscribe to the comments via RSS Feed