Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,071 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:
Jan 31, 2010
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (7)
Mar 27, 2010
This post has been removed. Please see our
Community Guidelines or
Terms of Service for more information.
Mar 27, 2010
This post has been removed. Please see our
Community Guidelines or
Terms of Service for more information.
0 of 1 people found this helpful
Mar 30, 2010
Declare two stacks. One is the real stack of data. The other is a temporary one. Pop from real to temp. As u pop, check for minimum, save it in a variable. When finished, pop from temp stack back to real stack.
Stack S1; //stack contains data of ints
int Stack::getmin(Stack& S1)
{
int min=1000000; //initialize min
Stack S2;
//Transfer all from S1 to S2
while(!S1.isEmpty())
{
int temp = S1.pop();
if (temp<min)
{
min = temp; //set minimum
}
S2.push(temp); //put items in S2
}//end while
//Transfer all from S2 back to S1
while(!S2.isEmpty())
{
S1.push(S2.pop());
}
return min;
}//end getmin
Stack S1; //stack contains data of ints
int Stack::getmin(Stack& S1)
{
int min=1000000; //initialize min
Stack S2;
//Transfer all from S1 to S2
while(!S1.isEmpty())
{
int temp = S1.pop();
if (temp<min)
{
min = temp; //set minimum
}
S2.push(temp); //put items in S2
}//end while
//Transfer all from S2 back to S1
while(!S2.isEmpty())
{
S1.push(S2.pop());
}
return min;
}//end getmin
Helpful Answer?
Yes |
No
Inappropriate?
0 of 1 people found this helpful
Apr 22, 2010
Wouldn't be easier to just have a variable min and compare to each int as you push it onto the stack:
int min=firstInt;
if(min>=nextPush)
min=nextPush;
Really you could just make that into a separate method too and just call it with push . . . or maybe I'm over simplifying.
int min=firstInt;
if(min>=nextPush)
min=nextPush;
Really you could just make that into a separate method too and just call it with push . . . or maybe I'm over simplifying.
Helpful Answer?
Yes |
No
Inappropriate?
Jan 18, 2011
Jake,
It's not that simple. Say you pushed 1, 2, and 3, and then popped 1. If you just keep track of the minimum that was pushed, you would still have 1 but that's not even in the stack anymore.
You also can't just erase the value if you pop it off, because then a situation that was like push 1, 1, 2, 3, pop 1 would give you the wrong answer (i.e. should still be 1).
It's not that simple. Say you pushed 1, 2, and 3, and then popped 1. If you just keep track of the minimum that was pushed, you would still have 1 but that's not even in the stack anymore.
You also can't just erase the value if you pop it off, because then a situation that was like push 1, 1, 2, 3, pop 1 would give you the wrong answer (i.e. should still be 1).
Helpful Answer?
Yes |
No
Inappropriate?
Mar 23, 2011
template <class item>
class gmStack{
private
Stack<item> S;
Stack<item> m;
public
gmStack();
~gmStack();
void push(item *);
item * pop();
item * getMin();
}
void gmStack::push(item * i){
S.push(i);
item *t=m.pop(); m.push(t);
if(i<=t) m.push(i);
}
item *gmStack::pop(){
item *t=m.pop();
item *r=S.pop();
if(t!=r) m.push(t);
return r;
}
item *gmStack::getMin(){
item *t=m.pop(); m.push(t);
return t;
}
gmStack::gmStack(){
S=new Stack();
m=new Stack();
}
gmStack::~gmStack(){
delete S;
delete m;
}
class gmStack{
private
Stack<item> S;
Stack<item> m;
public
gmStack();
~gmStack();
void push(item *);
item * pop();
item * getMin();
}
void gmStack::push(item * i){
S.push(i);
item *t=m.pop(); m.push(t);
if(i<=t) m.push(i);
}
item *gmStack::pop(){
item *t=m.pop();
item *r=S.pop();
if(t!=r) m.push(t);
return r;
}
item *gmStack::getMin(){
item *t=m.pop(); m.push(t);
return t;
}
gmStack::gmStack(){
S=new Stack();
m=new Stack();
}
gmStack::~gmStack(){
delete S;
delete m;
}
Helpful Answer?
Yes |
No
Inappropriate?
Members can
answer or comment on this question
–
Join Now (It's Free) or
Sign In
You might also be interested in: Interview Questions, Software Engineer Intern Interview Questions, Google Interview
0 of 1 people found this helpful
by Interview Candidate: