Implement an LRU cache

Competency asserted: Coding (Logical and Maintainable)
Job title: Software Development Engineer (SDE II)

Problem Statement

Code a basic caching solution.

Requirements:

• Examples:
  • add(String userId, Object value)
  • get(String userId)
• eviction strategy: LRU.
• single threaded
• one instance

Solution

Hashtable for lookups. Doubly Linked List for expiration (we need both previous and next). When an item is accessed, move it to the top of the list (you get the reference from the hashtable). That way, the end of the list always contains the stalest information. When your cache is full, just remove the last element of the list.

This solution is built-in in Java via LinkedHashMap and its removeEldestEntry() method. If you know it, say it. It’s unlikely you will be able to use it during your interview though. From the javadoc, “This is useful if the map represents a cache: it allows the map to reduce memory consumption by deleting stale entries.”

The interviewer can challenge you by asking a different eviction strategy or by asking you to handle multiple machines.

LeetCode LRU Cache
InterviewBit
Cracking the Coding Interview

Example feedback

Candidate 1

Vote: ?

His code was easy to read, correctly formatted and had proper variable naming and constants. However, the code produced was too small to evaluate if it was maintainable.

The candidate rushed to the whiteboard and started coding. He asked if we had “more” requirements instead of asking specific questions and deal with ambiguity. The candidate only inquired about the eviction strategy. However, he did not clarify if the eviction was based on the latest insertion or latest get. “LRU” is very confusing if you don’t exactly remember what it stands for.

He came up with a naive solution and coded the solution FIRST, before thinking it through (time complexity, space complexity, bottlenecks and challenges, etc.).

The candidate explained his thoughts along the way and asked clarifying questions when asked to implement a follow-up, or when faced with a choice during coding. With the removal, he did not easily see a way to abstract through map to address and did it with a little help from the interviewer.

He struggled to reach the optimal solution (hashmap + doubly linked list) despite many hints and guidance. His final answer still had 2 hashset where only one was really needed.