Implement Cache, Undo, and DFS

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.