Anonymous
BAN USER- 1of 1 vote
AnswersWrite a function that receives a stream of pairs: id (some unique integer) + weight (positive real number).
- Anonymous 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 - 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 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 - 3of 3 votes
AnswersYou are given an array of distinct numbers. You need to return an index to a "local minimum" element, which is defined as an element that is smaller than both its adjacent elements. In the case of the array edges, the condition is reduced to one adjacent element.
- Anonymous in Israel
Reach a solution with better time complexity than the trivial solution of O(n).
If there are multiple "local minimums", returning any one of them is fine.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 0 votes
AnswersYou are given a positive integer number N. Return the minimum number K, such that N can be represented as K integer squares.
- Anonymous in Israel
Examples:
9 --> 1 (9 = 3^2)
8 --> 2 (8 = 4^2 + 4^2)
15 --> 4 (15 = 3^2 + 2^2 + 1^2 + 1^2)
First reach a solution without any assumptions, then you can improve it using this mathematical lemma: For any positive integer N, there is at least one representation of N as 4 or less squares.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm - 1of 1 vote
AnswersYou are given a double linked list and an array of pointers to elements in this list (no assumptions can be made on the array - number of pointers, order and duplicates allowed).
- Anonymous in Israel
Return the number of sequences of elements (groups of consecutive elements), pointed by the array.
For example, if this is the array (number relates to index in the list, not the actual pointer value): 9,1,3,7,8,5,2.
Then output is 3, representing these sequences: [1,2,3], [5], [7,8,9]| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Data Structures
Correct, edited again, sorry. I think "trivial solution" should be pretty obvious.
- Anonymous January 27, 2015