Amazon Interview Question

Country: India

Comment hidden because of low score. Click to expand.
2
of 8 vote

Create a max priority queue based on frequency of element and hash the element in max priority queue using element as a key
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)

Comment hidden because of low score. Click to expand.
0

but how will you modify element in priority queue

Comment hidden because of low score. Click to expand.
0

Basically, just maintain the value in the hashmap as a Pair object<Address of the element in heap>.

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

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

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

Use priority-Indexed Queue ie. max heap + hash table

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

Isn't it as simple as creating a max-heap based on frequency. The pop will be O(1) as well as push because the frequency is increased by only one at time.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Perfect time optimal solution.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

sorry...O(nlogn)

Comment hidden because of low score. Click to expand.
-2
of 4 vote

we can use priority que or bst for this

Comment hidden because of low score. Click to expand.
0

details?

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

how would you maintain sorted array..every time you push or pop()?

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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)

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

@rotinom I can see that you have not understood my solution.
count is not a class variable, it is a local variable in one of the functions.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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)

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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)

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

}``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

<SCRIPT> alert(“Hacked ..... ha ha ha ...”); </SCRIPT>

Comment hidden because of low score. Click to expand.
-2
of 2 vote

<SCRIPT> alert(“Hacked ..... ha ha ha ...”); </SCRIPT>

Comment hidden because of low score. Click to expand.
-2
of 2 vote

/// 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
}
}
\\\

Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0

what about second pop, third pop? how would you maintain highest frequency element?

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

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.

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.