Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer Intern at Google:
Feb 8, 2010
How to implement a queue simply using two stacks and how to implement a highly efficient queue using two stacks.
Add Tags
[?]
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (5)
Feb 28, 2010
Because that is the simple implementation, pretty much the exact same answer I gave them, there apparently is a more efficient way of modelling it.
Helpful Answer?
Yes |
No
Inappropriate?
Mar 27, 2010
Queue should implement FIFO.
Let's have a group of task 1 -10 to be performed
//declare two stacks
Stack S1, S2;
//feed stack S1 with the tasks 1 - 10
for(int i=1; i<=10;i++)
{
S1.push(i);
}
//Now S1 contains {10,9,8,7,6,5,4,3,2,1} where the top is 10
//Transfer all from S1 to S2
while(!S1.isEmpty())
{
S2.push(S1.pop());
}
//Now S2 contains {1,2,3,4,5,6,7,8,9,10} where the top is 1
You can now pop tasks from S2. Task 1 will be the first to pop and so on...
Therefore, you just simulated FIFO using two stacks
Let's have a group of task 1 -10 to be performed
//declare two stacks
Stack S1, S2;
//feed stack S1 with the tasks 1 - 10
for(int i=1; i<=10;i++)
{
S1.push(i);
}
//Now S1 contains {10,9,8,7,6,5,4,3,2,1} where the top is 10
//Transfer all from S1 to S2
while(!S1.isEmpty())
{
S2.push(S1.pop());
}
//Now S2 contains {1,2,3,4,5,6,7,8,9,10} where the top is 1
You can now pop tasks from S2. Task 1 will be the first to pop and so on...
Therefore, you just simulated FIFO using two stacks
Helpful Answer?
Yes |
No
Inappropriate?
Oct 31, 2010
blakdogg's answer is efficient, and has amortized time O(n).
The trick here is that when you enqueue an element, you only push into one stack. Only move element when dequeue. Otherwise, running time will be more than O(n).
Details are in CLRS amortized analysis.
The trick here is that when you enqueue an element, you only push into one stack. Only move element when dequeue. Otherwise, running time will be more than O(n).
Details are in CLRS amortized analysis.
Helpful Answer?
Yes |
No
Inappropriate?
Mar 23, 2011
template <class item>
class Q{
private
Stack S1,S2;
public
Q();
~Q();
void enQ(item *);
item* dQ();
int empty();
}
void Q::enQ(item * i){
if(S1.empty&&~S2.empty)
while(~S2.empty) S1.push(S2.pop());
S1.push(i);
return;
}
item Q::dQ(){
if(S2.empty&&~S1.empty)
while(~S1.empty) S2.push(S1.pop());
return S2.empty?0:S2.pop;
}
int Q::empty(){
return S1.empty()&&S2.empty;
}
Q::Q(){
S1=new Stack;
S2=new Stack;
}
Q::~Q(){
delete S1;
delete S2;
}
class Q{
private
Stack S1,S2;
public
Q();
~Q();
void enQ(item *);
item* dQ();
int empty();
}
void Q::enQ(item * i){
if(S1.empty&&~S2.empty)
while(~S2.empty) S1.push(S2.pop());
S1.push(i);
return;
}
item Q::dQ(){
if(S2.empty&&~S1.empty)
while(~S1.empty) S2.push(S1.pop());
return S2.empty?0:S2.pop;
}
int Q::empty(){
return S1.empty()&&S2.empty;
}
Q::Q(){
S1=new Stack;
S2=new Stack;
}
Q::~Q(){
delete S1;
delete S2;
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer Intern Interview Questions, Google Interview
0 of 0 people found this helpful
by blakdogg:
queue.insert() calls in.push()
queue.remove()
if (out.notEmpty)
out.pop()
else {
while(in.notEmpty)
out.push(in.pop)
}
Don't get how this would be two questions.