Google Interview Question






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

One option is to combine heap (to get top) with hashtable (to find element in heap). That way insert is o(logn) and retrieval is o(1).

- superstar007 July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution is a leftist tree. The complexity is O(log n) for melding.

- AB July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Leftist Tree ... I don't see the connection?

- music_lover January 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Heap or the priority queue must be STABLE, that is important for the expected stack behaviour i suppose.

- yemre_ank October 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

Solution constant time for all operations (using hashmaps):
It basicly uses 2 hashes. One mapping element -> count and other mapping count -> stack of elements;

public class FrequencyStack<T> {
	private final Map<T, Integer> countMap = new HashMap<T, Integer>();
	private final Map<Integer, Set<T>> stackMap = new HashMap<Integer, Set<T>>();
	private int maxCount = 0;
	public void push(T o) {
		Integer c = countMap.get(o);
		if (c == null) {
			countMap.put(o, c = 1);
		} else {
			countMap.put(o, ++c);
		}
		Set<T> set = stackMap.get(c);
		if (set == null)
			stackMap.put(c, set = new LinkedHashSet<T>());
		set.add(o);
		if (c > maxCount)
			maxCount = c;
	}	
	public T pop() {
		if (maxCount == 0)
			return null;
		Set<T> set = stackMap.get(maxCount);
		T o = set.iterator().next();
		set.remove(o);
		if (maxCount == 1) {
			countMap.remove(o);
		}
		if (set.size() == 0) {
			stackMap.remove(maxCount);
			--maxCount;
		}
		return o;
	}	
	public T top() {
		if (maxCount == 0) 
			return null;
		return stackMap.get(maxCount).iterator().next();
	}	
}

- lucas.eustaquio August 02, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This will not work for multiple pops as the value of maxCount is not getting updated after a pop.
Using a sortedMap would be a better solution

- Gaurav August 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The max is being updated in method pop.
Code:

if (set.size() == 0) {
	stackMap.remove(maxCount);
	--maxCount;
}

A set with size zero means that it has no more values at maxCount. Tested it with JUnit.
A sorted map would increase the overall complexity in logn. A linkedHashSet has predictable iteration order, that is the order that elements are added. Unfornatelly, i'm poping the element that appeared first at that count. It shoul be the last one (stack behavior). But i would stick to that implementation, and say i that using another implementation of a map that have a way of retrieving the last key would be correct. For exemple the same linkedhashset of apache commons codec.

- lucas.eustaquio August 04, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I've a doubt if Pop() is really O(1) complexity. Let we've below order of push():

push(7)
push(5)
push(9)
push(3)
push(7)
push(3)
push(9)
push(7)
push(3)
push(7)
push(9)
push(7)

So, the frequency is as below
7 -> 5
3 -> 3
9 -> 3
5 -> 1

Now, first pop() would remove 7 as it's with highest frequency (5). A second pop() should remove 3 as it's next highest frequency (3). I'm lost how it's maintained in your approach (in constant time). Third pop() should removes 9, and final pop should remove 5. Sorry, I'm not familiar with Java code. So, your explanation would be appreciated to resolve this confusion.

- anonymous August 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That is correct. But in my implementation, if you push a number 5 times you will have to pop it 5 times also.
Operations:
1. Push: Check the current count of the pushed item, getting it from a hashmap. If the count is zero, add count = 1, else increments count, and adds the the element in another map indexed by its count. Updates the current max count if needed. All oprations are O(1).
2. Pop: get the list of items from the map indexed by count using max count. Retrieve a element from it, and remove from the list. This list is also a hash, so removal O(1). If this list is now empty, decrements max count. It also decrements the current count of the element (another map) by one.

All I used was hash, so it must be O(1) since all operations i use are constant, dont you agree?

By the way, the output for your pushs are:

Pop 1 -> 7
Pop 2 -> 7
Pop 3 -> 7
Pop 4 -> 3
Pop 5 -> 9
Pop 6 -> 7
Pop 7 -> 3
Pop 8 -> 9
Pop 9 -> 7
Pop 10 -> 5
Pop 11 -> 9
Pop 12 -> 3

- lucas.eustaquio August 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

By the way, i just pushed 1.000.000 elements and then poped all of then. The total time was 1.6s, and that for the whole operation(adding and poping).
Add avg: 0.0011
Pop avg: 0.0005
For 100.000 elements it was:
Add avg: 0.00208
Pop avg: 0.00155

For less elements the avg was higher because of the overhead for some operations was less amortized. But it shows consntant time behavior.

- lucas.eustaquio August 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Where are you updating stack map. Suppose if i push 3 3 times, and 2 4 times.
pop 1 -> 2
pop 2 -> 2
pop 3 -> 3 (Here 3 is 3 times, 2 is two times).
Where is stackmap being update. Still stackmap points to the old counts. I am not familiar to java much

- kiran May 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think lucas.eustaquio's idea is neat and correct.
I'm just curious why using 'LinkedHashSet' (a more complex data structure) rather than 'Stack' (a simpler data structure) in the 'stackMap'.
Maybe 'LinkedHashSet' is lucas.eustaquio's favorite data structure :)

- Alva0930 March 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

isn't it a heap then?

- nirvanaforu July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it's not heap exactly. Heap assures top and getMax in O(1) and O(logn) respectively. But, for push it'd be O(n). 'Coz when push (x) will be called, it needs finding x in heap - which would take linear time. Then a heapify would be needed to adjust heap property.

- anon July 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about binary tree: each node stores Item and Number of times it was added. Comparison made by items, but when Push called tree structure is updated in such a way that Number[Parent]>=Number[Child]. This update can be done in O(log n) using left and right turns. The most frequent element will be on top, so Pop is O(1).
However, the problem may be that tree may become very unbalanced.

- Zerg July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is good solution except for the condition of unbalanced.

- Avinash November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry this doesn't work forex <val, count>
         5,3
        /
     3,2
        \
        4,1
now pushing 3 two times BST property is lost

- Avinash November 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

I think using linked list and hash table all operation can be supported in O(1). I am thinking about this solution, if I'll achieve it then I'll post for further discussion.

- Socrates July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It can't be O(1). Finding an element in linked list (for Push operation) would take O(n).

- anon July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if Hash table maintains frequency as well as an array of nodes in the link list corresponding to HashKey. so when we push we either create a new node which becomes tail or if hash key exists we insert this node in the existing list (anywhere).

lemme know your thoughts on this

- Sem April 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A solution to this problem would be to 1st create a height balanced BST and from that BST create a stack.
1.) Traverse the items and create a height balanced BST- the frequency would be considered.- o(log n)
2.) Traverse the tree in an inorder manner and push these elements into a stack. o(n) is the total complexity and it would be o(1) amortized.
So we have the stack with us now:
push: o(1) amortized
pop: o(1)
top: o(1)

- Anonymous July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

oops time complexity is wrong,
in a HB BST the total insertion time for n elements is nlogn
and inorder tranversal for n elements would be n
so it would be nlogn/n=log n
push would be o(log n) amortized

- Anonymous July 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would use LRU implementation in this situation. For example: you could use LinkedHashMap from java collections.

push(), pop() and top() => O(1) average

- m@}{ July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But more correctly it would be to use binary heap (priority queue) and hash table.

push(), pop() => O(lgN)
top() => O(1)

- m@}{ July 14, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why would you need a binary heap, or any data structure other than a simple array? use maybe just an unsorted array, and if you are going to use a hash anyway, why not add info about currentIndex in the array, along its frequency, inside the HashMap (if it's deleted, set currentIndex=-1) ? O(1), O(1), O(1)... please let me know. Thank you.

- Julie July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh sorry! I had a wrong understanding of the question.. please ignore. thank you!

- Julie July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey79400" class="run-this">#include<iostream.h>
#include<conio.h>
#include<stdio.h>
# define MAXSIZE 200
# define TAB 128
int stack[MAXSIZE][2];
int table[TAB][2];
int top,max;
void push(int);
int pop();
int hash(int n,bool p)
{
int h;
h=n%TAB;
if(p==0)
{

if(!table[h])
{
table[h][0]=n;
table[h][1]=1;
}
else
++table[h][1];
}
if(p==1)
--table[h][1];
return table[h][1];
}

main()
{
int will=1,i,num;
while(will ==1)
{
printf("MAIN MENU: 1.Add element to stack2.Delete element from the stack");
scanf("%d",&will);
switch(will)
{
case 1:
printf("Enter the data... ");
scanf("%d",&num);
push(num);
printf("Max freq %d ",max);
break;
case 2: i=pop();
printf("Value returned from pop function is %d ",i);
break;
default: printf("Invalid Choice . ");
}
printf(" Do you want to do more operations on Stack ( 1 for yes, any other key to exit) ");
scanf("%d" , &will);
}
getch();
}
void push(int y)
{
int k;
if(top>MAXSIZE)
{
printf("STACK FULL");
return;
}
else
{
top++;
stack[top][0]=y;
stack[top][1]=hash(y,0);
if(max<stack[top][1])
{
max=stack[top][1];
}
printf("current top %d '",stack[top][0]);
printf("current's frequency %d '\n'",stack[top][1]);
}
}
int pop()
{
int a,i;
if(top<=0)
{
printf("STACK EMPTY");
return 0;
}

if(stack[top][1]<max)
{ i=stack[top][0];
stack[top][1]=hash(i,1);
top--;
a=pop();
push(i);
return a;
}
else
{
a=stack[top][0];
stack[top][1]=hash(a,1);
top--;
max--;
return a;
}
}
</pre><pre title="CodeMonkey79400" input="yes">
</pre>

- Anonymous July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the code above pops until d mode element is found, pops it and then pushes others back; using recursion. What will the complexity ?
I think it is push O(1) and pop O(n)

- Anonymous July 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n) is too expensive. And, I doubt how you achieve O(1) for Push().

- anon July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A binary Heap with hash map to index the nodes and then using 'increase key' when same item is added

- kk July 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

can we design push() ,pop() and top() interface using self ordering link lists with property that every node will have count : the number of times it has been accessed and the node with largest count will be at top. it is O(n) solution. any improvements?

- mrn July 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

using hashtable in this case where numbers are random in range is a wastage of space.So here again : time/space tradeoff :)

- mrn July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess hashtable will not improve the overall time complexity which will anyways be O(n) for pushing. The heaps as priority queues are meant for that purpose and implement increase key in O(n) time. So, we can search for the node using any traversal method and increase the frequency and update the heap

- kk July 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about splay tree?

- Anonymous July 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about min heap?

- software engineer July 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

May be this would work (if I understood the problem correctly)

Data Structure:
a) Map (key = input item, value = Ref of a Node - explained next)
b) Doubly linked list (class level: MAX Node Ref, Object level: Count, Set of Items)

This would give ability to solve all operations in O(1).

In push(item) or pop():
- (If item is already present then) We can go to the actual Node directly (using Map 'value'). No need of (binary or other) search for 'count numbers'.
- We will only need, previous &/or next element (as push() or pop() just changes the count value by 1). This can be achieved using Doubly linked list.
- We will need to have collections of items to get the 'item' back from Max count Ref Node. This collections could be Set of items to remove element (on pop()) from set of element, merge elements etc. in constant time.

Would like to hear any improvements in this scheme.

- Aryabhatt July 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Thanks for the clarification. Now, I can comprehend your implementation.

However, I believe hash() can give O(1) time on average, not for worst case complexity. Just think you've 1000 entries all with same frequency. Now, when you push a particular value x, time to extract x from those 1000 entries can't be O(1). Overall, I think your approach is good enough (manageable code size with good complexity).

- anonymous August 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you misunderstood the pop procedure. The pop hash isn't mapping count to all elements with same frequency, it is mapping count to another hash with all elements at that frequency. Its a hash of hashes. With a good hash function it will be O(1) on average.
It behaved pretty well in my 1.000.000 elements tests. There was way more than 1000 elements at the same frequency, and the pop time was constant, actually it decreased with more elements (amortization effect).

- lucas.eustaquio August 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A single max heap. Each node has two fields frequency and stack element.

push - find the element in heap -> O(n)
if element is present
increment its frequency
Heapify - O(logn)
else
insert the element with frequency 1
Pop Delete the max heap - O(1)
top - max heap element O(1)

Correct me if I'm wrong..

- Kirubakaran August 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think top always returns recently added element and not most frequently added element.

- Chandu September 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@eepiyush: Why spam CC with OLD posts only.
Go to stackoverflow, and post there, your moron!

People gave complete solution there. Specially lucas's solution was perfect. you fucking moron can't get a solution...then why do u repost it!

- anonymous September 05, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dude, the proper way to handle this is to use Report Dup link given with each question. you can point the correct question there along with abusing (if you wish).

- ACP Pradyuman September 05, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, CC needs an easier way to find dups; it's too much work right now.

'a website has lots of posts; how would you go about finding a first-cut of similar ones, to make it easier for people to find dups?'. I have to say, stackoverflow already does this better - it brings up a list of possibly related posts, even when you're writing your question. Though, there are so many of them. Hum; a better way to do that could be a product to sell them...

fwiw I did find an earlier dup from Jul 2011 and reported this one, but I could swear I saw one in early 2010 at latest.

- jeremiah.bullfrog October 10, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

have one general stack implementation and one Heap .. (Heapify based on frequeny not based on element value)

can any one tell me the time complexity for the above logic .. as well as any other good algo for the same.

- Anonymous September 07, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

#include <iostream>
#include <stack>
#include <climits>
#include <boost/unordered_map.hpp>

using namespace std;
using namespace boost;

template <typename T>
struct Node{
    int freq;
    T val;
};

template <typename T>
class freqstack{
private:
    stack<T> s;
    unordered_map<T, int> m;
    Node<T>* heap[1000];
    int heapsize;
    int parent(int index)
    {
        return index / 2;
    }
    int leftchild(int index)
    {
        return index<<1;
    }
    int rightchild(int index)
    {
        return (index<<1) + 1;
    }
    void swap(int i, int j)
    {
        m[heap[i]->val] = j;
        m[heap[j]->val] = i;
        Node<T>* temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    void increase(int index)
    {
        int p = parent(index);
        if (heap[p]->freq < heap[index]->freq)
        {
            swap(p, index);
            increase(p);
        }
    }
    void decrease(int index)
    {
        if (heap[index]->freq == 0)
        {
            swap(index, heapsize);
            m.erase(heap[heapsize]->val);
            delete heap[heapsize];
            --heapsize;
        }
        int left = leftchild(index);
        int right = rightchild(index);
        int largest = index;
        if (left <= heapsize && heap[left]->freq > heap[largest]->freq)
        {
            largest = left;
        }
        if (right <= heapsize && heap[right]->freq > heap[largest]->freq)
        {
            largest = right;
        }
        if (largest != index)
        {
            swap(largest, index);
            decrease(largest);
        }
    }
public:
    freqstack()
    {
        heap[0] = new Node<T>();
        heap[0]->freq = INT_MAX;
        heapsize = 0;
    }
    void push(T v)
    {
        if (m.find(v) == m.end())
        {
            if (heapsize == 999)
            {
                cerr << "no space" << endl;
                return;
            }
            ++heapsize;
            m.insert(pair<T, int>(v, heapsize));
            heap[heapsize] = new Node<T>();
            heap[heapsize]->val = v;
            heap[heapsize]->freq = 1;
        }
        else
        {
            int index = m[v];
            heap[index]->freq++;
            increase(index);
        }
        s.push(v);
    }
    void pop()
    {
        if (s.size() == 0)
        {
            cerr << "no element" << endl;
            return;
        }
        int index = m[s.top()];
        heap[index]->freq--;
        decrease(index);
        s.pop();
    }
    T top()
    {
        return s.top();
    }
    T max()
    {
        if (s.size() == 0)
        {
            cerr << "no element" << endl;
            return -1;
        }
        return heap[1]->val;
    }
    ~freqstack()
    {
        for (int i = 0; i <= heapsize; ++i)
        {
            delete heap[i];
        }
    }
};

int main()
{
    freqstack<int> s;
    s.push(1);
    cout << s.max() << endl;
    s.push(2);
    s.push(2);
    cout << s.max() << endl;
    s.push(3);
    s.push(3);
    s.push(3);
    cout << s.max() << endl;
    s.push(2);
    s.push(2);
    cout << s.max() << endl;
    s.pop();
    s.pop();
    cout << s.max() << endl;
    s.push(7);
    s.push(5);
    s.push(9);
    s.push(7);
    s.push(9);
    s.push(7);
    s.push(7);
    s.push(9);
    s.push(7);
    cout << s.max() << endl;
}

- wenlei.zhouwl May 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do push/pop in Best case O(1), worst case O(logn).
Have an HeapTable which stores freequency of an element such that the parent has a higher freequency than the two childs. It Have a HashTable to store the element.
HeapTable has a pointer into HashTable and viceversa for each element.

Push operation
Hash the element into the hash table.
1. If it exists, follow the pointer into the HeapTable and increment the freequency. We may have to compare with the parent node and ensure that the HeapTable remains in sorted order. worst case - O(logn), best case O(1).
2. If the element does not exist, add the element in the hash table and take the next space in HeapTable and update the freequency to 1. Add pointers from hash table to HeapTable amd vice versa.

Pop operation
1. Take the root element from HeapTable, decrement count, follow the pointer and return the element.
2. Adjust the HeapTable such that it remains in sorted order. Best case O(1), worst case O(logn).
3. If count becomes 0, we need to remove the element from hash table.

- gavinashg September 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@gavinashg - But you are not supporting the 'top' operation !

- kewl_coder December 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create 2 data structure, a max-heap b ased on a array an a hashmap

The array is ordered according to the number of the hits. So an extra hit is a heapifyUp and a new hit is addition at the last index of the heap

The hashmap contains the item as key and its index in the previous heap structure as the value.When an item is popped out completely, it is removed from this hashmap.

Peek/Top: O(1)
Push: (O(logN) if it is a existing element
O(1) if it is a new element

Pop: This is ambiguous if pop decreases a hit or completely pops the element out. Whatever the answer, its a heap pop and hence it is O(logN)

- biswajit.86 April 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple:

class FreqStack {
public:
    map<int, int> base;
    map<int, stack<int> > freq;
    int maxF;
    FreqStack() {
        maxF = 0;
    }
    
    void push(int x) {
        base[x]++;
        int f = base[x];
        freq[f].push(x);
        maxF = max(maxF, f);
    }
    
    int pop() {
        int x = freq[maxF].top();
        freq[maxF].pop();
        base[x]--;
        if(freq[maxF].empty()) {
            maxF--;
        }
        return x;
    }
};

leetcode.com/problems/maximum-frequency-stack/

- Rajat.nitp July 10, 2020 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More