Implement cache and merge intervals
Company: Microsoft
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
The interview included two coding tasks:
1. Implement a fixed-capacity key-value cache with `get(key)` and `put(key, value)`. Both operations must run in O(1) average time. When the cache is full and a new key is inserted, evict the least recently used entry. A successful `get` also counts as a use.
2. Given a list of closed intervals `[start, end]`, merge all overlapping intervals and return the resulting non-overlapping intervals sorted by start value.
Quick Answer: This question evaluates proficiency in designing and implementing efficient data structures (a fixed-capacity LRU key-value cache) and interval-processing algorithms (merging overlapping closed intervals), emphasizing time-complexity constraints, correct state management, and robustness to edge cases within the Coding & Algorithms category.