Google Interview Report
- 1of 1 vote
AnswersWrite a class that receives in the constructor a vector of strings representing a browser history (URLs), and a method for "auto-complete":
- Anonymous January 27, 2015 in Israel
The method that receives a string representing a partial URL typed by the user and returns a vector of all possible completions of this partial URL (prefix).| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersWrite a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).
- Anonymous January 27, 2015 in Israel
The stream ends with the special pair {0,0}.
The function should return one the unique ids at random, with probability proportional to its weight (compared to the total weights sum when stream has ended).
Stream size and weights sum are unknown in advance, and you are allowed O(1) memory consumption.
Example: If this was the stream: {1,2},{2,2},{3,4},{4,10}, then id 2 would be returned with probability 1/9.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm