Implement Caches, Undo, and Traversal
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Interview Round: Onsite
Solve the following coding tasks. For each task, define clean APIs, implement the core logic, and be prepared to explain time and space complexity.
### Task 1: Timed cache
Implement an in-memory key-value cache where every item has a fixed expiration time.
Requirements:
- `put(key, value, ttlSeconds)` stores a value and an expiration timestamp.
- `get(key)` returns the value if the key exists and has not expired; otherwise it returns `null` or an equivalent missing value.
- Start with the simplest correct implementation.
- Follow-up: add cache cleanup so expired entries are eventually removed.
- `get` is the hot path, so avoid doing expensive cleanup work inside `get`.
- Assume there can be a sidecar or background cleanup process. Design what data structures that process should use.
- Discuss the time complexity of `put`, `get`, and cleanup.
### Task 2: Command undo
Implement an undo manager for commands.
Requirements:
- A command has an `execute()` operation and an `undo()` operation.
- `executeCommand(command)` executes a command and records it only if execution succeeds.
- `undo()` reverts the most recently executed command that has not already been undone.
- Define behavior when there is nothing to undo.
- Discuss time and space complexity.
Optional follow-up:
- Extend the design to support `redo()`.
### Task 3: Organization tree traversal
You are given an organization hierarchy represented as a rooted tree. Each node has an id and zero or more child nodes.
Implement a depth-first traversal that returns the node ids in DFS order.
Requirements:
- Provide either recursive or iterative DFS.
- Handle an empty tree.
- Discuss time and space complexity.
Quick Answer: This question evaluates proficiency with data structures, API design, and system-level concerns by combining timed in-memory caching, command undo/redo semantics, and depth-first traversal of a tree; it falls under the Coding & Algorithms domain and is commonly asked to assess practical implementation skills, correctness under edge cases, and the ability to reason about time and space complexity. The level of abstraction spans practical application—designing clean APIs and implementing core logic—while also requiring conceptual understanding of complexity analysis and background cleanup or state-management patterns.
Part 1: Timed Cache Simulation
Implement a timed in-memory cache simulator. Each put stores a key, value, and expiration time equal to timestamp + ttlSeconds. A get returns the value only if the key exists and the given timestamp is strictly smaller than the expiration time; otherwise it returns None. A cleanup operation represents a background process that removes all expired entries at or before the given timestamp. If the same key is put again, the newer value replaces the older one. Return the outputs of every get and cleanup operation in order.