Question

Microsoft | OA Coding Questions and Solutions | Set - 99 | 2022

Answer 1

You need to implement the following interface:

 

public interface FindMaxFreqNumber {
	void add(int num); // adds a number to the sequence
	void removeOldest(); // removes the oldest inserted number
	int getMaxFreqNumber(); // returns (not removes) max frequent number
}

Answer 2

C++ Implementation:

 

 class FindMaxFreqNumber {
      // adds a number to the sequence
      struct comp{
             bool operator()(const pair<int,int> &a, const pair<int,int> &b) const{
                     return b.second<a.second;
             }
      };

      multiset<pair<int,int>,comp> st;  //for returning max frequent and removing its instance when removeoldest is called.
      unordered_map<int,int> mp;  //for elements frequency
      queue<int> q;   //for oldest

     void add(int num){
            q.push(num);
            mp[num]++;   //update frequency 
            st.insert({num,mp[num]});   //insert new instance in the multiset
     } 

     void removeOldest(){
            if(q.size()==0) return;   //if queue has no elements
            int old= q.front(); q.pop();   //pop from queue
            int freq= mp[old]--;   //decrease frequency because we remove its one instance
            st.erase(st.find({old,freq}));  //remove first instance
     }

     int getMaxFreqNumber(){
         pair<int,int> n= *(st.begin());  //top most is the max frequent
         return n.first;
     }
}

Answer 3

Assuming we have some rules for having multiple max frequent numbers,

 

Deque to track insertion order.
Need hashmap<num, cnt> to track frequency cnt.
Need treemap<cnt, TreeSet of nums> to order frequency groups.

 

add(): insert to back of deque, update treemap by getting the cnt from map and removing from current cnt group. Add to cnt+1 group. Update hashmap.

 

remove(): remove front of deque. Do similar process as add, but opposite.

 

getMaxFreqNumber(): return tail of our treemap, tail of our treeset.

 

O(logn) add, remove, getMaxFreqNumber().