wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Compiled Google Interview Questions
        
(Message started by: Ivan on Nov 17^th, 2006, 5:52pm)

Title: Compiled Google Interview Questions
Post by Ivan on Nov 17^th, 2006, 5:52pm

1. Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.

2. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

3. Given an array,
i) find the longest continuous increasing subsequence.
ii) find the longest increasing subsequence.

4. A building of 100 floors, there is a threshold N s.t. if an egg drops from Nth floor and above it will break. If it's dropped from any floor below, it will not break. Given 2 eggs, find this N, and minimize the number of drops for the worse case.

5. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

6. Write a function to find the middle node of a single link list.

7. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

8. Implement put/get methods of a fixed size cache with LRU replacement algorithm.

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 18^th, 2006, 9:03am

on 11/17/06 at 17:52:20, Ivan wrote:

2. Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.

You can search for "coin change problem" and get lots of material on this.

Quote:

3. Given an array,
i) find the longest continuous increasing subsequence.

O(n) time solution easily possible

Quote:

ii) find the longest increasing subsequence.

Dynamic Programming

Quote:

4. A building of 100 floors, there is a threshold N s.t. if an egg drops from Nth floor and above it will break. If it's dropped from any floor below, it will not break. Given 2 eggs, find this N, and minimize the number of drops for the worse case.

Has been discussed in this forum before. I think the title was "egg dropping". I will see if i can find the link.

[edit]here is the link (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027807348;)[/edit]

Quote:

5. Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?

Dont understand?? Is there any specific hierarchy in the company that we need to adhere to? In which case, are we looking at tree merging?

Quote:

6. Write a function to find the middle node of a single link list.

Move two pointers. One pointer moves forward at every cycle and another moves at only even cycles.

Quote:

7. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

Do any of the pre/in/post order traversal on both the trees simultaneously.

Quote:

8. Implement put/get methods of a fixed size cache with LRU replacement algorithm.

**The following is nothing standard. Its just the way i would write put and get**

Assuming cache line has three fields (id, data, age)

top = 0

put(idt, x)
{
if(top == cachesize) top--
cache[top].id = idt
cache[top].data = x
cache[top].age = 0
top++
}

get(idt)
{
find idt in 0 to top
if idt found at z
cache[z].age++
x = cache[z].data
insertsort(0,z) on age
return x
}

Title: Re: Compiled Google Interview Questions
Post by Ashwin on Nov 18^th, 2006, 5:18pm

Regarding merging of N companies evenly, is the answer = N - 1.

Essentially, you want to merge two companies that have the smallest difference in "size". This means calls for a priority queue using heaps

Q <- N //create the queue using N companies with size as the priority

for i = 1 to n - 1
x = Q.ExtractMin()
y = Q.ExtractMin()
z = Company(x,y)
Q.Insert(z);
end for

return Q.ExtractMin()

Title: Re: Compiled Google Interview Questions
Post by Grimbal on Nov 18^th, 2006, 5:41pm

on 11/18/06 at 09:03:19, TenaliRaman wrote:

Move two pointers. One pointer moves forward at every cycle and another moves at only even cycles.

I thought the same. But it is simpler and just as fast to scan the list once to count the items and a second time to reach the element at (length/2).

Title: Re: Compiled Google Interview Questions
Post by Eigenray on Nov 18^th, 2006, 7:29pm

on 11/18/06 at 17:41:50, Grimbal wrote:

I thought the same. But it is simpler and just as fast to scan the list once to count the items and a second time to reach the element at (length/2).

Yeah but that uses log(n) extra space. Which is really bad for some reason.

Title: Re: Compiled Google Interview Questions
Post by Ashwin on Nov 18^th, 2006, 9:13pm

bool SameTrees(struct node* a, struct node* b)
{
if(a == NULL && b == NULL)
return true;
else if(a != NULL && b != NULL)
{
return ( (a->data == b->data) &&
SameTrees(a->left,b->left) &&
SameTrees(a->right,b->right));
}

return false;
}

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 19^th, 2006, 3:25am

Am i dreaming? What happened to Eigenray's and Grimbal's Post Numbers??

[edit]Forgot to reply:
Yeah, just realised that both the idea have 3n/2 running time. Moreover, we have two pointers here so we are needlessly wasting space. Thats what the point is about i guess.[/edit]

Title: Re: Compiled Google Interview Questions
Post by towr on Nov 19^th, 2006, 7:10am

on 11/19/06 at 03:25:46, TenaliRaman wrote:

Am i dreaming? What happened to Eigenray's and Grimbal's Post Numbers??

They both seem to have two accounts (one with a capital and one without). At least assuming they're not being impersonated.
It had me worried there for a moment too.

Title: Re: Compiled Google Interview Questions
Post by Grimbal on Nov 19^th, 2006, 1:52pm

Aaaah. Now I understand why the forum marked all posts as "unread".
:-[
I thought it was another YaBB glitch.

Title: Re: Compiled Google Interview Questions
Post by Grimbal on Nov 19^th, 2006, 1:53pm

on 11/18/06 at 19:29:05, Eigenray wrote:

Yeah but that uses log(n) extra space. Which is really bad for some reason.

But you save a pointer which is also log(n) storage. ;D

Title: Re: Compiled Google Interview Questions
Post by Eigenray on Nov 19^th, 2006, 2:59pm

on 11/19/06 at 13:53:18, Grimbal wrote:

But you save a pointer which is also log(n) storage. ;D

But, but, then in addition to your 3n/2 pointer advancements, you have 3n/2 counter increments. And those are like log(n) each!

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 19^th, 2006, 7:34pm

on 11/19/06 at 14:59:13, Eigenray wrote:

But, but, then in addition to your 3n/2 pointer advancements, you have 3n/2 counter increments. And those are like log(n) each!

oh never thought of that! That makes the two pointer method the better one.

-- AI

Title: Re: Compiled Google Interview Questions
Post by Grimbal on Nov 20^th, 2006, 1:33am

on 11/19/06 at 14:59:13, Eigenray wrote:

But, but, then in addition to your 3n/2 pointer advancements, you have 3n/2 counter increments. And those are like log(n) each!

I totally agree with you. :)

Title: Re: Compiled Google Interview Questions
Post by VaMpIrE on Nov 24^th, 2006, 8:34pm

For the first one is this possible!!
the Stack works as we know , apart form that, the top element always is the copy of the min element ,

So the algo for PUSH would be
1. If first element , then push(i) , push(i) <-- the copy
2. else min=pop();
push(i)
if(min>i)
push(i)
else
push(min)
For POP:
min=pop()
elem=pop()
push(min)
For MIN :
pop()

NOTE : 'PUSH' is the modified method, 'push' is the usual one .
So except the first element rest of the stack is same. and the first element is the min. so all operations in constant time [comments !!]

Title: Re: Compiled Google Interview Questions
Post by balanagireddy.tcs on Nov 25^th, 2006, 1:43am

can someone explain 3. ii ?

Title: Re: Compiled Google Interview Questions
Post by balanagireddy.tcs on Nov 25^th, 2006, 1:48am

I think for the fifth question.
suppose there are 4 companies.

we can merge them like this

1+2,1+2+3,1+2+3+4
1+2,3+4,1+2+3+4
1+2+3,4,1+2+3+4
1+2+3+4

so there are n ways to merge if permutations are not considered considering 1,2,3...n at a time.

and for each merge there are again n-1 possible

so total possible are

n( (n-1) + (n-2) + ......1)

(n*n*n-1)/2

so there are (n^2(n-1)) / 2

Title: Re: Compiled Google Interview Questions
Post by balanagireddy.tcs on Nov 25^th, 2006, 1:48am

Title: Re: Compiled Google Interview Questions
Post by balanagireddy.tcs on Nov 25^th, 2006, 1:52am

For the sixth question

Suppose if the linked list is using array implementation there is a constant time solution.

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 25^th, 2006, 2:24am

on 11/24/06 at 20:34:24, VaMpIrE wrote:

So the algo for PUSH would be
1. If first element , then push(i) , push(i) <-- the copy
2. else min=pop();
push(i)
if(min>i)
push(i)
else
push(min)
For POP:
min=pop()
elem=pop()
push(min)
For MIN :
pop()

NOTE : 'PUSH' is the modified method, 'push' is the usual one .
So except the first element rest of the stack is same. and the first element is the min. so all operations in constant time [comments !!]

Lets say that the current state of your stack be,

(bottom to top)
[5,2,3,4,1,1 <--(the min at top)]
Now i do a pop on your stack,
By your pop operation, stack will become
[5,2,3,4,1 <--(the min at top)]
Now, i do a min operation, so your stack will give me 1.

Is 1 still the min of the stack?

-- AI

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 25^th, 2006, 2:25am

on 11/25/06 at 01:43:09, balanagireddy.tcs wrote:

can someone explain 3. ii ?

http://en.wikipedia.org/wiki/Longest_increasing_subsequence_problem

-- AI

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 25^th, 2006, 2:28am

on 11/25/06 at 01:52:53, balanagireddy.tcs wrote:

For the sixth question

Suppose if the linked list is using array implementation there is a constant time solution.

It wont be much of a puzzle then, now would it? ;D

-- AI

Title: Re: Compiled Google Interview Questions
Post by VaMpIrE on Nov 26^th, 2006, 10:36am

Redefined POP :
So as pointed out one needs to remember the min_elem seen at every stage of the stack,
so one can keep a bit in the stack such that
boolean min = false ==> the element is the stack value
= true ==> its the min stored by the us
so the algo becomes
PUSH :
if the top>elem then push elem, push elem_set bit
else pop min(top is always the min), push elem, push min
POP :
min = pop()
elem = pop()
if(top has bit not set)
push(min) // min is still there ...
MIN:
min= pop()

This is better than keeping a seperate array. Same for worst case but good for best case
for the given eg:
the state would be [ a * indicates bit SET]
5 5* 4 4* 3 3* 2 2* 1 1*
pop will result in
5 5* 4 4* 3 3* 2 2*
I guess its ok now.

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 26^th, 2006, 11:21am

on 11/26/06 at 10:36:11, VaMpIrE wrote:

Yeah, you have got quite the right idea. However, a much more simpler implementation of this strategy is,

Code:

push(x)
{
if stack.empty()
{
stack.push(x);
stack.push(x);
}
else
{
if x > stack.top()
{
min = stack.top()
stack.push(x)
stack.push(min)
}
else
{
stack.push(x)
stack.push(x)
}
}
}

pop()
{
stack.pop()
return stack.pop()
}

min()
{
return stack.top()
}

Now, only thing is that we have used space twice that of the elements. Cant really much help this, but there is some amount of optimizations that can be done in terms of repeat mins.

For example,
Suppose the elements being pushed are 5,3,4,7,1. Then our stack will have,
[5,5,3,3,4,3,7,3,1,1]

We see that the three's are repeated quite a bit, we can avoid that as well. However, now that i think about it, are you doing that using your boolean bit?

-- AI

Title: Re: Compiled Google Interview Questions
Post by Ivan on Nov 26^th, 2006, 12:00pm

I think that this is just like the number of binary trees of n nodes. Thus I am guessing the answer is Catalan number.

on 11/25/06 at 01:48:22, balanagireddy.tcs wrote:

Title: Re: Compiled Google Interview Questions
Post by VaMpIrE on Nov 26^th, 2006, 12:42pm

yeah boolean bit and for this input my stack would look like
[5,5*,3,4,7,3*,1,1*] where * is the bit set.

Title: Re: Compiled Google Interview Questions
Post by VaMpIrE on Nov 26^th, 2006, 1:59pm

Another easier way
Insight : compress the information using diff

PUSH :
if stack empty
push(elem)
push(elem)
else
min = pop()
push(elem-min)
push(min)

POP :
min = pop()
elem = pop()
if elem is -ve
push(min-elem) // earlier min
return min
else
push(min)
return elem + min

MIN :
min = pop()
push(min)
return min

O(n+1) space and constant operations for pop push min !!

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 26^th, 2006, 8:23pm

on 11/26/06 at 12:42:53, VaMpIrE wrote:

yeah boolean bit and for this input my stack would look like
[5,5*,3,4,7,3*,1,1*] where * is the bit set.

Yeah thats what i thought. I did the same but used another stack to store the mins and levels.

-- AI

Title: Re: Compiled Google Interview Questions
Post by Ivan on Nov 26^th, 2006, 8:25pm

on 11/26/06 at 20:23:00, TenaliRaman wrote:

Yeah thats what i thought. I did the same but used another stack to store the mins and levels.

-- AI

Yep, that is the idea. Nice job.

Title: Re: Compiled Google Interview Questions
Post by Ivan on Nov 26^th, 2006, 8:26pm

on 11/26/06 at 12:00:53, Ivan wrote:

I think that this is just like the number of binary trees of n nodes. Thus I am guessing the answer is Catalan number.

Any comments on this one?

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 26^th, 2006, 8:43pm

on 11/26/06 at 13:59:00, VaMpIrE wrote:

Another easier way
Insight : compress the information using diff
<snip>
O(n+1) space and constant operations for pop push min !!

O(n+1) is still O(n) and for that matter, even the earlier implementation had O(n) space ::)

Your implementation, is that really correct??
Lets say we are trying to put elements 5,7,3,4,1

So, stack states are,
1. [5,5]
2. [5,2,5]
3. [5,2,-2,5]
4. [5,2,-2,-1,5]
5. [5,2,-2,-1,-4,5]

Calling min gives 5.

The problem with your code is that you forgot to check the min element during push. That is quite easy to correct though. Your code works quite nicely that way. Great idea of using differences, it totally skipped me.

-- AI

Title: Re: Compiled Google Interview Questions
Post by TenaliRaman on Nov 26^th, 2006, 8:53pm

on 11/26/06 at 20:26:11, Ivan wrote:

Any comments on this one?

Well, the question 5 is still kinda unclear to me. I dont have a clue as to what they want. You can make any assumptions regarding the solution and end up with an answer.

If you are considering them as tree merging as i had earlier stated, then it could be a bit more involved. However, if you are simply considering the N companies as N letters of alphabets and merging operation is simply binary bracketing of these N letters then the number of ways to do that is Catalan(N).

-- AI

Title: Re: Compiled Google Interview Questions
Post by VaMpIrE on Nov 26^th, 2006, 9:09pm

yeah i forgot to write that .. the last push in PUSH should be push the minimum(elem,min)
for : 5,7,3,4,1 the states would be
5 5
5 2 5
5 2 -2 3
5 2 -2 1 3
5 2 -2 1 -2 1
so min now gives 1
pop gives 1 and changes the min to (min-elem) = 3
I think that right (unless i did some typing mistake )
you see i am storing the diff and using the signs to navigate and make decision ;D
The imp point is i am trying to avoid the usage of two stacks right from start. Thus got an idea for this so for larger values works fine

Title: Re: Compiled Google Interview Questions
Post by VaMpIrE on Nov 26^th, 2006, 9:20pm

yeah same here .. i didnt get the 5th question.
But yes , it looks more to me like bracketing problem.

Title: Re: Compiled Google Interview Questions
Post by satheesh on Mar 14^th, 2007, 9:47pm

To merge the companies say (1,2,3,4) only the cases like

1+2,1+2+3,1+2+3+4
1+2,3+4,1+2+3+4
1+2+3,4,1+2+3+4
1+2+3+4

have been considered.
What happened to the cases like,

1+3, 2+4, 1+3+2+4 ?
many combinations are like this, I guess.

Title: Re: Compiled Google Interview Questions
Post by tim612 on Aug 23^rd, 2007, 9:56pm

on 11/19/06 at 14:59:13, Eigenray wrote:

But, but, then in addition to your 3n/2 pointer advancements, you have 3n/2 counter increments. And those are like log(n) each!

Don't increments amortize to O(1)?

Addition of arbitrary numbers is O(log(n)), but addition of 1 to an arbitrary number is just O(1).

Title: Re: Compiled Google Interview Questions
Post by Eigenray on Sep 4^th, 2007, 8:18pm

on 08/23/07 at 21:56:50, tim612 wrote:

Don't increments amortize to O(1)?

Next time I shall use the appropriate emoticon.

Title: Re: Compiled Google Interview Questions
Post by mad on Feb 9^th, 2008, 9:45pm

on 11/26/06 at 11:21:22, TenaliRaman wrote:

Yeah, you have got quite the right idea. However, a much more simpler implementation of this strategy is,

Code:

I don't get it. If we call min() twice, what will happen?
I think we should develop a method that can get a minimum from the remaining stack also. Any ways for that?

Title: Re: Compiled Google Interview Questions
Post by towr on Feb 10^th, 2008, 7:12am

on 02/09/08 at 21:45:08, mad wrote:

I don't get it. If we call min() twice, what will happen?

It return the value of the top element both times. (Top doesn't remove the element)

Quote:

I think we should develop a method that can get a minimum from the remaining stack also. Any ways for that?

Well, it wouldn't be much of a stack if you can just remove an element in the middle somewhere. So just pop the stack till you've reached the minimum, or otherwise use a different data-structure.

Title: Re: Compiled Google Interview Questions
Post by mad on Mar 3^rd, 2008, 7:57am

But will min() return the same element again without popping the top element?
In the above eg., calling min will be 1,1 and not 1,3.

Title: Re: Compiled Google Interview Questions
Post by towr on Mar 3^rd, 2008, 8:50am

on 03/03/08 at 07:57:56, mad wrote:

But will min() return the same element again without popping the top element?
In the above eg., calling min will be 1,1 and not 1,3.

min() doesn't change any variables; so however often you call it it will do exactly the same thing each time.
Not until you call pop or push will it do anything else.

Title: Re: Compiled Google Interview Questions
Post by purple_nurple on Jul 6^th, 2008, 1:26am

ANS for 5 (?):

Given M companies, the number of unique pairs is M*(M-1)/2 (the number of unique mergers possible).

Once a merge occurs, there are M - 1 remaining companies.

So I think the solution should be
(Product i=2 to N) i * (i - 1) / 2

(although conceptually it is (Product i=N to 2 step -1))

Which is
N!*(N-1)! / 2^(N-1)

... Is that right?