PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Netflix
  • Coding & Algorithms
  • Software Engineer

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.

Part 1: Timed Cache Simulator

Implement a timed in-memory cache simulator. Each cache entry has a value and an expiration time computed as `now + ttl` when it is inserted. You must process a sequence of operations in order: - `('put', key, value, ttl, now)`: Insert or overwrite `key` with `value`. The item expires at time `now + ttl`. - `('get', key, now)`: Return the stored value if the key exists and `now < expire_time`; otherwise return `-1`. - `('delete', key)`: Remove the key if it is physically present in the cache. Return `True` if something was removed, otherwise `False`. - `('cleanup', now)`: Physically remove all expired entries whose expiration time is `<= now`, and return how many keys were removed. Important requirements: - `get` is the hot path, so it must only inspect the requested key. - Updating the same key multiple times can leave stale expiration records behind; cleanup must ignore stale records safely. Return a list of results for every non-`put` operation, in order.

Constraints

  • 0 <= len(operations) <= 2 * 10^5
  • Timestamps used in `put`, `get`, and `cleanup` are non-decreasing integers.
  • 0 <= ttl <= 10^9
  • Keys are hashable Python literals such as strings or integers.

Examples

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

Expected Output: [10, -1, 1, -1]

Explanation: Key 'a' expires at time 5. It is valid at time 3, expired at time 5, and cleanup physically removes it.

Input: [('put', 'x', 1, 10, 0), ('put', 'x', 2, 2, 1), ('cleanup', 4), ('get', 'x', 4), ('cleanup', 11), ('get', 'x', 11)]

Expected Output: [1, -1, 0, -1]

Explanation: The second put overwrites 'x' with an earlier expiration. The old heap record from the first put becomes stale and must be ignored later.

Input: [('delete', 'z'), ('put', 'z', 7, 3, 2), ('delete', 'z'), ('get', 'z', 3), ('cleanup', 10)]

Expected Output: [False, True, -1, 0]

Explanation: Deleting a missing key returns False. After deleting 'z', later get misses and cleanup removes nothing.

Input: [('put', 'k', 5, 0, 10), ('get', 'k', 10), ('cleanup', 10), ('get', 'k', 11)]

Expected Output: [-1, 1, -1]

Explanation: A ttl of 0 means the item expires immediately at insertion time.

Input: []

Expected Output: []

Explanation: No operations means no results.

Hints

  1. Use a hash map so `get(key, now)` only needs to inspect one key.
  2. A min-heap of `(expire_time, key)` pairs lets `cleanup(now)` remove expired candidates efficiently while skipping stale heap entries.

Part 2: Undo Manager for a Text Editor

Implement an undo manager for a simple command-based text editor. The document starts as an empty string. Process operations in order: - `('append', text)`: Append `text` to the end of the document. - `('delete', k)`: Delete the last `k` characters. If `k` is larger than the current length, delete the whole document. - `('replace', start, end, text)`: Replace the substring `document[start:end]` with `text`. - `('undo',)`: Undo the most recent modifying command that has not already been undone. If there is nothing to undo, do nothing. - `('canUndo',)`: Return `True` if there is at least one executed modifying command that can still be undone; otherwise return `False`. - `('get',)`: Return the current document. Each modifying command must store enough information to roll itself back. Return the results of all `get` and `canUndo` operations in order.

Constraints

  • 0 <= len(operations) <= 2 * 10^4
  • For every `replace` command, `0 <= start <= end <= len(current_text)` at execution time.
  • For every `delete` command, `k` is a non-negative integer.
  • The total number of characters appearing in all appended and replacement strings is at most 2 * 10^5.

Examples

Input: [('append', 'abc'), ('append', 'de'), ('get',), ('delete', 2), ('get',), ('undo',), ('get',), ('replace', 1, 4, 'XYZ'), ('get',), ('undo',), ('get',), ('canUndo',)]

Expected Output: ['abcde', 'abc', 'abcde', 'aXYZe', 'abcde', True]

Explanation: Demonstrates append, delete, replace, and undo in sequence.

Input: [('canUndo',), ('undo',), ('get',)]

Expected Output: [False, '']

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

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

Expected Output: ['', 'hi']

Explanation: Deleting more characters than exist clears the document; undo restores it.

Input: [('replace', 0, 0, 'a'), ('get',), ('undo',), ('get',)]

Expected Output: ['a', '']

Explanation: A replace with `start == end` acts like insertion, and undo removes the inserted text.

Input: []

Expected Output: []

Explanation: No operations produce no query results.

Hints

  1. You do not need to snapshot the whole document after every command; store only the inverse information needed for undo.
  2. For `replace`, save the old substring and remember the range occupied by the new text so you can restore the old content later.

Part 3: Depth-First Traversal of an Organization Tree

You are given the root of an organization tree. Each node is represented as a dictionary with this shape: `{'id': value, 'children': [child1, child2, ...]}` Return a depth-first traversal starting from the given root. Use preorder DFS: 1. Visit the current node. 2. Visit each child subtree from left to right. Your solution must handle: - an empty tree (`None`) - any number of children per node - deep trees, where an iterative solution is safer than recursion

Constraints

  • 0 <= number of nodes <= 10^5
  • Each node uses the format `{'id': value, 'children': [...]}`.
  • Children must appear in the output in the same left-to-right order as listed in the input.
  • Node ids may be integers or strings.

Examples

Input: None

Expected Output: []

Explanation: An empty tree has no traversal.

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

Expected Output: [1]

Explanation: A single-node tree visits only its root.

Input: {'id': 'CEO', 'children': [{'id': 'CTO', 'children': [{'id': 'Dev1', 'children': []}, {'id': 'Dev2', 'children': []}]}, {'id': 'CFO', 'children': []}, {'id': 'COO', 'children': [{'id': 'Ops1', 'children': []}]}]}

Expected Output: ['CEO', 'CTO', 'Dev1', 'Dev2', 'CFO', 'COO', 'Ops1']

Explanation: This is a preorder traversal: parent first, then each child subtree from left to right.

Input: {'id': 10, 'children': [{'id': 20, 'children': []}, {'id': 30, 'children': [{'id': 40, 'children': []}, {'id': 50, 'children': []}, {'id': 60, 'children': []}]}]}

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

Explanation: The tree has an arbitrary branching factor, not just binary children.

Input: {'id': 1, 'children': [{'id': 2, 'children': [{'id': 3, 'children': [{'id': 4, 'children': []}]}]}]}

Expected Output: [1, 2, 3, 4]

Explanation: A deep chain should still be traversed correctly.

Hints

  1. Preorder DFS visits the node before its children.
  2. If you use an explicit stack, push children in reverse order so they are processed 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 Streaming Word Counter - Netflix (medium)
  • Implement TTL Cache and Tree Balance Reporting - Netflix (medium)
  • Implement ordering and undo executor - Netflix (medium)