A very commonly asked question during interviews is to write a recursive solution to reverse a stack. A lot of discussion is out there with different kind of implementation varying from O(n*n) to O(n).My interest in this question is due to something else.
While I was getting ready for office my room-mate was having a telephonic interview with one of the IT companies in Bangalore. He was asked this question (Which is very straight forward if no constraints are given), with a constraint that he is supposed to use recursion and he is allowed to use only constant memory in each recursion. Well , when I saw this question I was pretty convinced that it can be done in O(n) given I use few bytes in each recursion and I decided to hack in my beloved "C++" to help me through it.
The approach that is explained here is a little non-trivial but not too difficult to understand. Now try this code :-
To understand "why this code is working" you will need to know how bits synchronously dance around your computer's hardware to make your code run.In case you don't get it read this blog entry.
Now, if you can manage to see the stack and how local variables are placed in there you should be able to observe that the way it is placed each time variable data is getting the same relative location in its own function's memory space. Given the same function is being called and size of memory assigned to it is same each time, it is possible to know where all variables are placed.
From above observation it can be concluded that distance between a variable of function with itself in next recursive call remains the same throughout.
If memory can be visualized as horizontal straight line as follows :-
Where, X is the variable (data) and function (reverse) get the memory between ' | '.Distance between two X's is same throughout.
Now when this information is available, distance between variable in each recursion can be calculated if the address of variable in previous recursion (prevdata) is available. As size of stack is known we know that (n-1)th element of stack should be replaced with 0th element, (n-2)th element with 1st element and so on. Upto half size of stack we can just take the data which is at the same distance from middle element and place it on the stack and replace the content at other point with current element of the stack. When recursion goes below half, it will have information available in variable data in reverse order, which we just need to place on the stack.
Hope you like this blog entry.Views and modifications are welcome.
While I was getting ready for office my room-mate was having a telephonic interview with one of the IT companies in Bangalore. He was asked this question (Which is very straight forward if no constraints are given), with a constraint that he is supposed to use recursion and he is allowed to use only constant memory in each recursion. Well , when I saw this question I was pretty convinced that it can be done in O(n) given I use few bytes in each recursion and I decided to hack in my beloved "C++" to help me through it.
The approach that is explained here is a little non-trivial but not too difficult to understand. Now try this code :-
void reverse(stack<int> &s,int *prevdata=0) {
int data,*t;
if(s.empty())
return;
data=s.top();
s.pop();
size++;
reverse(s,&data);
if(s.size() <= (size-1)/2) {
t=(int*((char*)(&data)-((((char*)&data)-((char*)prevdata))*((size-1)-s.size()*2)));
s.push(*t);
*t=data;
} else {
s.push(data);
}
}
To understand "why this code is working" you will need to know how bits synchronously dance around your computer's hardware to make your code run.In case you don't get it read this blog entry.
Now, if you can manage to see the stack and how local variables are placed in there you should be able to observe that the way it is placed each time variable data is getting the same relative location in its own function's memory space. Given the same function is being called and size of memory assigned to it is same each time, it is possible to know where all variables are placed.
From above observation it can be concluded that distance between a variable of function with itself in next recursive call remains the same throughout.
If memory can be visualized as horizontal straight line as follows :-
_| _ _ X _ _ _| _ _ X _ _ _| _ _ X _ _ _| _ _ X _ _ _| _ _ X _ _ _|
Where, X is the variable (data) and function (reverse) get the memory between ' | '.Distance between two X's is same throughout.
Now when this information is available, distance between variable in each recursion can be calculated if the address of variable in previous recursion (prevdata) is available. As size of stack is known we know that (n-1)th element of stack should be replaced with 0th element, (n-2)th element with 1st element and so on. Upto half size of stack we can just take the data which is at the same distance from middle element and place it on the stack and replace the content at other point with current element of the stack. When recursion goes below half, it will have information available in variable data in reverse order, which we just need to place on the stack.
Hope you like this blog entry.Views and modifications are welcome.
