Frequency Queries Solution

carlosbf
carlosbf
Sep 1, 2018 · 2 min read

This is one of the medium difficulty problems in the Dictionaries and Hashmaps section of hackerrank’s interview preparation kit problem set. Link here.

The problem states that you are given a list of queries of three types to be executed on a data structure you maintain.

Query type 1 is an insertion query it will insert a value into the data structure.

Query type 2 removes exactly one occurrence of a value in your data structure only if it has previously been inserted.

Query type 3 will print 1 if there is at least a value in the data structure that appears k times.

You have to implement this functionality, execute all queries and return the results of queries of type 3.

Solution

To be able to execute each of our queries in constant time we will need a way to count the occurrences of the values inserted or removed in the queries and keep track of how many values appear with k frequency in the data structure all in constant time.

This can be done using two hash-maps, one to keep track of the frequency of each value inserted and another one to keep track of the number of values with a specific frequency in the data structure.

This way when there is an insertion or deletion we update both maps and when we need to produce the number of elements with k frequency we just look up k in the hash-map keeping track of this data. We only want to be extra careful in the implementation and not removing items when they have not been inserted previously.

Code

SOLUTION ON GITHUB (Formatted)CLICK HERE

vector<int> freqQuery(vector<vector<int>> queries) {

int q;
int type;
int current_count;
vector<int> query;
vector<int> query_results;
unordered_map<long, int> count_map;
unordered_map<int, long> frequency_map;

q = queries.size();

for(int i =0 ; i < q ;i++){
query = queries[ i ];
type = query[0];
switch(type){
case 1:
frequency_map[count_map[ query[1] ]]--;
count_map[ query[1] ]++;
frequency_map[count_map[ query[1] ]]++;
break;
case 2:
current_count = count_map[ query[1] ];
if(current_count > 0){
frequency_map[current_count]--;
count_map[ query[1] ]--;
frequency_map[count_map[ query[1] ]]++;
}
break;
case 3:
query_results.push_back(( frequency_map[query[1]] > 0 )? 1:0);
break;
default:
break;
}

}
return query_results;
}

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade