Question

Flipkart | SDE | Coding OA Questions and Solutions | Set - 6

Answer 1

Design a data structure to give top 10 stocks from a stream of tuple at any point of time.
tuple (id, stock-price)
Basically, getTop10() should be returning a list of top 10 stocks having maximum value at any point of time.

 

For example,
Stream -->>(a, 10), (b,20), (c,30) (d, 40) (a, 30) (d,10)

 

getTop2() returns [{a,30}, (c,30)];

Comments

This can be solved using min heap. Suppose we made a heap of K elements. Now new element is X. If X > top element of heap, remove top element and insert X in heap

---

int main()
{
    vector<pair<char,int> > items = { {'a', 10}, {'b',20}, {'c',30}, {'d', 40}, {'a', 30},{'d',10} };
    set< pair<int,char> > s;
    map<char,int> mp;
    for(auto e:items)
    {
        if(mp.find(e.first)==mp.end())
        {
            s.insert({e.second,e.first});
            mp[e.first] = e.second;
        }
        
        else
        {
            s.erase({mp[e.first],e.first});
            mp[e.first] = e.second;
            s.insert({mp[e.first],e.first});
        }
        
    }
    int k = 2;
    for(auto it=s.rbegin();it!=s.rend()&&k;it++)
    {
        cout<<it->second<<"-"<<it->first<<"\n";
        k--;
    }
    
    return 0;
                                     
}```
//Output
//c-30
//a-30