Amazon Interview Question
Country: India
Python:
I didn't use any modules. collections.Counter(list).most_common(1)
would get most common element in a list right away
push -> just appends the given element to the stack
pop -> identifies common element, remove it from stack and return it to user
pop(): for a given list [2,2,2,1,1,3]
if length of stack is zero, throw an "Stack Empty" exception
else
convert the list to element's count and element [2,2,2,1,1,3] --> [(3, 2), (2, 1), (1, 3)]
sort and retrieve the last element -> [(1,3), (2,1), (3,2)] --> (3,2)
(3, 2) -> count is 3 and element is 2
remove element (2) from stack.
return the element (2)
class Stack(object):
""" Stack which pops out most common element """
def __init__(self, tlst=None):
if tlst is None:
tlst = []
self._stack = tlst
def push(self, elm):
self._stack.append(elm)
def pop(self):
if len(self._stack) == 0:
raise Exception('Stack is Empty')
stack = list(set(map(lambda x: (self._stack.count(x), x), \
self._stack)))
elm = sorted(stack, key=lambda e:e[0])[-1]
self._stack = filter(lambda x: x!=elm[1], self._stack)
return elm[1]
Testing:
>>> stack = Stack()
>>> stack.push(2)
>>> stack.push(2)
>>> stack.push(2)
>>> stack.push(1)
>>> stack.push(1)
>>> stack.push(3)
>>> stack._stack
[2, 2, 2, 1, 1, 3]
>>> stack.pop()
2
>>> stack._stack
[1, 1, 3]
>>> stack.pop()
1
>>> stack._stack
[3]
>>> stack.pop()
3
>>> stack._stack
[]
>>> stack.pop()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 10, in pop
Exception: Stack is Empty
>>>
Use Tree Map, create custom object with priority attribute. Create comparator to sort custom objects with priority attribute.
push method (entryItem): Create custom object of the entryItem remove the custom object from TreeMap if already exist. If already exist use existing object and increment the priority and add to TreeMap. If new use new custom object set priority1 and add to TreeMap.
pop: get last Entry which will be one which was most frequently added.
Take a hash map<Object(Element),Position in arraylist> and an arraylist(Stores the frequency) Now use priority queue and heapify when changes are made.
Though space requirement is high. still....O(log n ) ...time complexity ??
Take a hash map<Object(Element),Position in arraylist> and an arraylist(Stores the frequency) Now use priority queue and heapify when changes are made r made in arralist
Though space requirement is high. still....O(log n ) ...time complexity ??
Modify the stack by keeping an extra value frequency in the stack that is modify the structure of the stack like:
struct stack
{
int top;
int arr[size];
int freq;
}; Then further increment this value for every element in the stack and if for a particular element the frequency is greater than the previous element then push this element to the stack and thus the pop operation will lead to the most frequent element
You need the following DS:
HashMap<Integer, Stack<Integer>> countStackMap
HashMap<Integer, Integer> valueCountMap
int maxCount
For push operation:
1> Check if the element is present in valueCountMap
1a> If present then increment the count in valueCountMap and add a element (newCountOfThisElement -> Stack(newelement) in countStackMap ; if the newCountOfThisElement is present in countStackMap then (newCountOfThisElement -> Stack(newElement,.....other elements)
1a> If not present then add element in valueCountMap with count as 1 and add in countStackMap the key-value pair (1 -> stack(newElement,...old elements)
2> If the count of this new element is greater than maxCount ; increment maxCount by 1
For pop operation:
1> Return countStackMap.get(maxCount).pop()
2> Reduce the maxCount by 1 if the stack countStackMap.get(maxCount) is empty
Complexity:
push: O(1)
pop: O(1)
Code is as follows:
public class StackOnElementFrequency {
private HashMap<Integer, Stack<Integer>> countStackMap;
private HashMap<Integer, Integer> elementCountMap;
private int maxCount;
public StackOnElementFrequency() {
countStackMap = new HashMap<Integer, Stack<Integer>>();
elementCountMap = new HashMap<Integer, Integer>();
maxCount = 0;
}
public void push(int newElement) {
int count = 0;
if(elementCountMap.containsKey(newElement)) count = elementCountMap.get(newElement) + 1;
else count = 1;
elementCountMap.put(newElement, count);
if(countStackMap.containsKey(count)) countStackMap.get(count).push(newElement);
else {
Stack<Integer> stack = new Stack<Integer>();
stack.push(newElement);
countStackMap.put(count, stack);
}
if(count > maxCount) maxCount = count;
}
public int pop() {
if(maxCount == 0) {
System.err.println("Empty Stack");
return -255;
}
Stack<Integer> maxElementCountStack = countStackMap.get(maxCount);
int resultToPop = maxElementCountStack.pop();
if(maxElementCountStack.isEmpty()) {
countStackMap.remove(maxCount);
maxCount = maxCount - 1;
}
elementCountMap.put(resultToPop, elementCountMap.get(resultToPop) - 1);
if(elementCountMap.get(resultToPop) == 0) elementCountMap.remove(resultToPop);
return resultToPop;
}
}
what about the sequence:
push(10); // count = 1, maxCount = 1;
pop(10); // maxCount = 0;
push(10); // count = 2, maxCount = 2;
pop(10); // maxCount = 0
push(10); // count = 3, maxCount = 3;
pushd(5); // count = 1, maxCount = 3;
pop(10); // maxCount = 2
The maxCount = maxCount-1 line will cause you to lose items... Once the top item is removed, you cannot guarantee to get any of the other items in the stack.
What should be done if there are more than one most frequently added item ?
Say if I am adding a, b, c, d and e. If both a and b have the same frequency, what should be returned ? This will affect the way we design the data structure.
So my suggestion would be to have a maxHeap with the heap being created based on the frequency. So at any given time the most frequently added item will be at the top. After insertion the percolation should not stop when the frequencies are same. This will help in getting the newly added item.
Pop: Always o(1)
Insertion time if item is already in the heap: o(log n) for searching if the item is already in the heap + o(1) to increment the frequency + o(log n) for percolating up = o(log n)
Insertion time if the item is new: o(log n) for searching if the item is already in the heap + o(1) to insert + o(log n) for percolating up = o(log n)
This isn't a "real" stack, since there is no FIFO. More of a priority queue with a twist.
template <typename T>
class frequency_stack{
private:
struct pq_struct{
int key;
T value;
pq_struct(const int& k, const T& v) : key(k), value(v){}
bool operator<(const pq_struct& rhs) const {return key < rhs.key;}
}
public:
// Push an item - log(n)
void push(const T& val){
unordered_map<T, int>::iterator iter = count_table.find(T);
if(count_table.end() == iter){
iter = count_table.insert(val, 0);
}
p_queue.push(pq_struct(*iter, val));
++(*iter); // Increment our count
}
// remove the top item - log(n)
T pop(){
return p_queue.pop().value;
}
// Wipe out the history
void obliterate(const T& val){
count_table.erase(val);
}
private:
unordered_map<T, int> count_table;
priority_queue<pq_struct<T> > p_queue;
};
1.) create a hasmap Dictionary<Element, int > where int represents the frequency of the element added.
2.) Based on the highest frequency initialize an Array where each index represents the frequency of the element. This index holds a node with list of elements
3.) POP operation just pops from end of this array adding the elements to the node at the decremented position which is a unit operation
4.) Collision cases can be discussed with the interviewer on which element to pop so pop operation once the array is initialized is O(1);
Extra space is O(Maxfreq)+O(disctinctelement.count)
public class HashStack<T> {
private HashMap<T,Integer> map=new HashMap<T,Integer>();
private Stack<T> stack=new Stack<T>();
private int max=Integer.MIN_VALUE;
public void push(T t){
Stack <T> tmp=new Stack<T>();
int currentNum=0;
if (map.get(t)==null){
map.put(t, 1);
}else{
currentNum=map.get(t)+1;
map.put(t, currentNum);
}
if (currentNum>=max){
stack.push(t);
max=currentNum;
}else{
while (!stack.isEmpty()){
T value=stack.peek();
if (map.get(value)<currentNum){
break;
}else{
tmp.push(stack.pop());
}
}
while (!tmp.isEmpty()){
stack.push(tmp.pop());
}
}
}
public T Pop(){
return stack.pop();
}
}
/// class stack
{
// Map of value and count
map<int,int> Cntmap;
public:
void push(int val)
{
// Find val in map
// if found then increment map count
// else
// insert a pair (val,1)
}
int pop( )
{
// Find the Key in Cntmap with max value
// using std::max_element
// Decrement the Cntmap count for the popped val
}
}
\\\
Create a max priority queue based on frequency of element and hash the element in max priority queue using element as a key
- shsf July 10, 2013-insert element, check in hash if it is already added
if yes, then increase the frequency by one and heapify the priority queue ..
if no, then insert in hash table and priority queue with frequency one
O(lgn)
-getmax() O(1)