Implement Cache, Undo, and DFS
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Onsite
Answer the following independent coding prompts.
1. Timed cache: Implement a generic in-memory cache. Each inserted item has a fixed expiration time known at insertion time. Support put(key, value, ttl), get(key), delete(key), and cleanupExpired(now). Start with the simplest correct version. Then extend it so expired entries are physically removed by a sidecar cleanup process. get is the hot path, so it should not scan the cache or perform bulk cleanup. State the time and space complexity of each operation.
2. Command undo: Implement an undo manager for a simple command-based application, such as a text editor with append, delete, and replace commands. A command should contain enough information to apply itself and to roll itself back. Support execute(command), undo(), and canUndo(). Discuss time and space complexity.
3. Organization tree traversal: Given a tree whose nodes represent employees or organization units and whose children are direct reports, return a depth-first traversal starting from a given root. Handle an empty tree, arbitrary branching factor, and deep trees. Provide either a recursive or iterative implementation and analyze complexity.
Quick Answer: This question evaluates implementation skills in data structures, algorithmic complexity, and state-management patterns by combining a timed in-memory cache, a command-undo manager, and depth-first traversal of an organizational tree, and is categorized under Coding & Algorithms.
Part 1: Timed Cache Simulator
Implement a timed in-memory cache simulator.
Each cache entry has a value and an expiration time computed as `now + ttl` when it is inserted. You must process a sequence of operations in order:
- `('put', key, value, ttl, now)`: Insert or overwrite `key` with `value`. The item expires at time `now + ttl`.
- `('get', key, now)`: Return the stored value if the key exists and `now < expire_time`; otherwise return `-1`.
- `('delete', key)`: Remove the key if it is physically present in the cache. Return `True` if something was removed, otherwise `False`.
- `('cleanup', now)`: Physically remove all expired entries whose expiration time is `<= now`, and return how many keys were removed.
Important requirements:
- `get` is the hot path, so it must only inspect the requested key.
- Updating the same key multiple times can leave stale expiration records behind; cleanup must ignore stale records safely.
Return a list of results for every non-`put` operation, in order.
Constraints
- 0 <= len(operations) <= 2 * 10^5
- Timestamps used in `put`, `get`, and `cleanup` are non-decreasing integers.
- 0 <= ttl <= 10^9
- Keys are hashable Python literals such as strings or integers.