Interview Question and Internal Scoring Criteria at LinkedIn

Provide an implementation of the RetainBestCache class (skeletons below).

Internal Note for the Interviewer

To begin with, assume that ranks will not change once read. Don't offer this information until the candidate asks.

It's usually wise to let the candidate ignore concurrency safety initially, to ensure they can get a core solution functioning first, but it's a good follow-up requirement.

Follow-up Questions:
1. When rank values are the same, how does the current evict work? Can we change it to evict based on the last access time?
- Notice Rank still has a higher priority over Access time; low-rank items will be evicted first.
- This will suggest a candidate implement a double-linked list for each key. Change HashMap to HashMap>. They also need to update the evict implementation.
- If TreeMap implementation, the candidate needs to convert Set to DoubleLinkedList.
- If Heap implementation, the candidate needs to convert Node to Node>.
- This evaluates candidates on how they merge two different solutions (heap and LRU cache) to resolve a new question.
...

Bonus - Sharding
Depending on how you present the question (and follow-ups), sharding might come up as a way to improve performance. Adding sharding to the existing implementation shouldn't be difficult, especially if the candidate is good and uses composition rather than expansion.

Sample Solutions
For O(1) retrieval—which all candidates should at least assume is required, if not ask about explicitly—it’s apparent that a hashmap of some kind is required. But that doesn’t help with the ordering requirement regarding eviction, so the interesting part of the question starts with what additional data structure is necessary.

Scoring
1. A great candidate will:
Implement the cache cleanly and correctly, with clear and easy-to-follow logic, in O(1) for cached fetches and O(log(n)) if an eviction is required
(e.g., using a HashMap for O(1) cached fetching, a PriorityQueue or TreeMap> of ranks for O(log(n)) firstEntry(), remove(), and put(), and synchronized blocks to make the methods safe for multithreading.)
Ask about cases like low-rank fetches (it is unclear whether an object with rank X should be replaced by a new object with rank less than X) and non-static rank on their own.
Be able to handle non-static rank in a sensible way, as well as putting reasonable limits on when changed ranks will be reflected.
Ask about or consider making this data structure safe for multithreading.
Complete the question in less than 30 minutes.

... ...