PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Netflix
  • Coding & Algorithms
  • Software Engineer

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.

Constraints

  • 0 <= len(operations) <= 200000
  • Keys are strings and values are integers
  • 0 <= ttlSeconds <= 10^9
  • 0 <= timestamp <= 10^9
  • Operation timestamps are given in nondecreasing order
  • Latest put for the same key overwrites the previous value

Examples

Input: [('put', 'a', 10, 5, 0), ('get', 'a', 4), ('cleanup', 5), ('get', 'a', 5)]

Expected Output: [10, 1, None]

Explanation: Key 'a' is valid at time 4, expires at time 5, is removed by cleanup at time 5, and is missing afterward.

Input: [('put', 'a', 1, 10, 0), ('put', 'a', 2, 3, 1), ('get', 'a', 3), ('cleanup', 5), ('get', 'a', 5), ('cleanup', 11), ('get', 'a', 11)]

Expected Output: [2, 1, None, 0, None]

Explanation: The second put overwrites the first. Cleanup removes only the current expired entry. The old heap record is stale and must be ignored.

Input: [('put', 'x', 7, 0, 10), ('cleanup', 10), ('get', 'x', 10)]

Expected Output: [1, None]

Explanation: A ttl of 0 means the entry expires immediately at the put timestamp.

Input: []

Expected Output: []

Explanation: No operations means no outputs.

Hints

  1. Use a hash map for fast key lookup on get.
  2. For background cleanup, keep expirations in a min-heap and use a version counter so stale heap entries from overwritten keys can be ignored.

Part 2: Undo Manager for Text Commands

A text buffer starts empty. You must process editor commands with undo support. Command ('type', s) appends string s to the end of the buffer and always succeeds. Command ('delete', k) removes the last k characters, but if k is larger than the current buffer length, the command fails, the buffer stays unchanged, and the failed command must not be recorded in undo history. Command ('undo',) reverts the most recent successful command that has not already been undone. If there is nothing to undo, undo does nothing. Return the current buffer after every operation.

Constraints

  • 0 <= len(operations) <= 200000
  • All typed strings are non-empty
  • 1 <= k <= 200000 for delete operations
  • Total length of all typed strings is at most 200000
  • Operations are valid tuples in one of the listed formats

Examples

Input: [('type', 'ab'), ('type', 'cd'), ('delete', 3), ('undo',), ('undo',)]

Expected Output: ['ab', 'abcd', 'a', 'abcd', 'ab']

Explanation: Undo first restores the deleted text, then undoes the earlier type command.

Input: [('type', 'hi'), ('delete', 5), ('undo',), ('undo',)]

Expected Output: ['hi', 'hi', '', '']

Explanation: The delete fails because the buffer is too short, so it is not added to history. The first undo removes 'hi'. The second undo does nothing.

Input: [('undo',)]

Expected Output: ['']

Explanation: Undo on empty history is a no-op.

Input: [('type', 'a'), ('type', 'bc'), ('undo',), ('type', 'd'), ('delete', 1), ('undo',)]

Expected Output: ['a', 'abc', 'a', 'ad', 'a', 'ad']

Explanation: After undoing 'bc', typing 'd', deleting it, and undoing again, the buffer returns to 'ad'.

Hints

  1. Use a stack to store the inverse of each successful command.
  2. When deleting, save the removed substring so undo can restore it exactly.

Part 3: DFS Traversal of an Organization Tree

You are given the root of an organization hierarchy. Each node is a dictionary with keys id and children, where children is a list of child nodes in left-to-right order. Return the node ids in depth-first preorder traversal order, meaning you visit a node before its children. If the tree is empty, return an empty list.

Constraints

  • 0 <= number of nodes <= 100000
  • Each node has an integer id
  • Children are already listed in the required left-to-right visit order
  • Node ids are unique

Examples

Input: (None,)

Expected Output: []

Explanation: An empty tree has no nodes to visit.

Input: ({'id': 1, 'children': []},)

Expected Output: [1]

Explanation: A single-node tree is visited by returning just that node's id.

Input: ({'id': 1, 'children': [{'id': 2, 'children': [{'id': 5, 'children': []}, {'id': 6, 'children': []}]}, {'id': 3, 'children': []}, {'id': 4, 'children': [{'id': 7, 'children': []}]}]},)

Expected Output: [1, 2, 5, 6, 3, 4, 7]

Explanation: Preorder visits the root first, then each subtree from left to right.

Input: ({'id': 10, 'children': [{'id': 20, 'children': [{'id': 30, 'children': [{'id': 40, 'children': []}]}]}]},)

Expected Output: [10, 20, 30, 40]

Explanation: In a chain-shaped tree, preorder follows the single path from top to bottom.

Input: ({'id': 0, 'children': [{'id': -1, 'children': [{'id': 2, 'children': []}, {'id': 3, 'children': []}]}, {'id': 5, 'children': []}]},)

Expected Output: [0, -1, 2, 3, 5]

Explanation: The traversal still follows preorder correctly even with negative ids.

Hints

  1. An iterative solution with an explicit stack avoids recursion depth issues.
  2. If using a stack, push children in reverse order so they are visited left to right.
Last updated: May 4, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Compute Minimum Task Completion Time - Netflix (medium)
  • Solve String Arrays and Row Deduplication - Netflix (medium)
  • Implement Cache, Undo, and DFS - Netflix
  • Implement Streaming Word Counter - Netflix (medium)
  • Implement TTL Cache and Tree Balance Reporting - Netflix (medium)