## Yahoo Interview Question for Software Engineer / Developers

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

Since we're using recursion - aren't we already using another stack ?
hence making this a two stack problem ;)

Comment hidden because of low score. Click to expand.
0

+1

Comment hidden because of low score. Click to expand.
0

The other stack is implicit.

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

May be implemented using recursion.

Comment hidden because of low score. Click to expand.
0

Recursion uses stack in the back end, so technically, we are still using an extra data structure... if the interviewer does not have problem with that, it's a different thing.

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

yes, seems using the recursion and processing from the last element of the stack is the suitable approach for this scenario.Any other optimal technique ?

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

Assuming 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) {
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.

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

{
top = index;
for(index = 0; index<=top; index++)
{
num = pop();
push(num+100); // update
printf("\t %d ", stack[index] );
}
}

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

public int ProcessStack(ref Stack<int> stck, int val)
{
if (val == 0)
return val;

int newVal = ProcessStack(ref stck, stck.Pop());
if (newVal != 0)
{
stck.Push(val);
return newVal;
}

return val;
}

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

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;
}

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

If your stack is linked list, just reverse the list. Pop and reverse again. You can reverse list using O(1) space

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.

### 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.