Atlassian first round - rejected
Anonymous User
1818
AtlassianInterview

Asked to implement following class:

//implement class to return most popular content ID
class MostPopular {
    void increasePopularity(int contentId);
    int mostPopular();
    void decreasePopularity(int contentId);
}

I wrote following solution:
Basically maintaining id_to_popularity and popularity_to_id maps. As there can be multiple IDs with same popularity so value for pop_to_id map is a vector of int. Best case all the 3 functions are o(1).

Code compiled and produced correct output. Don't know why I was rejected.

#include<iostream>
#include<vector>
#include<unordered_map>
#include<set>

using namespace std;

//implement class to return most popular content ID
class MostPopular {
    unordered_map<int, int> id_to_pop;
    unordered_map<int, set<int>> pop_to_id;
    int max_pop;
public:
    MostPopular() {
        max_pop = INT_MIN;
    }
    void increasePopularity(int contentId);

    int mostPopular();

    void decreasePopularity(int contentId);
};

void MostPopular::increasePopularity(int contentId) {

    if (id_to_pop.find(contentId) == id_to_pop.end()) {
        id_to_pop[contentId] = 1;
        pop_to_id[1].insert(contentId);
        //update max_pop
        if (max_pop < 1) {
            max_pop = 1;
        }
    } else {
        int initial_pop = id_to_pop[contentId];
        id_to_pop[contentId]++;
        auto collection = pop_to_id[initial_pop];
        collection.erase(contentId);
        
        auto new_collection = pop_to_id[initial_pop+1];
        new_collection.insert(contentId);
        pop_to_id[initial_pop+1] = new_collection;
        if (max_pop < initial_pop+1) {
            max_pop = initial_pop+1;
        }
    }
}

int MostPopular::mostPopular() {
    int ret = max_pop <= 0? -1: max_pop;
    int ret_id = -1;
    auto collection = pop_to_id[ret];
    cout<<"New call to mostPopular"<<endl;
    /*for(auto i = collection.begin(); i != collection.end(); i++) {
        ret_id = *i;
        cout<<*i<<endl;
    }*/
    //cout<<ret<<endl;
    return ret;
}

void MostPopular::decreasePopularity(int contentId) {
    if (id_to_pop.find(contentId) == id_to_pop.end()) {
        id_to_pop[contentId] = -1;
        pop_to_id[-1].insert(contentId);
        //update max_pop
        if (max_pop < -1) {
            max_pop = -1;
        }
    } else {
        int initial_pop = id_to_pop[contentId];
        id_to_pop[contentId]--;
        auto collection = pop_to_id[initial_pop];
        collection.erase(contentId);
        
        auto new_collection = pop_to_id[initial_pop-1];
        new_collection.insert(contentId);
        
        if (collection.size() == 0 && max_pop == initial_pop) {
            max_pop = initial_pop-1;
        }
    }
}
//id->pop unordered_map<int, int>
//pop->id unordered_map<int, vector<int>> //vector<int> which is a heap

int main() {
    //cout<<"Hello World!";
    //return 0;
    MostPopular popularityTracker;    
    popularityTracker.increasePopularity(7);

  popularityTracker.increasePopularity(7);

  popularityTracker.increasePopularity(8);

  popularityTracker.mostPopular();        // returns 7

  popularityTracker.increasePopularity(8);

  popularityTracker.increasePopularity(8);

  popularityTracker.mostPopular();        // returns 8

  popularityTracker.decreasePopularity(8);

  popularityTracker.decreasePopularity(8);

  popularityTracker.mostPopular();        // returns 7

  popularityTracker.decreasePopularity(7);

  popularityTracker.decreasePopularity(7);

  popularityTracker.decreasePopularity(8);
  popularityTracker.mostPopular();
    
}
Comments (6)