There are two standard ways to solve this problem. One of them answers the queries online (as in if we don't have access to all the queries and we should answer a query to access the next query) and the other answers the queries offline (as in we have access to all the queries beforehand and we can answer the queries in a random order).
Online method : The online method uses a data structure called the merge sort tree. It can answer similar queries efficiently in a complexity of O(NlogN + Qlog^2N)
. It is however very tough to implement such a structure in a short amount of time and hence this method is not recommended.
Offline method : Since we are given the vector containing the queries beforehand, we can use offline method of answering the queries.
If we want to find the employees having salary greater than x in a range [l,r], we can find out the number of employees having salary greater than x in the range [1,r] and subtract the number of employees having salary greater than x in the range [1,l-1]. In this way we can split the original query into two symmetric queries which can be answered easily as explained below.
For each index i, we will maintain a list of values of x such that the information about the number of employees having salary greater than x in the range [1,i] can help answer an original query. Once we have precomputed this list for each index, we can iterate through the array and find the required values for all the indices in one go using a Fenwick Tree(BIT) / Segment Tree / Ordered Set (C++ specific Policy Based Data Structure).
vector<map<int,int>>
for this. Now we will populate the lists for all indices by iterating through the queries and appending the value of x for this query in the lists of both l-1 and r for this query.Since, we only request two values for each query, thus the no of values of x aggregated over all the indices will be 2Q and hence the time complexity is O(QlogN)
Filter(N,A,Queries):
vector<map<int,int>> list_x(N) //creating the list for storing the values of x for each position
for query in Queries: //populating the lists for all indices
list_x[query.l-1][query.x] = -1 //creating an entry in the hashmap for index l-1
list_x[query.r][query.x] = -1 //creating an entry in the hashmap for index r
ordered_set<int> tree //using the C++ built in PBDS, you can also use BIT/Segment tree
for i from 1 to N:
tree.insert(A[i][1]) //Inserting the current value into the tree
for x in list_x[i].keys(): // Finding the required values by iterating through the hashmap for this index
list_x[i][x] = tree.size() - tree.order_of_key(x) // One can use similar methods in BIT/Segment tree through coordinate compression and similar techniques
for query in Queries: // answering the queries as we now have all the information required to answer them.
print(list_x[query.r][x] - list_x[query.l-1][x])
We can also use techniques like MO's algorithm and Square root decomposition to answer the queries offline. But the method explained in this post is the easiest to implement in a short amount of time especially if you code in C++. Java/Python users might need to code a BIT/Segment tree but its still better than MO's both in terms of time complexity and the time required to implement.
The input consists of JSON strings and each query is a key of the JSON object represented by the string. Each dictionary in the JSON can be viewed as a tree. The input sample visualized as a tree is shown below:
Here we can see that the JSON dictionary is a tree, with the keys being nodes. If they key corresponds to a value which is just a string, we can store it directly in the node, but if the key has a value which is itself a dictionary consisting of keys (concept of nested dictionaries), then each of the keys of this sub-dictionary act as nodes which are children of the key. Hence we can form a tree from a JSON dictionary.
Then searching for a query is a simple traversal in the tree, by looking at the keys in the query. By all keys, I mean keys which are separated by a dot.
Implementation for Tree Formation
Implementation for Querying
struct TreeNode
{
string val = "";
vector<pair<string, TreeNode*>> children;
map<string, int> mapping_children;
};