Time-based KV Store in Go (Interview Question)

I recently got a question in an interview asking me to implement a time-based key value store it's a really interesting problem but I actually think it's something that we can put a spin on to make it even more interesting in more thoughtful around data structure and algorithm uh Concepts so the original question breaks down to the idea where we're asked to build a new structure called a Time map and this structure should have two methods attached to it one should be set which takes a key and a value and then a time stamp that we put in and adds to the map of course and then the get which actually goes in and gives takes a key and a timestamp and then effectively returns a valid value based on that now if you look at the base case inside of the lead code example what they want you to do if there's multiple such values that meet less than or equal to that time stamp it wants you to return the value associated with the largest timestamp available but still hitting that condition of being less than or equal to so I I'm not going to spend a ton of time talking about the solution here because there's a bunch of videos and it's on leeco so of course there's a million different solutions that you can look up but suffice to say that typically what happens is you end up with a map implementation with o of one and then a get implementation with something around log of n unless you're doing something tricky where effectively with the time stamp search you're doing a binary search because we assume that when setting records they're put into order so a visualization of kind of this implementation inside of you know the leak code example is that typically you'll have a higher level map you'll add something like dog dog will effectively be a pointer or referencing a array behind the scenes that array will slowly put in noises for the value under dog and if we go to search again you can imagine the binary search so if we search for the time stamp of 2.5 right the first higher than 2.5 value is Hal so the first lower than 2.5 value is Wolf so you could imagine if you've ever done on binary search how you could kind of slice that up and find that value easily now one of the complexities with the setting of course is that when we add new keys we need to do some kind of initialization work to ensure that you know in the case of cat if a brand new array needs to be established it can be established and then those values can be inserted into it and then it's just business as usual just like we see here in in case one so you can dig a little bit more into this and check out the lead code problem again that's 981 if you want to check it out but we're going to spend our time together looking at an enhanced version of this problem and how you might solve it all right so in the enhanced version of this problem we're going to be making a couple different changes first off when we Implement set it's no longer going to take a time stamp this is simply going to be calculated at the time of the call then the time Precision that we use when we make the implementation is going to be at a Precision level of a nanosecond get is going to now start accepting timestamp optionally now when get receives no time stamp the implication is that we're going to return the latest key uh or I guess value for that key so if in the case of this example dog was called how should be the last thing that is effectively returned and then if get does receive a timestamp what we're going to do this time is we're going to do an exact match for that specific item so if dog came in and we asked for three we should get Hal coming back to us all right and then finally we're going to implement a third function which is actually just the same real logic from the previous example or exercise which is to do a get before and get before we'll take a string it will take a time stamp and it will effectively return all the elements that are before or equal to that time stamp so things still get set in order obviously because insort is going to put the time stamp in when it does the insert but this is effectively going to give us a list back rather than a single item and some key things that we're going to consider here before we get into the design itself is that we're going to attempt to keep the complexity as low as possible we're going to try to stay constant time for all of the get operations the get before operation is still going to be something that is going to be log of n but set and get are going to stay as close to constant as possible all right so let's talk a little bit about what the solution to this data structure might look like so I'll just zoom in one here so we know we still need to implement a Time map at the highest level and time amp is something that's going to hold a bunch of keys now we're going to do this time is rather than having that key go right down to an array of values we're going to implement a new type of structure called a Time store and time store is actually going to have two structures attached to it so if you kind of follow it down to values so time store and its reference to values values is kind of like what we had in this original problem where there's going to be an array or in ghost case a slice of values and we're going to have the ability to search through these should we need to like in the case of get before now time index is going to be a map that holds pointers to those values now what we're doing with this map is we're going to be able to facilitate that get command at a constant time because what will happen is upon each insertion We'll add a key to this map with that insertion timestamp and ensure that there's a pointer going down to the value in the array and you'll notice here that these are kind of out of order and that is potentially expected because Maps don't have a guaranteed order so whatever order they're in we're just going to have a constant time look up and as long as we can resolve the appropriate timestamp we're going to end up with the correct value so with this structure in mind times map pointing to a Time store which holds a Time index in a value array let's look at how we might code this inside of go starting off implementing the data structure will first set up what a value is going to be so this will be a type value which is a struct the first field is going to be the stamp which is the time stamp and then lastly will be value or string which could be any object but we're just going to hold a string value in there for now additionally we have the Time store struct as a reminder times store is going to be the holder of both an array of those values along with this time index construct so inside of time store we'll start with the time index now the interesting thing about time index is that the key is actually going to be a structured type it's going to be from the standard Library time dot time and then the value is going to be a pointer to one of these underlying values all right now the actual values themselves are a slice of values and then we can end this here with the Time store struct now we have the higher level Time map struct and this is going to just be a map of strings this will be Keys like dog and cat and this will hold a pointer to each instance of that time store and this is largely our data structure that we need to set up so a key thing to keep in mind is that this time store construct that is kind of the holder of both the value array and the overlaying index is going to have a unique time store for every type of key so dog cat and so on next we're going to implement a Constructor and two convenience functions so starting off with the Constructor it'll be a pretty standard Constructor in go this is going to be a new function that returns a Time map the actual return is quite simple so we're just going to directly return a new instance of a Time map and for the key we're going to set times equal to an initialized map where the key is a string and the value is a pointer to a Time store so again this will be cat pointing to the Time store for cat we'll end that and now we have our Constructor for Time map now a couple more conveniences that we want to put in place we want to also have a internal Constructor for the Time store itself we'll of course call this when a new key comes in and we need to initialize a new time store for that key so similar to the new for Time map this will just return the Time store it's going to have the time index initialized which is that map of times where it points to the value and the underlying value array as well that we are going to be able to search through when we need to find things that based on timestamps come before something well and that and now we've got our Constructor for the new time store and then last but not least we've got the actual get time store function now this will be quite critical in our get calls because we need to see if a key exists and there's Associated time store if there is we want to return that time store so we can actually do lookups otherwise we'll return an error so what we'll do with go is we'll start with the notation where we check to see if the key exists and if it does exist we'll store it in the TS variable then if we've got that it's a good case we just need to return the Time store in a nil variable to the caller we'll close that out and then at the very end here if we don't pass that we know that the key did not exist so we're going to return a nil value for the Time store and then an error letting the caller know that key did not exist we'll close that out and these are our Constructors and helper functions for this data structure with the constructors and helpers created we're now ready to do get set and get range now from a Time complexity standpoint again we want to focus on all cases of get being o of constant time set the same and then get range we're still going to accept the log n from the binary search so let's start off with actually setting values inside of the map to start this off we're going to declare the set signature this is going to be attach the time map object and it is going to accept a key that also will accept data and both of these will effectively be a string then we're going to check if that time store exists this is the key thing if the actual key is in there and if there's a Time store associated with it we're ready to just insert into that existing value array so if that is the case ready to insert we'll establish a new Time by getting the current time we'll then go and establish the value where the first field stamp is that time stamp we just captured the value is the data passed in as an argument and then we're going to look at the time store values which is that array or slice of values and we're going to append that to the existing time store values with that new value we just created so now the list is filled up but remember if we look back at our diagram as we're adding things into the list we also need to be sure that we're maintaining this time index which has the map pointing into that element in the list so if we go back here we can now access the time index by saying timestore.time index at stamp this is going to be equal to that value and just keep in mind that this value is a pointer it is not a copy so we're going to ensure that they're looking at the same memory address and then if all goes well we're just going to return which might feel a little obscure right now but I'll show you why this is helpful we'll close out the if and this effectively becomes our base case for this algorithm now if we get out of the if that means that the key did not exist in which case we're best off going ahead and doing a new time store right here and this new time store will set that to the key now what's interesting here is we're then just going to recursively call set because now that we've got the Time store associated with that key we're actually ready to just hit this base case and do the actual insertion so we'll do the recursive call and end the function and this is all of the logic we need to do for set jumping back to Maine this would be a good time to test and ensure that set is working as expected so what we're expecting here is that as we add keys in we get a new time store we want to make sure that values are filled up and that the time index is pointing to the appropriate underlying value inside of main what we'll do here is start off by creating a map of keys with values that are effectively array and in this case we have dog we have cat you can see the different sounds that these make and this will be our sample data KVs now building off of KVs we're going to create that new instance using our Constructor of Time map we'll refer to this as TM going forward and then what we want to do here is we want to Loop through KVs so effectively for each animal and for each animal key and for each sound array we'll go ahead and bring these through and then we want to loop again and in this case we don't care about the index inside of here we just care about the specific sound and we'll range through the sounds so what we'll do is we will do a set inside of our map for each animal and each one of its sounds and then we will close this out and now we've got theoretically a Time map that is all set up and good to go now a tool I like to use when I'm setting up algorithms especially with data structures like this is I like to you spew and you can find spew at this GitHub address just with a quick go get you can get it in any of your projects but with spew I use it because it prints out and kind of traverses a data structure even follow pointers dereference them and really help me understand what I've built and whether it's working as I expect so with all of this said I'm going to save the file we're going to go over to a new terminal window and let's do a go run of main.go and see what we get back now we're getting a lot of different output here and what we'll go ahead and do to examine this output is maybe just put it through neovim for a moment and I'll say set no wrap there we go that'll make it a little bit easier for us to read now it's not stylized or colored so a little hard to read but bear with me here we know that the times map existed we can see that it has a length of two so dogs and cats inside of time index we effectively have all of the different cat sounds right here and then the values for those cat sounds so this is the value array as a reminder that's here and then the actual map now one thing that's probably worth checking is to make sure that the values are pointing to the same memory address as the map so let's take a quick look at Screech as our as our example so Screech is at the timestamp of 60431 and you'll notice here if we go to kind of the end of Screech that it's memory address at the very far right is the zero X ending in 8 5 10. so that's 8 5 10 for Screech now let's go back down to the values array and find Screech again and we'll see that time stamp at 60431 and we'll see the address is 8 5 10. so effectively while they are being referenced in two different data structures we do know that it is the same underlying value in memory that is being pointed to and will be accessed regardless of how we get to it speaking of getting to it now let's talk about implementing the get functionality as a reminder on get we want get to be able to receive no time stamp and return the latest value for that key or to receive a time stamp and send the single element back that matches that exact value so to set up our signature here we know that we're going to have this attached to the time map it's going to be called get we're going to accept the key string and we're going to use variatic functions here that's what the three dots are to accept technically a list of times now why I'm using this is in that list it actually can be zero or no elements all the way to multiple elements now we'd want to think a little bit about our API signature and documentation for instructing users on how to use this but this is actually inherently going to make things work in an optional manner for stamp now once stamp finds a value assuming it does it will return a pointer to that in an error the last thing I'll say on this value pointer is it does enable the people getting the value to potentially mutate it we're not going to worry about that concern for this exercise but potential usually sending back a copy could be better depending on what you're trying to do so first thing we're going to do is try to get the Time store for that key or get an error out and if it is an error we'll just return the error back and end execution of this function right here now let's assume we did get a Time store back or in other words the key does exist with that being the case we now need to figure out did the user provide a time stamp now if the user did not or in other words because again stamp is going to come in as an argument that will be featured as an array so if it's less than one or the user did not specify that what we want to do to achieve o of one is actually go in through the values array and release the or not release but return the last element inside of it because as long as it's sequential which is part of the constraints it is going to always be the latest so what we'll do is we will return the time series values or sorry the time stores values at the very last element and return nil for an error so this is a very simple case when no stamp is put in place but what if a stamp is put in place well if a stamp is put in place we know we actually want to access through the time index because we want that constant time of looking up the timestamp and then grabbing a value so again we're going to just grab the first stamp value in the array this is again a bit tricky for API callers because they technically could put in multiple stamps then we need to think about how to handle it but in this case assuming a list of stamps or some amount of stamps were provided as arguments we're just going to grab the first one then we're going to grab the time index and try to look up that time stamp and see if it exists in the key so this is both capturing that value and also seeing if it did find a key well then if we find a key simply return that value in a nil error now if we did get this far and did not find the key that's a problem because we had the key inside of here but we did not find a correlated timestamp so we're once again going to return nil for the value and we're going to provide an error back to the caller so effectively this is our git our get sorry not get but get Logic for both getting when a timestamp is provided and when it is not provided okay so now we're back inside of Main and we can test out get first we'll capture sound for the latest value that was added to dog this should be the latest because there is no time stamp inserted if an error is returned we will Panic then we'll just print out sound and see if that works in the case of dog the last sound inserted was whimper so we should get that returned next up we will iterate through our map of times and grab the or I guess the map for dog under time index and actually just capture all the time stamps we know about so we're kind of doing some trickery here since we have access to the underlying data structures we're just going to capture them all so in each case we will do dog for each stamp and we will capture the noise if it's Error which it shouldn't be we will panic but we'll go ahead and print out this kind of pretty printed way of saying for this stamp I correlated to this noise and that will just guarantee us that our lookup is working for the get operation so now we've got this in place under four and we should be good to test this out back in the terminal let's try running this so we'll do go Main and we have imported but not used spew so we'll fix that real quick because I did get rid of the spew command to make the output a little bit cleaner for this example all right and now we can see the first print that has no metadata around it which is whimper that's exactly what we would expect here and then we can see the insertions and the time stamps for each value now I don't exactly know without doing the dump what the correlated insertions were but here's one way that we could kind of validate it so if we go back to our sample data let's take a look at Wolf and bark we know that they should be the two newest items we're actually better off let's do wolf and whimper so this should be the newest this should be the latest so for Wolf if we look that up we can see that the time stamp is clocked at 91553398 and if I look up at the three digit here it looks like this is in fact the first one inside of that time stamp so this is the right time for Wolf for sure and then if we look at whimper we can see that it's nine seven one five five five three five seven and if we start at the five digit we know there's a couple five digits but then if we look at the three digit here you can see that the three digit does not have anything higher than it there's a four seven here there's a five two there's a five zero but five three is the latest in nanoseconds and whimper is in fact the last element inside of here so overall I would say get seems to be working as we would expect last up is our implementation of get before it's the most complicated but still not that bad get before is going to accept a key it's going to accept a time stamp and it's going to return any elements in the list that are less than or equal to the timestamp that's passed in so let's visualize this with our graphic for a moment pretend wolf is at timestamp zero bark is at timestamp one and how is that time stamp two now I know these are indexes but just pretend they're time stamps for a moment let's pretend that you inserted a timestamp search at 1.5 so clearly 1.5 is less than bark or sorry it's greater than Mark and less than how so what we basically want to do here is we want to identify that first greater than element which will be how and if we can find the index of how we'll then know since these are sequential that everything that comes before Hal should be returned as part of get before jumping back to our implementation let's look at what this might look like and go so we're going to attach get before to the time map nothing new here it will accept key and it will require a time stamp this time so that will be part of the arguments the return is going to be a list or a slice of pointers to values same consideration might not be that smart to be sending pointers to Value back but we'll just keep it as is for now and then a error if something goes wrong so first thing we need to do does the key even exist if it does not exist we will just return the error to the caller in a nil set of values now if it does exist we now need to do the lookup and search so what we're going to focus on here is using sort.search sort.search is going to accept the length or size of the slice that we want to search through so this will just be TS values and then it will allow us to implement a condition for which it will be true now what do I mean by condition for which it will be true well let's look at search inside of the standard library for a moment what's interesting about search is it's going to do a binary search and what it does is it's actually going to return the smallest index it finds that matches the condition we specify so this correlates directly to this example where in the case of inserting 1.5 here we know that if we insert 1.5 Powell at 2 is going to be the first or lowest indexed element that matches that condition let's pretend for a moment again zero one and two let's pretend for a moment that you insert 0.5 okay technically bark at one and howl at two are greater than 0.5 but search will return the smallest index so it would return bark as part of 0.5 and then everything to the left of that if we knew Bark's index could be returned as part of the result that is basically what we want here so we will head back in our code to where we were implementing search and what I'm basically doing here is I'm putting the condition in for this function so let's take just a quick look at what's happening here so as an argument function I int I is going to be the currently evaluated index so we just look in our array and pass in I and then we can look inside of I for the stamp and since this is a time.time object there is the after method that we can call and provide it the argument so we're comparing stamp in the currently evaluated data structure element with the stamp that was passed in as an argument to get before and once again if we can identify the index because there's a match of the lowest index that is after we will get the index and be able to return all the things before so let's assume for a moment that we do find that and the return call just looks something like this which is a little bit clever but you know still understandable so the idea here is that if we look at the TS values it's going to return from the start of the array all the way to the index and now this index value is non-inclusive so let's pretend for a moment we have index 0 1 and 2. let's pretend for a moment that it returns index two okay so for how meaning that you know we're at that 1.5 condition we want to release or return these two so in this case we now know that the index is going to or the expression is going to evaluate to zero and then go all the way to 2. now since 2 is not inclusive this actually means that what's going to be returned is 0 and 1. if everything in the array for example was before this kind of always tricks me with go is it's actually going to evaluate like this and you would think oh my gosh and index out of bounds right but again it's not inclusive so you're actually going to get 0 1 and 2 returned in this result set and then of course if it finds that the first element in the array Let's Pretend wolf is actually after the timestamp that's provided nothing should be returned in that case so this is going to evaluate as 0 0 and then your results set is effectively empty all right so we'll back up here and go ahead and put this together and I'll highlight it here this is the end State I guess it's a little too much to highlight This is the End state of our get before function and it is going to to do exactly what we'd want so let's test that out as a final step all right back inside of the main function let's do one final test for get before so get before is a little tricky to test two we'll start off by getting a slice of times and we'll collect those slices by looking inside of the dog key for its list of values if we iterate through every item inside of dog we can capture the collected stamps and add them inside of here that we can then use for searching you might notice that I actually had to access values and not time index because time index doesn't have a guaranteed order it's it's a map so by going through the values I actually know that the indexes I'm collecting for collected stamps correlate in order to the time stamp so it will once again be chronological okay now inside of here I'm going to instantiate something called before time and this is going to use time dot parse where this is actually just a parsing argument for formatting and I'm giving it the argument of 2007 so this will evaluate to January 1st 2007 which should be way before any of these map insertions happened which should give me an empty slice back we will then just print that out to be super clear and then we're going to capture in the variable all before using the get before method we just implemented dog and the Before Time argument so again this should empty this should be totally empty when it returns all right and then if that error is nil we'll just go ahead and panic and we will dump out the full result set right here okay so we're going to jump back to the terminal and run this in Main and we can see here some of our old output but namely you'll notice that when searching for 2007 January 1st we get a completely empty result set of values back now that that's great but let's make sure we can get values back with a more appropriate date and that's why we collected these collected stamps right here so what we'll do is we'll uncomment out this indexed try and we will get rid of the before time and I am going to pass in as an argument collected stamps with index to try right here so collected stamps index to try all right and now we should be asking for the thing at timestamp 2 or the collected stamp to now if we go back up to dogs 0 1 2 is PSI so we're going to insert the timestamp associated with PSI when the search happens if all goes well this should realize that growl is the lowest index after that time stamp and we should effectively get wolf bark and PSY all returned to our client call heading back to our terminal we will run this again and now we can see that we are searching before so we'll look at this is 538 508 right so 53 8508 so we do know that we searched for PSI right here so that's good so 53 508 53 508 and then inside of here we got wolf bark and PSY omitting our whimper and omitting our growl which came after that inside of the sample data that we put in so get before is also working exactly as we expect so wrapping this all up I hope you found this to be kind of an interesting problem um I think that it's kind of a cool way to think about how like data structures can lay on top of data structures and Achieve certain time complexities and there are definitely some trade-offs that we should talk about for example the memory of this data structure will grow quite a bit more than just having an underlying array because we are maintaining this time index of map Keys as it grows and if we ever do deletions or you know we're already doing insertion but perhaps deletions it is a bit more complex especially if we ever have to concern ourselves with thread safety which is another piece worth mentioning this data structure is certainly not thread safe we would need to think about what our thread safe threat or multi-threading needs are and then maybe consider things like mu taxes or locks to actually make that happen all right so the last thing that I will kind of just point out although this is kind of a deep optimization consideration is that since we effectively have like pointers pointing to pointers pointing to pointers it's going to be a lot less likely that this ends up or this data structure ends up in the CPU cache CPU cache is a very very fast way to access memory and typically things that land in CPU cache are oftentimes contiguous memory things like arrays and the access speed of those can be super super fast but again in this example we weren't focused about on that level of optimization we were really focused on what could we do to get constant time complexity of accessing these values in these different contexts really quickly so again hope you found this really interesting I personally find these types of technical interviews to be extremely hard I will admit even though I've been programming for years I feel like I am programming for my first time ever when I'm kind of put in the hot seat and asked these kinds of questions but independent of not really loving the style of these live interviews I do really find the thought process around them and the exercise itself really intriguing and I hope you did too so that's all for now and I'll see you next time

Blog post: https://joshrosso.com/c/time-based-kv Source code: https://github.com/joshrosso/time-based-kv I recently got the Time Based Key-Value Store problem in a technical interview. It’s a fun exercise, and I believe there might a interesting spin one could put on it. What follows is not a recommendation for an interview question, more-so just an interesting modification to the problem for us to ponder and solve. K/V Store Problem: 00:00:00 K/V Store Problem Enhanced: 00:02:36 Data Structure Design: 00:04:21 Implementing the Data Structure: 00:05:53 Implementing the Constructor and Helpers: 00:07:18 Implementing Set, Get, and GetBefore: 00:09:21 Wrapping Up: 00:31:37