CareerCup

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

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 priority-Indexed Queue ie. max heap + hash table

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.

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

we can use priority que or bst for this

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)

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

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

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

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

Maintain a hashed map datastructure to store elements
Key : element
value : counter
Each time calculate max inserted element and keep track of it and complexity o(1) for pop

struct FrequentElementStack {
 Map<Element, Integer> elements = ..
 Element frequentElement = ..

 int addElement(Element element) {
  // returns counter of each element being inserted
 // calculate max element counter and element itself
 }

 Element getFrequentElement() {
  //returns most frequently added element
 }
}

Maintain a hashed map datastructure to store elements
Key : element
value : counter
Each time calculate max inserted element and keep track of it and complexity o(1) for pop

struct FrequentElementStack {
 Map<Element, Integer> elements = ..
 Element frequentElement = ..

 int addElement(Element element) {
  // returns counter of each element being inserted
 // calculate max element counter and element itself
 }

 Element getFrequentElement() {
  //returns most frequently added element
 }
}

Sorry guz!! I din't consider DS for keeping counter based elements

What does it mean to have a stack which returns element with highest frequency? Does it follow LIFO as well? And we have to implement this additional logic of returning max frequency element on the top of that?