Yahoo Interview Question
Software Engineer / DevelopersCouple of corrections:
OrigStack = { 2, 6, 5, 1, 3}
NewStack = {NULL};
//Assume OrgiStack has atleast one element
NewStack.push(OrigStack.pop());
while(!OrigStack.isEmpty())
{
val = OrigStack.pop();
while(!NewStack.isEmpty() && NewStack.top() < val) {
OrigStack.push(NewStack.pop());
}
NewStack.push(val);
}
OrigStack = NewStack; //Done
To do this recursively we need to do the following:
1) Remove the top item
2) Reverse the remaining stack
3) Put the top item we removed at the bottom of the stack
2) Is a recursive call. Also, since we have no way of directly putting an item at the bottom of a stack, we can implement 3) recursively as well. The following would work:
import java.util.Stack;
public class StackReverse
{
public void reverse(Stack stack)
{
if (!stack.isEmpty())
{
Object top = stack.pop();
reverse(stack);
moveItemToBottom(stack, top);
}
}
private void moveItemToBottom(Stack stack, Object bottomItem)
{
if (stack.isEmpty())
{
stack.push(bottomItem);
}
else
{
Object o = stack.pop();
moveItemToBottom(stack, bottomItem);
stack.push(o);
}
}
}
Oops, that was for the reverse a stack in place question. Posted it to the wrong thread.
Thanks mattj777! Actually in place sorting of stack can be done by modifying your solution of reverse stack!!
Instead of AddToBottom, we need to AddToCorrectLocation.
Thanks mattj777, I wrote a stack sort program based on your idea.
void insert_item(stack<int> &s, int k) {
if (s.empty())
s.push(k);
else {
int j = s.top();
if (j < k) {
s.push(k);
}
else {
s.pop();
insert_item(s, k);
s.push(j);
}
}
}
void stack_sort(stack<int> &s) {
if (!s.empty()) {
int k = s.top();
s.pop();
stack_sort(s);
insert_item(s, k);
}
}
int main() {
stack<int> s;
for (int i = 0; i < 10; ++i) {
int k;
cin >> k;
s.push(k);
}
stack_sort(s);
while (!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
return 0;
}
void sort(stack)
{
type x;
if (!isEmpty(stack)) {
x = pop(stack);
sort(stack);
insert(x, stack);
}
}
void insert(x, stack)
{
type y;
if (!isEmpty(stack) && top(stack) < x) {
y = pop(stack);
insert(x, stack);
push(y, stack);
} else {
push(x, stack);
}
}
brilliant.. just use & before stack in each function and it works fine!!!
code:
void insert(stack<int> &stk,int x)
{
if(!stk.empty() && stk.top()>x)
{
int y =stk.top();
stk.pop();
insert(stk,x);
stk.push(y);
}
else
{
stk.push(x);
}
}
void sort_stk(stack<int> &stk)
{
if(!stk.empty())
{
int x=stk.top();
stk.pop();
cout<<x<<endl;
sort_stk(stk);
insert(stk,x);
}
return;
}
using two stacks
void SortStack(stack<int>& stk)
{
int elem;
stack<int> secStk;
if(stk.empty())
return;
secStk.push(stk.top());
stk.pop();
while(!stk.empty())
{
elem = stk.top();
stk.pop();
if(elem >= secStk.top())
{
secStk.push(elem);
}
else
{
int data;
while(!secStk.empty() && secStk.top() > elem)
{
data = secStk.top();
secStk.pop();
stk.push(data);
}
secStk.push(elem);
}
}
while(!secStk.empty())
{
stk.push(secStk.top());
secStk.pop();
}
}
Are we allowed to instantiate one more stack ?
- posix4e September 12, 2010If yes, the problem is straightforward.
OrigStack = { 2, 6, 5, 1, 3}
NewStack = {NULL};
//Assume OrgiStack has atleast one element
NewStack.push(OrigStack.pop());
while(!OrigStack.isEmpty())
{
val = OrigStack.pop();
while(NewStack.top() < val) {
OrigStack.push(NewStack.top());
}
NewStack.push(val);
}
OrigStack = NewStack; //Done
Let me know suggestions. This the first trivial algo i can think about at the moment.