Amazon Interview Question Interns
Country: United States
Interview Type: Phone Interview
Add and Remove are trivial. But for the mode, we can do this in O(1) time.
When you add to the stack, you keep a hashtable containing a mapping between number and count and the location of the number in the heap. <Number, Count, Heap Location>. Now, you can keep a max heap of pairs <Number, Count>. When you add a number to the stack, you update it in the hashtable. Next, if the number doesn't exist in the heap, we add it to the heap (in logn time), then update the hashtable to point to it. If it DOES exist in the heap already, we remove it from the heap, then add it again with its new count to the heap in O(logn) time.
In total, adding to the stack would take 2logn -> O(logn). Getting the mode would be O(1), as it would just be looking at the top of the max heap.
I really like this question, because it proves whether you understand this basic data structure or not. Here is my implementation; (i)my stack is going to be a array of numbers. (ii) push(int) will store the number in to the array and increment a position of the array and puts the number into a hashmap. (iii) pop() will decrement the position of the array and decrements the number in the hashmap. (iv)mode() takes the max occurrences of the given number and returns it.
import java.util.*;
public class stack{
private int [] iStack;
private int currentPos = -1;
private HashMap <Integer,Integer> map = new HashMap<Integer,Integer>();
/*
* Constructor: initializes the size
* of the stack.
*/
public stack(int size){
iStack= new int[size];
}
/*
* push: pushes a number into the stack
*/
public void push(int number){
if((++currentPos) < iStack.length){
iStack[currentPos] = number;
//put in a hashmap for mode.
if(map.get(iStack[currentPos])!= null)
map.put(iStack[currentPos], map.get(iStack[currentPos])+1);
else
map.put(iStack[currentPos],1);
}
else
System.out.println("There's no space in the stack");
}
/*
* pop: takes the last number placed
* in the stack.
*/
public int pop(){
if(currentPos > -1){
if((map.get(iStack[currentPos]) != null) || (map.get(iStack[currentPos]) > 0))
map.put(iStack[currentPos],map.get(iStack[currentPos]-1));
return iStack[currentPos--];
}
else
return -1;
}
/*
* peek: returnst the last number
* placed in the stack.
*/
public int peek(){
if(currentPos > -1)
return iStack[currentPos];
else
return -1;
}
/*
* mode: returns the most repeated number,
* if two numbers have the max value, it
* it retursn the the latest number being
* pushed to the stack.
*/
public int mode(){
int max=0,val=0,index=0;
if(currentPos > 0)
for(int i=0;i<=currentPos; i++){
val=map.get(iStack[i]);
if(val>max){
max=val;
index =i;
}
}
return iStack[index];
}
public static void main(String [] args){
stack newStack = new stack(10);
newStack.push(1);
newStack.push(5);
newStack.push(8);
newStack.push(3);
newStack.push(2);
newStack.push(3);
newStack.push(1);
// System.out.println(newStack.peek());
// newStack.push(2);
// System.out.println(newStack.pop());
System.out.println(newStack.mode());
}
}
Clean Code with push, pop and mode operations in O(1).
HashMap to store the counts. LinkedHashSet to store frequencies. Extending Java stack class.
Can handle multiple modes also, in O(1).
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Stack;
class StackMode extends Stack<Integer>{
HashMap<Integer,LinkedHashSet<Integer>> lists;
HashMap<Integer,Integer> counts;
int maxCount;
public StackMode()
{
maxCount = 1;
lists = new HashMap<>();
counts = new HashMap<>();
lists.put(1,new LinkedHashSet<Integer>());
}
public void push(int v)
{
super.push(v);
Integer i = counts.get(v);
if(i == null)
{
counts.put(v,1);
lists.get(1).add(v);
maxCount = Math.max(maxCount,1);
}
else
{
if(lists.get(i+1) == null)
lists.put(i+1, new LinkedHashSet<Integer>());
lists.get(i+1).add(v);
counts.put(v, i+1);
maxCount = Math.max(i+1, maxCount);
}
}
public Integer pop()
{
if(super.isEmpty())return null;
int val = super.pop();
int count = counts.get(val);
lists.get(count).remove(val);
if(count == maxCount && lists.get(count).size() == 0)
maxCount--;
count--;
System.out.println("c="+count);
if(count > 0)
{
lists.get(count).add(val);
}
counts.put(val,count);
return val;
}
public ArrayList<Integer> mode()
{
if(super.isEmpty())return null;
return new ArrayList<Integer>(lists.get(maxCount));
}
}
public class StackModeTester
{
public static void main(String[] args)
{
StackMode t = new StackMode();
t.push(1);
t.push(3);
t.push(4);
t.push(6);
t.push(6);
t.push(1);
t.push(6);
t.push(5);
System.out.println("Peek "+t.peek());
System.out.println("Mode "+t.mode());
t.pop();
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
}
}
Clean code to perform push(), pop() and mode() in O(1).
Uses HashMap to store counts (frequencies) . LinkedTreeSet to perform operation in O(1). The code can return multiple modes as well, ie. when there are more than one number with highest frequency, all in O(1).
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Stack;
class StackMode extends Stack<Integer>{
HashMap<Integer,LinkedHashSet<Integer>> lists;
HashMap<Integer,Integer> counts;
int maxCount;
public StackMode()
{
maxCount = 1;
lists = new HashMap<>();
counts = new HashMap<>();
lists.put(1,new LinkedHashSet<Integer>());
}
public void push(int v)
{
super.push(v);
Integer i = counts.get(v);
if(i == null)
{
counts.put(v,1);
lists.get(1).add(v);
maxCount = Math.max(maxCount,1);
}
else
{
if(lists.get(i+1) == null)
lists.put(i+1, new LinkedHashSet<Integer>());
lists.get(i+1).add(v);
counts.put(v, i+1);
maxCount = Math.max(i+1, maxCount);
}
}
public Integer pop()
{
if(super.isEmpty())return null;
int val = super.pop();
int count = counts.get(val);
lists.get(count).remove(val);
if(count == maxCount && lists.get(count).size() == 0)
maxCount--;
count--;
System.out.println("c="+count);
if(count > 0)
{
lists.get(count).add(val);
}
counts.put(val,count);
return val;
}
public ArrayList<Integer> mode()
{
if(super.isEmpty())return null;
return new ArrayList<Integer>(lists.get(maxCount));
}
}
public class StackModeTester
{
public static void main(String[] args)
{
StackMode t = new StackMode();
t.push(1);
t.push(3);
t.push(4);
t.push(6);
t.push(6);
t.push(1);
t.push(6);
t.push(5);
System.out.println("Peek "+t.peek());
System.out.println("Mode "+t.mode());
t.pop();
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
t.pop();
System.out.println("Mode "+t.mode());
}
}
Keep 2 stacks, one that works as normal, and another that contains elements of max freq (and which only gets a value pushed or popped if the current max freq changes - this works similarly to the question in CTCI on maintaining 2 stacks to track the max or min value in a stack).
- JW April 04, 2015Also have a hash from elements to their count.
push: add element to 1st stack and increase element's frequency in hash. If element's freq > current max freq (freq of top element on 2nd stack), push added element to 2nd stack.
pop: remove top element of 1st stack and decrease element's frequency in hash. If popped element equals the element on the top of the 2nd stack, see if it's frequency falls below the next element below in the 2nd stack. If so, pop the element from the 2nd stack.
mode: return top element of 2nd stack
All operations are O(1).