Question: Sprinklr | 4th October | Online Assessments | JSON Parsing | Tax Payment |
4
Entering edit mode

Solution to Problem 2

Analysis

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).

Implementation

  • We will create a list of values for x for each index which will be required to answer some query. We can use a 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.
  • Now we will iterate through the array maintaining a Fenwick Tree(BIT) / Segment Tree/ C++ PBDS and find the required values by iterating through the list of the current index and using the maintained data structure.
  • Finally, we can answer the queries as we have already computed the values that will be required to answer them in the previous step.

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)

PseudoCode

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])

Remarks

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.

ADD COMMENTlink 2.2 years ago Ayush Gangwani 1.2k
2
Entering edit mode

Solution to Problem 1

Analysis

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:Input Sample as output

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

  • We will create a custom struct for a Tree Node, which will have 3 variables: Value, a string which stores the value corresponding to the key of this node, in case the value is a simple string, Children, a vector which stores pairs of {Children Keys, Corresponding Nodes}, in case the key corresponds to another dictionary instead of a simple string, and a Map to Position map, which maps the string of the children keys to their position in the Children vector. (You can remove the Children Keys part in the vector of pairs, since we just need the Map to Position map to get the corresponding node for a key)
  • We create a root node from the struct made in Point 1, and then iterate over the JSON string given to us. We first check what is the first key, by iterating and seeing when do we get a closing inverted commas ("). As soon as we get the closing inverted commas, we know what the key is, create a new Tree Node for that key and now need to figure out what it's corresponding value is (whether it is a simple string or a dictionary).
  • We can check whether it is a string or a dictionary by checking the next character after the colon, if it is a inverted comma, then it is a simple string, and we can iterate over that string to get the value and store it in our node.
  • In case it is a dictionary, i.e. we get an opening brace {, we can move to the point after the opening brace and repeat the step 2, 3, 4. This can be done by using a recursive function.
  • As soon as we encounter a closing brace, it means that there are no more children of this root, and we can return from this recursive call.

Implementation for Querying

  • Separate all keys in the query. Student.Name = Student, Name
  • Iterate over all the keys in the query and go to the corresponding child recursively.
  • When you get to the last key in the query, its corresponding nodes value will be the answer.

Code for Tree Structure

struct TreeNode
{
    string val = "";
    vector<pair<string, TreeNode*>> children;
    map<string, int> mapping_children;
};
ADD COMMENTlink 2.2 years ago Yash Sahijwani 940

Login before adding your answer.

Similar Posts
Loading Similar Posts