Google Interview Report
- 0of 0 votes
AnswersAlgorithm to output for a length m of a number stream, the value of the element j appearing in the stream for which freq[j]>m/2 with space complexity O(1) and time complexity O(m). Dont need to worry about the case when there are no elements with freq > m/2.
- ALgeek November 17, 2011 in India
The question in simpler terms:
In a collection of 'M' elements, some elements are repeated. Find the element which occurred at least M/2 times.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer - 0of 2 votes
AnswersFor a stream of insertions and deletions, recall that x[j] = #insertions - #deletions of element j.
- ALgeek November 17, 2011 in India
Given such a stream satisfying x[j] >= 0 for all elements j, let
A = { j : x[j] > 0 }
Determining whether A is empty is easy: just check if the sum of all x[j]'s equals 0 (which is easily doable in a stream).
Problem: devise a small memory streaming algorithm to determine if |A| = 1.
Extensions: What about higher sizes of A? What if the promise is not satisfied and we define A to be the set of j's with x[j] not equal to 0.| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer