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.