I interviewed for a Google internship in 2005 and it started with a phone screen. The first question was something simple that I don’t remember anymore. The second question was more interesting: say you have a huge file on disk, too big to fit in memory, and it has a list of N 2d (x,y) points. How can you find the K points that are closest to the origin?
The answer was to use a max heap and keep inserting each point and when you have more than K points in the heap, pop the biggest point so that you’re always maintaining the K smallest. That gets you to O(N log K). I remember that after I solved it, the guy quizzed me to check that I knew you could skip the square root in the distance to origin calculation as an optimization.
Read other answers by Adam D'Angelo on Quora:
- What are the best arguments to use on a candidate who is afraid to leave Google, even when all evidence suggests it will be a good career move for her?
- What are some instances when Google has violated its "Don't be evil" motto?
- How many people work on each of Google's various products?
from Quora http://ift.tt/2hbrT6C
No comments:
Post a Comment