In this week’s coding interview question post, I’m going to analyze one of the best questions I’ve seen in recent interviews. As many people ask for the pseudo code in order to help them understand the algorithm, I will also include that in the post as well.
It’s worth to emphasize again that what’s truly important is not the final code/solution, it’s all about the analysis process and I’m going to teach you exactly how to come up with the right idea.
Implement data structure “Map” storing pairs of integers (key, value) and define following member functions in O(1) runtime: void insert(key, value), void delete(key), int get(key), int getRandomKey().
We select this question for mainly two reasons:
- The question was asked by Uber last month and got a lot of discussions.
- It’s a great question to test your understanding of basic data structures. Memorizing data structure definition won’t work. It’s all about UNDERSTANDING.
First and foremost, think about the question by yourself. It’s a great opportunity to test if you have a clear understanding of basic data structure.
Here we go.
There are many ways to implement a map, for instance, C++ std library is using red-black tree as the underlying system. However, to make operations of O(1) time complexity, hash should be the No.1 thing in your mind and I hope it won’t take you more than a second to come up with this.
With a hashmap, we can easily achieve O(1) time complexity for Insert, Get and Delete, however, what makes the question interesting is GetRandomKey function. As you can see, a hashmap won’t allow you to get all the keys instantly and you need O(n) time to get a random key.
Many people are stuck here. However, there are a couple of ways to think about this problem.
First and foremost, since the problem we have is GetRandomKey is of O(n) time complexity instead of O(1), a good technique is the time and space tradeoff. Specifically, if we want to make algorithm faster, we can try using more memory. This gives us some rough ideas like using another data structure (maybe tree, queue, linked list, array etc) to store all the keys separately, or when inserting a pair, we can store some additional data with the pair.
Secondly, when getting a random key, the most straightforward approach is to have a random number and somehow we map this number to the corresponding key. To make it O(1) time complexity, most likely we’ve got to do the random sampling of an array.
Things become much clearer. The right approach seems to be when inserting a new pair, we store the new key in a separate array. And when we call GetRandomKey, we can easily to the random sampling of the array in O(1) time complexity. However, a new problem pops up – Delete operation becomes O(n) since you need to delete key from the array as well when removing a pair.
If you want to achieve O(1) deletion, another option is to use a linked list to store all the keys, however, this won’t give you O(1) for GetRandomKey.
There’s a trick here. In essence, you need O(n) time for array deletion is because you are keeping its origin order. But this is totally unnecessary in the current problem. Suppose you have [1, 4, 2, 5, 9] in the array and you delete 2. Instead of move 5 and 9 to the left, you can just switch 2 with 9 and reduce the length by 1. So the deletion can be done in O(1) time complexity, although we lose the order.
In addition, in order to find the deleted key in array instantly, we also need to store the index in the map as well. Take the same array as well, when inserting 4 with value 10, we need to store <4, (10, 1)> in the map where 1 is the index of the key in the array.
Here is the pseudo code (I ignored all the checks like checking if key exists in the map).
There’s no need to summarize any takeaways from this question since the whole analysis process is worth reading twice.
In fact, I’ve gone through exactly the same thinking process when solving this problem. I thought about all the data structures I’ve mentioned like linked list, tree etc..
There are a couple questions that are solved in similar ways:
- How to design and implement LRU cache
- How to shuffle an array (this uses exactly the same technique in GetRandomKey)
By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook etc..