Katkat
Back

Implement Caches, Undo, and Traversal

NetflixSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.