Queries on Strings list

This approach is straightforward, we will make a HashMap where the key will be the strings given in queries and the value will be their current frequency.  We can process queries of types 1 and 2 in O(1) times by simply increasing and decreasing the value of the string ‘KEY’ given in the Add or Remove query. 

For queries of type 3 and 4, we need to iterate over the HashMap in order to find the lexicographically smallest string with the highest and lowest frequency respectively.

Algorithm

1. Create an empty HashMap and let it be named  ‘FREQ’.
2. Create an empty string list/array ‘RESULT’.
3. Iterate over the queries and do the following -:
   • If the query is of type-1 (Add ‘KEY’), then if ‘KEY’ is not present in ‘FREQ’, insert it with value ‘1’ otherwise,  increment its value by ‘1’.
   • If the query is of type-2 (Rem ‘KEY’), then if the value for key ‘KEY’ in  FREQ’ is 1, then remove this key, otherwise,  decrement its value by ‘1’.
   • If the query is of type-3 (GetMaxKey), then do the following -:.
     • Initialize an integer variable ‘MAXFREQ’: = 0, and create an empty string ANS.
     • Iterate over the HashMap ‘FREQ’, and for each (key, value) pair, if the value is greater than ‘MAXFREQ’ then assign the key to ‘ANS’ and value to ‘MAXFREQ’, If the value is equal to ‘MAXFREQ’ then assign the key to ‘ANS’ if the key is lexicographically smaller than ‘ANS’
     • Append ‘ANS’ in the ‘RESULT’.
   • If the query is of type-4 (GetMixKey), then do the following -:.
     • Initialize an integer variable ‘MINFREQ’: = INF, and create an empty string ANS.
     • Iterate over the HashMap ‘FREQ’, and for each (key, value) pair, if the value is smaller than ‘MINFREQ’ then assign the key to ‘ANS’ and value to ‘MINFREQ’, If the value is equal to ‘MINFREQ’ then assign the key to ‘ANS’ if the key is lexicographically smaller than ‘ANS’
     • Append ‘ANS’ in the ‘RESULT’.
4. Return ‘RESULT’.

In this approach for processing the query of types 1 and 2, we will keep a HashMap like the previous approach, where the key will be the strings given in queries and the value will be their current frequency.  We can then process queries of type 1 and 2  by simply increasing and decreasing the value of the string ‘KEY’ given in the Add or Rem query. 

For queries of type 3 and 4, we need a data structure called buckets. Here, each bucket will have a Self-Balanced Binary Search tree (Set of strings in C++ or TreeSet of strings in Java), and a pointer ‘PREV’ and ‘NEXT’ to the previous and next non-empty bucket. We create an array of buckets of size ‘N + 1’ and let it be named ‘BUCKETS’.  All the strings having frequency ‘X’ will be stored in the Set (Self-Balanced Binary Search tree) of  ‘BUCKETS[X]’. We also keep two pointers ‘HEAD’ and ‘TAIL’ at the non-empty bucket with lowest and highest index respectively.

Now when we perform type-1 query i.e (Add ‘KEY’), and if the frequency of ‘KEY’ after this becomes ‘X’,  then we remove it from ’BUCKETS[X - 1]’ and add it to ‘BUCKETS[X]’. Then we may need to update  ‘PREV’, ‘NEXT’ pointers of both buckets and  ‘HEAD’, ‘TAIL’ pointers accordingly.

Similarly when we perform type-2 query i.e (Rem ‘KEY’), and if the frequency of ‘KEY’ after this becomes ‘X’,  then we remove it from ’BUCKETS[X]’ and add it to ‘BUCKETS[X - 1]’. Then we may need to update ‘PREV’, ‘NEXT’ pointers of both buckets and  ‘HEAD’, ‘TAIL’ pointers accordingly.

As each bucket stores strings in a set of strings based on the Self-Balanced Binary Search tree,  then we can find lexicographically smallest strings with the highest and lowest frequency, by simply finding the start elements of a set of buckets pointed by ‘TAIL’ and ‘HEAD’ pointers respectively.

Algorithm

1. Create an empty HashMap and let it be named  ‘FREQ’.
2. Create an empty string list/array ‘RESULT’.
3. Create a list/array of bucket BUCKETS of size ‘N’+1. Initially each bucket should have ‘PREV’ = 0, ‘NEXT’ = 0, and empty Set of strings (self-balanced-BST ) ‘STRSET'.
4. Initialize two pointers ‘HEAD’:= 0, ‘TAIL’:= 0.
5. Iterate over the queries and do the following -:
   • If the query is of type-1 (Add ‘KEY’), then do the following -:
     • if ‘KEY’ is not present in ‘FREQ’, insert it with the value ‘1’ otherwise,  increment its value by ‘1’.
     • Let ‘X: = FREQ[‘KEY’].
     • Insert ‘KEY’ in BUCKET[X].STRSET.
     • If X > 1, then erase ‘KEY’ from BUCKET[X-1].STRSET.
     • Now we will update pointers as follows -:
     • If the list/array is empty before this query i.e ‘HEAD’:= 0 and ‘TAIL’:= 0 ,  do ‘HEAD’:=1, ‘TAIL’:=1.
     • Otherwise, If BUCKETS[X].PREV != 0 OR  BUCKETS[X].NEXT != 0,  then do nothing as pointers are already set correctly.
     • Otherwise, If X < HEAD,  then do BUCKET[X].NEXT = ‘HEAD’ and ‘HEAD’:= ‘X’  because X’ is now the smallest index of the non-empty bucket.
     • Otherwise, do BUCKETS[X].next = BUCKETS[X-1].next, BUCKETS[X].prev = X-1, TAIL = max(TAIL, X).
     • Otherwise, there can be two possible cases (i) BUCKETS[X-1].STRSET is not empty, in this case we simply do BUCKETS[X-1].NEXT:= ‘X’,  (ii) BUCKETS[X-1].STRSET is empty, in this case we erase BUCKETS[X-1] by setting pointers correctly.
   • If the query is of type-2 (Rem ‘KEY’), then if the value for key ‘KEY’ in  FREQ’ is 1, then remove this key, otherwise,  decrement its value by ‘1’.   After that we have to update BUCKETS and pointers, we can do it in a way similar to the type-1 query.
   • If the query is of type-3 (GetMaxKey), then append the first (lexicographically smallest) string of BUCKETS[TAIL].STRSET in ‘RESULT’.
   • If the query is of type-4 (GetMixKey), then append the first (lexicographically smallest) string of BUCKETS[HEAD].STRSET in ‘RESULT’.
6. Return ‘RESULT’.