Interview Question


Country: India




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

No

- Anonymous July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you just have to take another stack and run a loop keep popping from one stack push to another stack dispose off first stack and use the second stack this will be done in o(n)

- deepika July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No dear, we have to reverse the content not to generate a new stack

&

ONLY USING STACK OPRATION

- niraj.nijju July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ya right but here we are reversing the content only in second stack the contents would be reversed right? how are you performing it on o(n2) can you plz elaborate ?

- deepika July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

reversestack(stack)
{
data=pop
reversestack(s);
reversepush(S,data)
}

recursivepush(s,data)
{
if(empty stack)
{push(s,data) return}
temp=pop
recursivepush(s,data)
push(s,temp)
}

- niraj.nijju July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@niraj nijju: using recursion , you are creating internal stack by your code..

- cobra July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@niraj: Recursion internally uses stack to function so this is again not avoiding memory constraint!

- words&lyrics July 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void reverse()
{
if(empty())
return
 int i;
i=pop();
reverse();
push(i);

- abc July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will be same stack

- niraj.nijju July 21, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think it really does the reversing, it just gets the same stack with the same order of data

- Anonymous July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <vector>
using namespace std;

template <class VT>
class Stack
{
public:
Stack()
{
}

~Stack()
{
}

VT top()
{
if(size() > 0) return list_[size() - 1];
else return 0;
}

int push(VT v)
{
list_.push_back(v);
return 0;
}

void pop()
{
if(size() > 0) list_.pop_back();
}

int size()
{
return list_.size();
}
private:
vector<VT> list_;
};

/// Using a temp stack to reverse_stack
void reverse_stack(Stack<int> & stack)
{
if(stack.size() == 0) return;

int size = stack.size();
int top_v = 0;
Stack<int> stack_x;
while(size)
{
top_v = stack.top();
stack.pop();
int step = size - 1;
while(step)
{
stack_x.push(stack.top());
stack.pop();
step --;
}
stack.push(top_v);
while(stack_x.size())
{
stack.push(stack_x.top());
stack_x.pop();
}

size --;
}

}

/// Using 2 stacks to reverse stack
void reverse_stack_2(Stack<int> & stack)
{
Stack<int> stack_x, stack_y;
while(stack.size())
{
stack_x.push(stack.top());
stack.pop();
}
while(stack_x.size())
{
stack_y.push(stack_x.top());
stack_x.pop();
}
while(stack_y.size())
{
stack.push(stack_y.top());
stack_y.pop();
}
}

- zombie July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is no any space constraint, it can be done with o(n), poping from orginal and pushing to the second and hence reversing it.
But, even in the case of recursion, we are using additional space though it is incremental

- ethioer July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If there is no space constraint, and original stack addresses must be same then it can be done in O(n). Just take three stacks, first pop all elements from original stack(S1) and push into S2. Repeat the same step between S2 and S3. Finally, repeat it between S3 and S1. Now, S1 is a reversed stack and it takes O(3n) => O(n).

- nik July 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void reverse(Stack<Integer> test){
if(test.isEmpty()){
return;
}
int i= get_and_remove_last(test);

reverse(test);
test.push(i);
}
public static int get_and_remove_last(Stack<Integer> test){
int result=test.pop();
if(test.isEmpty()){
return result;
}
else{
int last=get_and_remove_last(test);
test.push(result);
return last;
}
}

- Chengyun Zuo July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to use a second data structure to store the result. It's not possible to reverse the stack in-place. If you pop an item, how would you push it to the bottom of the same stack without stack bashing?

- Yev August 16, 2012 | 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