TIme-Based Key Value Store

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
16 upvotes
Asked in company
Flipkart limited

Problem statement

You are given a stream of tuples which constitute three things ‘Key’, ‘Val’, and the ‘Timestamp’.

Your task is to implement the ‘TimeBased’ class having the two functions:

1) The first function is ‘setKey(string Key, string Val, int Timestamp)’, which stores the ‘Key’ and the ‘Val’ along with the ‘Timestamp’.

2) The second function is ‘getValue(string TargetKey, int TargetTimestamp)’, which returns the value of ‘Val’ associated with the ‘TargetKey’ such that its ‘Timestamp’ value is less than or equal to the ‘TargetTimestamp’. If there are multiple values of ‘Val’, return the value of ‘Val’ with the highest value of ‘Timestamp’ among the valid ones. If there is no valid value of ‘Val’ return “-1” as a string.

‘Timestamps’ will always be in strictly increasing order.

Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains an integer ‘N’, representing the total number of queries.

Then the next ‘N’ lines contain ‘N’ queries. A query can be of two types:
1 Key Val Timestamp  → stores the Key and the Val along with the Timestamp
2 TargetKey TargetTimestamp → returns the value of ‘Val’
Output format: 
For each test case, print the value of ‘Val’ for each query of type 2 only, output the answer to the query in a single line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given functions.
Constraints: 
1 <= T <= 10
1 <= N <= 3 * 10^4
1 <= | Val |, | Key | <= 10
1 <= Timestamp <= 10^7

Where ‘T’ represents the number of test cases, ‘N’ represents the number of queries, ‘Val’, ‘Key’ and ‘Timestamp’ are added to the stream.


Time Limit: 1 sec
Sample Input 1:
 2
 4
 1 abc def 10
 1 abc ghi 20
 2 abc 10
 2 abc 5
 3
 1 bbb ccc 5
 1 ddd ccc 5
 2 ddd 6
Sample Output 1:
 def  -1
 ccc
Explanation For sample Input 1:
For the first test case, 
First, “abc” is added as a key and “def” as a value, and 10 as a timestamp. So at this moment, we have a single data, i.e. {“abc”, “def”, 10}. Then again, “abc” is added as a key along with “ghi” as a value and 20 as the timestamp. Now we have two records, i.e. {“abc”, “ghi”, 20} and {“abc”, “def”, 10}. Now query of type 2 is called, and we have to find the value of ‘Val’ such that its key is “abc” and its timestamp value should be less than or equal to the target timestamp ‘TargetTimestamp’ i.e 10. So the output for this query is “def”. Now again, the query of type 2 is called, and we have to find the value of ‘Val’ such that its key is “abc” and its timestamp value should be less than or equal to the target timestamp ‘TargetTimestamp’ i.e 5. So the output for this query is “-1” as there exists no value of timestamp, which is less than or equal to 5. 

For the second test case, 
First, “bbb” is added as a key along with “ccc” as a value and 5 as a timestamp. So at this moment, we have a single data, i.e. {“bbb”, “ccc”, 5}. Then again, the query of type 1 is executed, and “ddd” is added as a key along with “ccc” as value and 5 as a timestamp. Now we have two records, i.e. {“bbb”, “ccc”, 5} and {“ddd”, “ccc”, 5}. Now query of type 2 is called, and we have to find the value of ‘Val’ such that its key is “ddd” and its timestamp value should be less than or equal to target timestamp ‘TargetTimestamp’ i.e 6. So the output for this query is “ccc”.
Sample Input 2:
2
3
1 yyy zzz 3
1 yyy xxx 4
2 yyy 4
4
2 fff 13
1 fff ggg 13
1 fff hhh 14
2 fff 14
Sample Output 2:
xxx
-1 hhh
Explanation For Sample Input 2:
For the first test case, 
First, “yyy” is added as a key and “zzz” as a value, and 3 as a timestamp. So at this moment, we have a single data, i.e. {“yyy”, “zzz”, 3}. Then again, “yyy” is added as a key along with “xxx” as a value and 4 as the timestamp. Now we have two records, i.e. {“yyy”, “zzz”, 3} and {“yyy”, “xxx”, 4}. Now query of type 2 is called, and we have to find the value of ‘yyy’ such that its key is “yyy” and its timestamp value should be less than or equal to the target timestamp ‘TargetTimestamp’ i.e 4. So the output for this query is “xxx”.

For the second test case, 
Initially, no data is present so for query 2, the output will be -1. First, “fff” is added as a key along with “ggg” as a value and 13 as a timestamp. So at this moment, we have a single data, i.e. {“fff”, “ggg”, 13}. Then again, the query of type 1 is executed, and “fff” is added as a key along with “hhh” as value and 14 as a timestamp. Now we have two records, i.e. {“fff”, “ggg”, 13} and {“fff”, “hhh”, 14}. Now query of type 2 is called, and we have to find the value of ‘fff’ such that its key is “fff” and its timestamp value should be less than or equal to target timestamp ‘TargetTimestamp’ i.e 14. So the output for this query is “hhh”.
Hint

Can you try to store the given input in an array and perform a linear search to find the required value of Val?

Approaches (2)
Brute Force

Approach: 

  1. In this approach, we will construct class ‘DATA’ in which each object of this class will store three things i.e ‘KEY’, ‘VAL’, and ‘TIMESTAMP’.
  2. Now whenever ‘setKey(Key, Val, Timestamp)’ is called we will create a new object of class ‘DATA’ to store these three things and insert that object in an array.
  3. Now, whenever ‘getVal(TargetKey, TargetTimestamp)’ is called we will iterate over the array of objects of class ‘DATA’ and find the value of ‘VAL’ for which both key is equal to ‘TARGETKEY’ and its timestamp value should be smaller than or equal to the ‘TARGETTIMESTAMP’. If there are multiple values of  ‘TIMESTAMP’ we will choose the largest value of  ‘TIMESTAMP’ among all the valid ones.

 

Here is the algorithm:

  1. Create a class ‘DATA’ with three parameters i.e keyData which will store the value of input ‘KEY’, ‘VALUE’ which will store the value of input ‘VAL’ and ‘TIME’ which will store the value of input  ‘TIMESTAMP’.
  2. Create an array ‘KEYTIMESTAMPVAL’ which will store the objects of class ‘DATA’.
  3. Now whenever ‘setKey(Key, Val, Timestamp)’ is called we will create a new object of class ‘DATA’ to store these three things and insert that object in the array ‘KEYTIMESTAMPVAL’.
  4. Now Now, whenever ‘getVal(TargetKey, TargetTimestamp)’ is called we will iterate over the array of objects of class ‘DATA’ and perform the following steps:
    • Create a variable index initialized to -1 to store the value of location at which we will find the required value of ‘VAL’.
    • Now iterate through the array ‘KEYTIMESTAMPVAL’ and find the location where both ‘TARGETKEY’ = ‘KEYTIMESTAMPVAL[i].KEYDATA’ and ‘TARGETTIMESTAMP’ = ‘KEYTIMESTAMPVAL[i].TIME’. If so we will update the value of index with ‘i’.
  5. Now if the value of the index is not equal to -1 then we will return the value of ‘VAL’ present at the location index in the array. Otherwise, we will return -1 as a string.
Time Complexity

O(N^2), where ‘N’ is the total number of queries.

 

Since there are N queries so when the ‘setKey()’ function is called, then insertion operation takes O(1) time per query which takes a total of O(N) time, and when the ‘getVal()’ function is called, then linear search takes O(N) time per query which in takes a total of O(N^2) time. So overall time complexity will be O(N^2).

Space Complexity

O(N), where ‘N’ is the total number of queries.

 

The array keyTimestampVal is created which uses O(N) space. So overall space complexity will be O(N). 

Code Solution
(100% EXP penalty)
TIme-Based Key Value Store
Full screen
Console