## 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

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

Correct, edited again, sorry. I think "trivial solution" should be pretty obvious.

- Anonymous January 27, 2015