Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand the question. Could you detail it more?

- Anonymous November 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Are u sure this is a question of phone interview?
I even can't understand it by reading. how can you understand it in cell phone?

Need more details about the problem.

- Anonymous November 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The Given part of the problem is understandable.
But the problem part (devise a small memory streaming algo) is not very clear. Is a data structure expected in answer which will help in calculating the |A| value when the input is a running stream?

- Learner November 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What is |A|? Is it the no of elements in the set A ?

If so, then this is fairly simple problem. I'm sure m missing something.

- P November 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It an be proven that you need to keep track of the value of x[j] for every j and update it as you see new values in the stream.
So, you MUST use a space of n*log m where n is the number of different elements and m is the length of the string.

- Kian November 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anybody explain the question if you catch it?
thx.

- Anonymous November 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nonsense ...

- hsong November 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Nonsense ...

- hsong November 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- DeY November 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

- zhenli3 December 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zhenli3
can u pls elaborate how u r computing Q ..
I am not able to understand it..
thank

- mgr December 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@zhenli3
can u pls elaborate how u r computing Q ..
I am not able to understand it..
thank

- mgr December 27, 2011 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More