Amazon Interview Question
Software Engineer / DevelopersCountry: -
Similar implementation in C++
CustomStack CustomStack::RecursiveReverse(CustomStack inputStack)
{
CustomStack tmpStack(_size);
int value;
//Base condition
//Vector of size 1 is by itself reversed
if(inputStack._Stack.size() == 1)
return inputStack;
//Pop the last item from the stack
value = inputStack.Pop();
//Recursive function call
tmpStack._Stack = RecursiveReverse(inputStack)._Stack;
//Insert the popped into the first position
tmpStack.RecursiveInsert(value);
return tmpStack;
}
int CustomStack::RecursiveInsert(int value)
{
if(this->_Stack.size() == 0)
{
this->Push(value);
}
else
{
int tmp = this->Pop();
this->RecursiveInsert(value);
this->Push(tmp);
}
return 0;
}
Reversing the stack is similar to reversing the singly linked list..
void ReverseStack(struct stack *oldtop,struct stack **newtop)
{
if(oldtop->next==NULL)
*newtop=oldtop;
else {
ReverseStack(oldtop->next,newtop);
oldtop->link->link=oldtop;
oldtop->link=NULL;
}
}
void ReverseStackRecursive(stack<int>* s)
{
if(!s || s->size() == 1) return;
for(int i = 0; i < s->size() ; i ++)
{
int head = s->top();
s->pop();
ReverseStackRecursiveAux(s, head, i); //insert the current head at position i from the bottom
}
}
void ReverseStackRecursiveAux(stack<int>* s, int value, int index)
{
if(s->size() == index)
{
s->push(value);
return;
}
int current = s->top();
s->pop();
ReverseStackRecursiveAux(s, value, index);
s->push(current);
}
Complexity will be O(n*n). We have to reverse element by element. Kindly suggest if you know a way to do this with lesser complexity.
public static void main(String[] args){
for(int i=1;i<stackSize;i++){
Object obj = reversestack(stack,i,0);
stack.push(obj);
}
}
public Object reverseStack(Stack stack, int toBeReversed, int current){
Object obj = stack.pop();
if(current == toBeReversed){
return obj;
}else{
Object obj2 = reverseStack(stack, toBeReversed, current+1);
stack.push(obj);
return obj2;
}
}
<pre lang="" line="1" title="CodeMonkey62146" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}
class ReverseStack {
// a simple recursive method that pops from the bottom of the stack
// and push that number
public void reverse(Stack<Integer> stack) {
if (stack.isEmpty())
return;
int bottom = popFromBottom(stack);
reverse(stack);
stack.push(bottom);
}
// recursive method that gets the number in the bottom of the stack
private Integer popFromBottom(Stack<Integer> stack) {
Integer oldValue = stack.pop();
// if the stack is empty after a pop operation, we know that
// we just got the number in the bottom of the stack and we can
// return this value
if (stack.isEmpty()) {
return oldValue;
}
// if this is not the number in the bottom of the stack, then keep going
Integer value = popFromBottom(stack);
// we need to put everything back into the stack except the number int he bottom
stack.push(oldValue);
return value;
}
}</pre><pre title="CodeMonkey62146" input="yes">
</pre>
static void Reverse(struct node** headRef) {
struct node* result = NULL;
struct node* current = *headRef;
struct node* next;
while (current != NULL) {
next = current->next; // tricky: note the next node
current->next = result; // move the node onto the result
result = current;
current = next;
}
*headRef = result;
}
/*Reverse Stack without knowing the data structure, Without using any other *data structure,only use stack operation i.e push(),pop(),top()...
* Below Code tested in C++11
*/
#include <cstdlib>
#include <iostream>
#include <stack>
using namespace std;
void appendStack(stack<int> &s, int a){
if (s.empty()) {
s.push(a);
return;
} else {
int o = s.top();
s.pop();
appendStack(s, a);
s.push(o);
}
}
void revertStack(stack<int> &s){
if (s.empty()) return;
int a = s.top();
s.pop();
revertStack(s);
appendStack(s, a);
}
void showstack(stack <int> s) {
while (!s.empty()){
cout << '\t' << s.top();
s.pop();
}
cout << '\n';
}
int main(){
stack<int> s ;
for(int i=0;i<10;i++)
s.push(i);
cout<<"Initial stack:- ";
showstack(s);
revertStack(s);
cout<<"reverse stack:- ";
showstack(s);
return 0;
}
public static void revertStack(Stack<Integer> s)
- Anonymous October 24, 2011{
if (s.isEmpty()) {
return;
} else {
Integer a = s.pop();
revertStack(s);
appendStack(s, a);
}
}
public static void appendStack(Stack<Integer> s, Integer a)
{
if (s.isEmpty()) {
s.push(a);
return;
} else {
Integer o = s.pop();
appendStack(s, a);
s.push(o);
}
}