The following is likely to end up in the list of questions we’ll ask candidates to answer when they apply to Hibernating Rhinos.
We need to store information about keys and their location on disk. We need to implement a trie. We want the trie to store int64 size values and unbounded UTF8 string keys.
Given that, we have the following interface:
We need to implement that with the following properties:
- The trie will be represented by single 32 kilobytes byte array.
- You cannot store any additional information about the trie outside of the array.
- The costs of searching in the trie in proportional to the size of the key.
- There are no duplicates.
- This is a single thread implementation.
- If the array is full, it is fine to return false from the TryWrite()
- Unsafe code is fine (but not required).
- You cannot use any in memory structure other than the byte array. But it is fine to allocate memory during the processing of the operations (for example, to turn the string key into a byte array).
We will be looking at the following aspect in the implementation:
- Space used
The idea is that we can pack as much as possible into as small a space as possible, but at the same time, we can get great performance.