Author |
Topic: Compiled Google Interview Questions (Read 3721 times) |
|
Ivan
Junior Member
Gender: 
Posts: 70
|
 |
Compiled Google Interview Questions
« on: Nov 17th, 2006, 5:52pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Compiled Google Interview Questions
« Reply #1 on: Nov 18th, 2006, 9:03am » |
Quote Modify
|
on Nov 17th, 2006, 5:52pm, 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[/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
}
|
| « Last Edit: Nov 18th, 2006, 5:10pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Ashwin
Newbie
Posts: 6
|
|
Re: Compiled Google Interview Questions
« Reply #2 on: Nov 18th, 2006, 5:18pm » |
Quote Modify
|
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()
|
|
IP Logged |
|
|
|
Grimbal
Newbie
Gender:
Posts: 11
|
|
Re: Compiled Google Interview Questions
« Reply #3 on: Nov 18th, 2006, 5:41pm » |
Quote Modify
|
on Nov 18th, 2006, 9:03am, 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).
|
|
IP Logged |
|
|
|
Eigenray
Newbie
Posts: 1
|
|
Re: Compiled Google Interview Questions
« Reply #4 on: Nov 18th, 2006, 7:29pm » |
Quote Modify
|
on Nov 18th, 2006, 5:41pm, 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.
|
|
IP Logged |
|
|
|
Ashwin
Newbie
Posts: 6
|
|
Re: Compiled Google Interview Questions
« Reply #5 on: Nov 18th, 2006, 9:13pm » |
Quote Modify
|
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;
}
|
| « Last Edit: Nov 18th, 2006, 9:16pm by Ashwin » |
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Compiled Google Interview Questions
« Reply #6 on: Nov 19th, 2006, 3:25am » |
Quote Modify
|
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]
|
| « Last Edit: Nov 19th, 2006, 3:30am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Compiled Google Interview Questions
« Reply #7 on: Nov 19th, 2006, 7:10am » |
Quote Modify
|
on Nov 19th, 2006, 3:25am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Compiled Google Interview Questions
« Reply #8 on: Nov 19th, 2006, 1:52pm » |
Quote Modify
|
Aaaah. Now I understand why the forum marked all posts as "unread".
I thought it was another YaBB glitch.
|
| « Last Edit: Nov 19th, 2006, 1:54pm by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Compiled Google Interview Questions
« Reply #9 on: Nov 19th, 2006, 1:53pm » |
Quote Modify
|
on Nov 18th, 2006, 7:29pm, 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. 
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Compiled Google Interview Questions
« Reply #10 on: Nov 19th, 2006, 2:59pm » |
Quote Modify
|
on Nov 19th, 2006, 1:53pm, Grimbal wrote:
But you save a pointer which is also log(n) storage. |
|
But, but, then in addition to your 3n/2 pointer advancements, you have 3n/2 counter increments. And those are like log(n) each!
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Compiled Google Interview Questions
« Reply #11 on: Nov 19th, 2006, 7:34pm » |
Quote Modify
|
on Nov 19th, 2006, 2:59pm, 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
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Compiled Google Interview Questions
« Reply #12 on: Nov 20th, 2006, 1:33am » |
Quote Modify
|
on Nov 19th, 2006, 2:59pm, 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. 
|
|
IP Logged |
|
|
|
VaMpIrE
Newbie
gIvE mE bLoOd N i GiVe yOu fReEdOm
Gender:
Posts: 15
|
|
Re: Compiled Google Interview Questions
« Reply #13 on: Nov 24th, 2006, 8:34pm » |
Quote Modify
|
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 !!]
|
|
IP Logged |
|
|
|
balanagireddy.tcs
Newbie
Gender: 
Posts: 28
|
|
Re: Compiled Google Interview Questions
« Reply #14 on: Nov 25th, 2006, 1:43am » |
Quote Modify
|
can someone explain 3. ii ?
|
|
IP Logged |
|
|
|
balanagireddy.tcs
Newbie
Gender:
Posts: 28
|
|
Re: Compiled Google Interview Questions
« Reply #15 on: Nov 25th, 2006, 1:48am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
balanagireddy.tcs
Newbie
Gender:
Posts: 28
|
|
Re: Compiled Google Interview Questions
« Reply #16 on: Nov 25th, 2006, 1:48am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
balanagireddy.tcs
Newbie
Gender:
Posts: 28
|
|
Re: Compiled Google Interview Questions
« Reply #17 on: Nov 25th, 2006, 1:48am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
balanagireddy.tcs
Newbie
Gender:
Posts: 28
|
|
Re: Compiled Google Interview Questions
« Reply #18 on: Nov 25th, 2006, 1:52am » |
Quote Modify
|
For the sixth question
Suppose if the linked list is using array implementation there is a constant time solution.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Compiled Google Interview Questions
« Reply #19 on: Nov 25th, 2006, 2:24am » |
Quote Modify
|
on Nov 24th, 2006, 8:34pm, 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
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Compiled Google Interview Questions
« Reply #21 on: Nov 25th, 2006, 2:28am » |
Quote Modify
|
on Nov 25th, 2006, 1:52am, 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?
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
VaMpIrE
Newbie
gIvE mE bLoOd N i GiVe yOu fReEdOm
Gender:
Posts: 15
|
|
Re: Compiled Google Interview Questions
« Reply #22 on: Nov 26th, 2006, 10:36am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Compiled Google Interview Questions
« Reply #23 on: Nov 26th, 2006, 11:21am » |
Quote Modify
|
on Nov 26th, 2006, 10:36am, VaMpIrE wrote: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
<snip><snip>
I guess its ok now.
|
|
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
|
| « Last Edit: Nov 26th, 2006, 11:29am by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Ivan
Junior Member
Gender:
Posts: 70
|
|
Re: Compiled Google Interview Questions
« Reply #24 on: Nov 26th, 2006, 12:00pm » |
Quote Modify
|
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 Nov 25th, 2006, 1:48am, balanagireddy.tcs wrote: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
|
|
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print