Amazon Interview Question Software Engineer / Developers
Team: KDK - Kindle Development Kit
Country: India
Interview Type: In-Person
suppose we want to insert 20 element (its just a random number) and in all these 20 number first element which we insert is the highest of all element and second one is the lowest element in all other then only one element goes in max stack and one element goes on min stack then we pop that max element and min too after that main stack have 18 element but max stack and min stack does not have any value .and then u r not able to find range .
if i m right then please let me know ...
No, ur wrong.
Didn't u read the solution properly ???
Wen ur inserting the 19th and 20th element (assuming 18 elements are already there), the maxStack and minStack are not empty. They contain the max and min as the elements were inserted till now. They will contain the max and min as were being formed while inserting the elements till this stage.
If u insert 19th element as highest and 20th element as lowest, then these two elements will become topmost elements in maxStack and minStack. When u remove them, the previous max and min will retain top positions in maxStack and minStack, so that u can get the range correctly.
Did u get this ???
Very interesting! Can you please elaborate on what you mean by maintaining "maintain two different stacks inside a stack called maxStack and minStack for max and min elements"?
You need to maintain max and min in the stack class along with two other stack. One for maintaining stack of maximum values and stack of minimum values. When a new maximum is formed that max will be updated and also pushed in maxStack. Now if max is popped out we will pop from maxStack and now new element at top of stack will be new max. please see the java code below
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package results;
import java.util.HashMap;
import java.util.Iterator;
import java.util.*;
public class Main {
public int max;
public int min;
public Stack st;
public Stack minSt;
public Stack maxSt;
Main(){
max=0;
min=1000;
st = new Stack();
minSt = new Stack();
maxSt = new Stack();
}
public void pushIn(int n){
st.push(new Integer(n));
if (n > max){
System.out.println("new max is "+n);
max = n;
maxSt.push(new Integer(n));
}
if (n < min){
min = n;
minSt.push(new Integer(n));
System.out.println("new min is "+n);
}
}
public void popOut(){
Integer a = (Integer)st.pop();
if ( a.intValue() == max){
maxSt.pop();
max = (Integer)maxSt.peek();
System.out.println("new max is "+max);
}
if ( a.intValue() == min){
minSt.pop();
min = (Integer)minSt.peek();
System.out.println("new min is "+min);
}
}
public void printStack(){
System.out.println(minSt);
System.out.println(maxSt);
System.out.println(st);
}
public int rangeStack(){
return(max-min);
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Main o = new Main();
o.pushIn(10);
o.pushIn(20);
o.pushIn(12);
o.pushIn(32);
o.pushIn(45);
o.pushIn(5);
o.pushIn(1);
System.out.println(o.rangeStack());
//o.printStack();
o.popOut();
//o.printStack();
o.popOut();
//o.printStack();
o.popOut();
o.printStack();
}
}
People here seem to often post excited comments like that without being sarcastic. Seems like you did well in your interview.
@BlackMath
You described the question in a very good way. I could actually imagine how the interviewer asked you the first question and after you answered, asked you the second question. I wish more people posted questions in the way that you did. Good job.
@BlackMath
I honestly thought that your answer was really good. But I couldn't figure out for the life of me how that could be misinterpreted as sarcasm.
/**
*
*/
package amazon;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Stack;
/**
* @author Vibs
*
*/
public class StackForRange extends Stack<Integer>{
Stack<HashMap<Integer, Integer>> stackMin ;
Stack<HashMap<Integer, Integer>> stackMax ;
public StackForRange() {
stackMin = new Stack<HashMap<Integer,Integer>>();
stackMax = new Stack<HashMap<Integer,Integer>>();
}
public int range(){
return max()-min();
}
public Integer pop(){
Integer value = super.pop();
if(value==max()){
int count = stackMax.peek().get(value);
if(count ==1) stackMax.pop();
else stackMax.peek().put(value, count-1);
}
if(value==min()){
int count = stackMin.peek().get(value);
if(count ==1) stackMin.pop();
else stackMin.peek().put(value, count-1);
}
return value;
}
public void push(int value){
if(value==max()){
int countMax = stackMax.peek().get(value);
stackMax.peek().put(value, countMax+1);
}
if(value==min()){
int countMin = stackMin.peek().get(value);
stackMin.peek().put(value, countMin+1);
}
HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
map.put(value, 1);
if(value<=min()) stackMin.push(map);
if(value>=max()) stackMax.push(map);
super.push(value);
}
public Integer min(){
Integer key = null;
if(stackMin.isEmpty())
return Integer.MAX_VALUE;
else {
HashMap<Integer, Integer> map = stackMin.peek();
Iterator iter = map.keySet().iterator();
while(iter.hasNext())
key = (Integer)iter.next();
return key;
}
}
public int max(){
Integer key = null;
if(stackMax.isEmpty())
return Integer.MIN_VALUE;
else {
HashMap<Integer, Integer> map = stackMax.peek();
Iterator iter = map.keySet().iterator();
while(iter.hasNext())
key = (Integer)iter.next();
return key;
}
}
public static void main(String [] args){
StackForRange rangeStack = new StackForRange();
rangeStack.push(5);
rangeStack.push(3);
rangeStack.push(6);
rangeStack.push(10);
rangeStack.push(1);
rangeStack.push(1);
rangeStack.pop();
System.out.println("range is "+rangeStack.range());
}
}
I don't know if i get your approach. According to my understanding, there seems to be a bug:
For instance if I want to insert the following stuff one by one: 7 , 8 , 1 ,6 , 9 ,2 .
Assume I have stackMax for the first element. Then:
stackMax: 7
stackMax: 8 , 7
stackMin : 1
what happens to 6 ???
ok, i would like to answer this.
inserting : 7, 8, 1, 6, 9, 2
insert element : 7
stack : 7
maxstack : 7
minstack : 7
insert element : 8
stack : 7, 8 (top of stack is the last element in this list)
maxstack : 7, 8
minstack : 7
insert element : 1
stack : 7, 8, 1
maxstack : 7, 8
minstack : 7, 1
insert element : 6
stack : 7, 8, 1, 6
maxstack : 7, 8
minstack : 7, 1
insert element : 9
stack : 7, 8, 1, 6, 9
maxstack : 7, 8, 9
minstack : 7, 1
insert element : 2
stack : 7, 8, 1, 6, 9, 2
maxstack : 7, 8, 9
minstack : 7, 1
Now if we pop 2, no effect on maxstack and minstack.
we can find the range correctly. Range is 9 - 1 = 8
Now we pop 9, maxstack : 7, 8
minstack : no change
we can still find the range correctly. Range is 8 - 1 = 7
Now we pop 6, maxstack and minstack no effect
we can still find the range correctly. Range is 8 - 1 = 7.
so, inserting or popping out 6 does not change anything,
since it is in between maxstack top value and minstack top value.
we can't pop out 7 or 8 before 6 is popped out.
so, we dont need to save 6 in the maxstack and minstack.
The algorithm works correctly for range.
Please evaluate the test case in this way, before posting comments.
I think this answers your second question too.
Please revert back your comments.
//to find range in a stack
#include<stdio.h>
int max[20];
int min[20];
int stack[20];
int top=-1,tmax=-1, tmin=-1;
void push(int num);
void pop();
void display();
main()
{
int ch=0, no;
while(ch<=3)
{
printf("\n enter your choice \n 1. PUSH \n 2. POP \n 3. Display \n");
scanf("%d", &ch);
switch(ch)
{
case 1: printf(" \n enter the element to be pushed \n ");
scanf("%d",&no);
push(no);
break;
case 2: pop();
break;
case 3: display();
break;
}
}
}
void push(int num)
{
if(top==-1)
{
max[++tmax]=num;
min[++tmin]=num;
}
else
{
if(num>max[tmax])
max[++tmax]=num;
else
if(num<min[tmin])
min[++tmin]=num;
}
stack[++top]=num;
printf("\n range is %d \n", (max[tmax]-min[tmin]));
}
void display()
{
int i;
printf("\n stack is \n");
for(i=0;i<=top;i++)
printf(" %d ", stack[i]);
printf("\n range is %d \n", (max[tmax]-min[tmin]));
}
void pop()
{
if(top==-1)
{
printf(" \n stack is underflow \n ");
return;
}
else
{
if(stack[top]==max[tmax])
--tmax;
if(stack[top]==min[tmin])
--tmin;
top--;
printf("\n range is %d \n", (max[tmax]-min[tmin]));
}
}
package stringmanip;
import java.util.Stack ;
/**
*
* @author SAURAV
*/
class stackElement {
int number ;
int maxTillNow ;
int minTillNow ;
stackElement(int number , int maxTillNow , int minTillNow )
{
this.number = number ;
this.maxTillNow = maxTillNow ;
this.minTillNow = minTillNow ;
}
public class StackRange {
public static void main(String[] args)
{
Stack<stackElement> s = new Stack() ;
stackElement temp ;
int[] numbers ={10,1,13,4,5,67,8,9} ;
for (int i =0 ;i<numbers.length ; i++)
{
stackElement num = new stackElement(numbers[i],numbers[i],numbers[i]) ;
if(s.empty())
{
s.push(num) ;
}
else
{
stackElement top = s.peek() ;
if((num.maxTillNow)<top.maxTillNow)
{
num.maxTillNow = top.maxTillNow ;
}
if((num.minTillNow )>=top.minTillNow )
{
num.minTillNow = top.minTillNow ;
}
s.push(num)
;
}
}
int range ;
range = s.peek().maxTillNow - s.peek().minTillNow ;
System.out.println("Range now : "+range) ;
while(!s.empty())
{
temp = s.pop() ;
System.out.print("Number : "+temp.number+" MaxTillNow: "+temp.maxTillNow+" minTillNow :"+temp.minTillNow) ;
System.out.println() ;
}
}
}
i implemented a stackelement class along with two other parameters maxTillNow and minTillNow , Suppose we are inserting an element into an empty stack , by default , for that particular stack element that is pushed in , the max and min till then are that number itself , otherwise we compare the maxTillNow and minTillNow with the corresponding values of the top element of the stack built till now and update the values of the element to be pushed in , so we can get the range of stac k in O(1) at anytime . Please correct me if i went wrong anywhere or if you find a sentinel case for which the code fails .
The following is a solution which will allow the range to be retrieved in constant time O(1)
- Maintain 2 seperate stacks... This adds O(n) space complexity but doesn't affect the time.
- In the first stack, maintain the max element encountered so far...
- In the second stack, maintain the min element encountered so far...
-At any point of time, if u wish to get the range, query the top elements of the min and max stacks... O(1)
This is not the complete code and i have not tested it.
The last part for duplicates is not coded here.
But this will give an idea what i wrote there.
- BlackMath June 26, 2012public class MyStack { int maxSize; int arr[maxSize]; int size; int top; Stack<Integer> maxStack; Stack<Integer> minStack; MyStack (int size) { arr = new int[size]; maxSize = size; this.size = 0; top = -1; maxStack = new Stack<Integer>(); minStack = new Stack<Integer>(); } public int getTop () { if (size <= 0) return -1; return arr[size-1]; } public int getRange () { if (size <= 0) return -1; return (maxStack.top() - minStack.top()); } public void push (Integer s) { if (size >= maxSize - 1) return; arr[size] = s; size++; if ( ! maxStack.isEmpty()) { if (maxStack.top() < s) maxStack.push(s); } else maxStack.push(s); if ( ! minStack.isEmpty()) { if (minStack.top() > s) minStack.push(s); } else minStack.push(s); } public void pop () { if (size <= 0) return; int elementToPop = arr[size-1]; size--; if ( ! maxStack.isEmpty()) { if (maxStack.top() == elementToPop) maxStack.pop(); } if ( ! minStack.isEmpty()) { if (minStack.top() == elementToPop) minStack.pop(); } } }