Amazon Interview Question
SDE1sTeam: Advertising
Country: United States
Interview Type: In-Person
package queue;
import java.util.LinkedList;
import java.util.Queue;
import org.junit.Assert;
import org.junit.Test;
public class StackWithQueue<T> {
Queue<T> queue1;
Queue<T> queue2;
public StackWithQueue() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
// retrive all elements from queue1 except last one
// retrieved elements are stored in queue2
public T pop() {
T result = null;
while (queue1.size() > 1) {
queue2.offer(queue1.poll());
}
result = queue1.poll();
// swap two queues so that next push can add elements in order
Queue<T> temp = queue1;
queue1 = queue2;
queue2 = temp;
return result;
}
// push items to queue1 first
public void push(T value) {
queue1.offer(value);
}
}
package queue;
import org.junit.Assert;
import org.junit.Test;
public class StackWithQueueTest {
@Test
public void testStack() {
int[] arr = {1, 2, 3, 4};
StackWithQueue<Integer> stack = new StackWithQueue<>();
for (int i=0; i<arr.length; i++) {
stack.push(arr[i]);
}
Assert.assertEquals(4, stack.pop().intValue());
stack.push(5);
Assert.assertEquals(5, stack.pop().intValue());
Assert.assertEquals(3, stack.pop().intValue());
Assert.assertEquals(2, stack.pop().intValue());
Assert.assertEquals(1, stack.pop().intValue());
}
}
Creating a stack using two queues
package data.structures;
import java.util.Queue;
class StackUsingQueues<T> {
Queue<T> A ;
Queue<T> B;
StackUsingQueues(){
A = new java.util.LinkedList<T>();
B = new java.util.LinkedList<T>();
}
void push(T value){
if(A.isEmpty() && B.isEmpty())
A.add(value);
else if(!A.isEmpty()){
A.add(value);
}
else
B.add(value);
}
T pop(){
T result = null;
if(!A.isEmpty()){
while(A.size() > 1){
B.offer(A.poll());
}
result = A.poll();
}
else{
while(B.size() > 1){
A.offer(B.poll());
}
result = B.poll();
}
return result;
}
}
public class TestStackUsingQueues{
public static void main(String Args[]){
StackUsingQueues stack = new StackUsingQueues<Integer>();
int array[] = {1, 2, 3 ,4, 5};
stack.push(array[0]);
stack.push(array[1]);
stack.push(array[2]);
System.out.println((Integer)stack.pop());
System.out.println((Integer)stack.pop());
stack.push(array[3]);
stack.push(array[4]);
System.out.println((Integer)stack.pop());
System.out.println((Integer)stack.pop());
System.out.println((Integer)stack.pop());
}
}
Output:
3
2
5
4
1
public class StackImplementWithQueue {
private Queue<Integer>pushQueue;
private Queue<Integer>popQueue;
public StackImplementWithQueue() {
// TODO Auto-generated constructor stub
pushQueue=new LinkedList<Integer>();
popQueue=new LinkedList<Integer>();
}
public void push(int n){
pushQueue.add(n);
}
public int pop(){
if(pushQueue.isEmpty())
return -1;
int val;
while(true){
val=pushQueue.remove();
if(pushQueue.isEmpty()){
pushQueue=popQueue;
popQueue=new LinkedList<Integer>();
break;
}
else{
popQueue.add(val);
}
}
return val;
}
public void showStack(){
System.out.println(pushQueue);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
StackImplementWithQueue stw=new StackImplementWithQueue();
stw.push(10);
stw.push(23);
stw.showStack();
stw.pop();
stw.showStack();
stw.pop();
stw.showStack();
}
}
1. We can create a queue using stacks but vice versa is not possible according to me.
Queue using stacks:
1. Just pop all elements from first stack and push it in second.
2. Now pop all from the second , which is a queue.
But in FIFO , how many ever times we dequeue same process repeats. So not possible according to me.
package com.algo.stack;
import java.util.LinkedList;
import java.util.Queue;
public class StackQueue {
private Queue<Integer> queue1 = new LinkedList<Integer>();
private Queue<Integer> queue2 = new LinkedList<Integer>();
public void push(Integer value){
queue1.add(value);
}
public Integer pop(){
Integer val = null;
while(!queue1.isEmpty()){
val = queue1.poll();
if(queue1.peek()!=null){
queue2.offer(val);
}
}
while(!queue2.isEmpty()){
queue1.offer(queue2.poll());
}
return val;
}
}
This is impossible. I know because I've been a developer for 12 years. You cannot create a stack out of a queue...especially when posting homework questions as amazon in person interview questions...
Amazon wouldn't waste it's time with such a question...
It was a real question that amazon asked, you need to know the properties of a stack and the properties of a queue. Think about what you would need to achieve the properties of a stack using the properties of a queue
This is one possible solution. I am using LinkedList instead of Queue.
- Ognian.Kabranov September 25, 2014