Amazon Interview Question for Software Engineer / Developers


Country: -




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

public static void revertStack(Stack<Integer> s)
{
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);
}
}

- Anonymous October 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Complexity in O(n*n)

- nitin December 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- i2infinity October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;

}
}

- msankith October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think the stack's implementation is sealed here.

- Joe October 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Emad October 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ishantagarwal1986 October 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- choi.bumyong October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

ignore the main class.. not sure what happened.

- choi.bumyong October 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Absolutely clear solution! Thanks!

- Anonymous December 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void ReverseStack(Stack s)
{
if(isEmpty(s) return;
x=pop(s);
ReverseStack(s);
RecursivePush(s,x);
}
RecursivePush(Stack s,int x);
{
int temp;
if(isEmpty(s)) {push(s,x) return;}
temp=pop(s);
recursivepush(s,x);
push(s,temp);
}

- Mandar November 06, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Rohanraj December 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ashutosh pandey November 20, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

reverse(Stack s)
{
int x=0;
if(!s.empty())
{
x=s.pop();
reverse(s);
}
s.push(x);

}

- Anonymous October 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

it will not reverse the stack. the order of stack element will remain same. just an extra 0 will be added.

- kamal October 23, 2011 | Flag
Comment hidden because of low score. Click to expand.


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More