Implement Rank based Cache. If time permits, follow up with:
- LRU Cache
- Rank Based LRU Cache
What is a Rank based cache?
A cache with a specific capacity that has static & distinct ranks (integers) associated with it. If the item exists in the cache, return it (no need to update the rank since it is static). You evict the item with lowest rank from the cache.
What is LRU Cache?
This question is covered by LeetCode
What is Rank Based LRU Cache?
Same as Rank based cache, but here you could have multiple keys with the same rank. While evicting, you need to evict the least recently used key if there are multiple keys with the same rank.
Answer:
I used Heap for Rank based cache. For Rank Based LRU Cache, I updated it the heap's value to be a doubly linked list. A hash map would keep track of a reference to the doubly linked list (same concept as LRU cache). The interview went pretty well and they moved forward with full loop. Though honestly, I didn't expect a medium-hard question for a manager role.
Overall process:
Step 1: Informational with manager - 1 hr
Step 2: Manager screen. Includes 2 interviews. 1 coding and 1 manager screen
Step 3: 7 interviews for full loop. One of them is system design, all others focused on different aspects including culture fit and management interviews.
Combined together. 10 if you include the 1hr informational. Almost the double some other companies I interviewed with. Sigh!