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.