Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
as far as I understood is as:
We have an array ..for every index j the element calculates that how many times j is inserted and how many times it is deleted ....find the difference and put that at index j so in this way we can have the array for example
x:(2,4,0,6,0,0,2)
meaning x[0]=2=#of times 0 is inserted-#of times 0 is deleted
x[1]=4=#of times 1 is inserted-#of times 1 is deleted
similarly for all
Now given A is those entries's index which are > 0
so A:(0,1,3,6)
so A will be empty is sum of all elements of x will be 0 which is in question given...
so the problem..
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.
No, I think in the problem, we are given a stream of insertions and deletions instead of given x directly (x only exists in logic)
e.g. steam = {insert 5, insert 10, delete 5, insert 3, delete 3, ...}
let's denote the stream as S. For simplicity, we can assume that all the elements are positive integers.
So, S={+5, +10, -5, +3, -3, ...}.
1) To decide if |A|=0
simply count
P = #total insertion - #total deletion = \Sigma_{i from 1 to |S|} sign(S[i])
if P=0, then |A|=0
if P>0, then |A|>0
(P<0 couldn't happen)
In other words, |A|=0 iff P=0
2) To decide if |A|=1
First count P as in 1).
If P=0, we know A=0; otherwise, count
Q = \Sigma_{i from 1 to |S|} S[i]
Then check for Q/P,
if x[Q/P] = #(insertion of Q/P) - #(deletion Q/P) = P holds
if yes, then |A|=1
otherwise, |A|>1
=================
Examples:
S={1,2,3,-3,-1,-2} => P=0 => |A|=0
S={1,2,3,-3} => P=2, Q=3 => x[3/2] != P => |A|>1
S={1,2,3,-1,-2,3} => P=2, Q=6 => x[6/2] == P => |A|=1
=================
Both algorithms runs in O(N) time (N is the length of the stream), and memory cost is only O(1)
I don't understand the question. Could you detail it more?
- Anonymous November 17, 2011