Yahoo Interview Question
Software Engineer / DevelopersAssuming stack is represented using a linked list and the telephone numbers are stored as integer. Data would hold the next telephone number when the function returns. I am using recursion to do to the last element and saving it in the data and then pushing back all the rest.
void dequeue(Stack* s, int* data) {
int r = pop(&s); //Remove from head, head will be modified to head->next, so passing &s
if(s == NULL) { // We have reached the end of the list and r contains the first element entered in the stack
*data = r;
return;
}
else {
dequeue(s, data);
push(&s, r);
}
}
This code should work but I think its very inefficient. The problem is that we are returning just one telephone number each call, so O(n) per retrieval. If the user wants to process all the telephone numbers present in the stack, we could have returned all the telephone numbers in a FIFO fashion but the restriction of no extra memory allocation is allowed keeps me from doing that.
Following is the code using recursion in Java, which does the job. I have used the built-in Stack (java.util) Data structure. But this should work with any other Stack implementation. Following is the code:
To test this you could write a main progam which initializes the stack & calls this method:
Main code snippet:
Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
System.out.println(pop(stack));
Recursive function:
private static Integer pop(Stack<Integer> stack) {
Integer temp = null, temp1 = null;
if(stack.size() == 1) {
temp = stack.pop();
} else {
temp1 = stack.pop();
temp = pop(stack);
stack.push(temp1);
}
return temp;
}
Since we're using recursion - aren't we already using another stack ?
- Coder July 09, 2011hence making this a two stack problem ;)