File-Content LRU Cache
Amazon● MediumFULLTIMEONSITE INTERVIEWProblem statement
Simulate a least-recently-used cache that stores file contents. The cache holds at most capacity files.
Each operation is either PUT|path|content or GET|path. A PUT inserts or replaces the complete content. A successful GET returns the content and makes that path most recently used; a missing path returns the empty string. When a new path exceeds capacity, evict the least recently used path.
Design the implementation so GET and PUT run in O(1) average time. One reported approach used a hash map plus a doubly linked list.
Reported follow-ups
- When a successful
GETrefreshes an entry, would you delete and recreate its linked-list node, or detach and move the existing node to the most-recently-used position? Explain the trade-offs, including pointer safety and allocation overhead, while preservingO(1)average updates. - Should the cache store only the file path and name and load content from storage on demand, or store the complete file content? For this exercise, store the complete content.
Return all GET results in operation order.
Function
runFileCache(capacity: int, operations: String[]) → String[]Examples
Example 1
capacity = 2operations = ["PUT|/a|alpha","PUT|/b|beta","GET|/a","PUT|/c|gamma","GET|/b","GET|/c"]return = ["alpha","","gamma"]Reading /a refreshes it, so /b is evicted by the insertion of /c.
Example 2
capacity = 1operations = ["PUT|/x|old","PUT|/x|new","GET|/x"]return = ["new"]Replacing one path updates its content without increasing cache size.
Constraints
0 <= capacity <= 500001 <= operations.length <= 100000- Paths and contents are non-empty printable strings and do not contain
|. - The empty string is reserved for a cache miss.