Last Updated: 29 Apr, 2021
TIme-Based Key Value Store
Moderate
Asked in company
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.
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
Approaches
Approach:
- 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’.
- 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.
- 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:
- 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’.
- Create an array ‘KEYTIMESTAMPVAL’ which will store the objects of class ‘DATA’.
- 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’.
- 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’.
- 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.
Approach:
- In this approach, we will construct class ‘DATA’ in which each object of this class will store three things i.e ‘VAL’, and ‘TIMESTAMP’.
- The idea behind this approach is to maintain a hashmap. The hashmap will store the ‘KEY’ and the array in which each entry is an object of class ‘DATA’ at that particular key as an entry in a map.
- Now for each particular ‘TARGETKEY’ and the target ’TARGETTIMESTAMP’, we have to find the value of ‘VAL’ such that its value of ‘TIMESTAMP’ is less than or equal to the ’TARGETTIMESTAMP’. And if there exist multiple values, then we have to consider the largest value of ‘TIMESTAMP’.
- So for this, we will perform a binary search on the array of objects of class ‘DATA’ as pointed by the given value of ‘TARGETKEY’ and find the required value of timestamp.
- In binary search, if the value of ‘TIMESTAMP’ at the middle of the array is equal to the ’TARGETTIMESTAMP’ then return the value of ‘VAL’ which is at the location with the value of ’TARGETTIMESTAMP’ in the array. If the value of ‘TIMESTAMP’ is greater than the value ’TARGETTIMESTAMP’ then reduce the search space from the right by one. Otherwise, increase the search space from left by one.
- If no answer is returned from the above step then return the value of ‘VAL’ which is at the last value of mid calculated from the above operation in the array of objects of class ‘DATA’.
Here is the algorithm:
- Create a class ‘DATA’ with two parameters i.e value which will store the value of input ‘VAL’ and ‘TIME’ which will store the value of input ‘TIMESTAMP’.
- Create a hashmap keyTimestampVal, which will store ‘KEY’ and array of objects of class ‘DATA’ as an entry in a map.
- When the ‘setKey(Key, Val, Timestamp)’ function is called, insert ‘KEY’ as key and value as an object of class ‘DATA’ in our hashmap.
- Now when the ‘getVal(TargetKey, TargetTimestamp)’ function is called, then perform the following steps:
- First, check if the value of the timestamp of the first entry of hashmap at that ‘TARGETKEY’ is greater than the value of ’TARGETTIMESTAMP’ then return -1 as string because it means there does not exist any value of timestamp whose value is less than ’TARGETTIMESTAMP’.
- Now check if the value ’TARGETTIMESTAMP’ is greater than or equal to the value of the timestamp of the last entry of hashmap at that ‘KEY’ then return the value of ‘VAL’ of the last entry in hashmap. This is because it is the largest valid value of ‘VAL’ as per our condition which is our answer.
- Now perform the binary search:
- Take ‘START’= 0 and ‘END’ = size of array for the given input ‘KEY’ - 1.
- Now till ‘START’ < ‘END’ calculate ‘MID’ as (‘START’ + ‘END’)/2.
- If the value at the keyTimestampVal[Key][mid].time is equal to TargetTimestamp then return the value of Val as keyTimestampVal[Key][mid].value.
- If the value at the keyTimestampVal[Key][mid].time is greater than the TargetTimestamp then update end as mid - 1.
- Otherwise, update start as mid + 1.
- Otherwise return keyTimestampVal[Key][mid].value as the value of ‘VAL’.