How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Netflix.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Netflix during technical interviews.

Implement TTL Cache and Tree Balance Reporting

Quick Overview

This question evaluates proficiency in designing efficient in-memory data structures and tree algorithms, specifically time-to-live cache behavior (expiration semantics and accurate unexpired counts) and per-node subtree-height computations for balance reporting, and it falls under the Coding & Algorithms domain.

Company: Netflix

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Complete both coding tasks. ### Task A: Time-limited cache Design and implement an in-memory cache where every key expires after a time-to-live duration. Required operations: - `put(key, value, ttlMillis, nowMillis)`: insert or update `key` with `value`; the key expires at `nowMillis + ttlMillis`. - `get(key, nowMillis)`: return the value if the key exists and has not expired; otherwise return `null` and treat the key as absent. - `count(nowMillis)`: return the number of keys that are currently unexpired. Handle overwrites, expired entries, and repeated calls efficiently. ### Task B: Report each tree node's level and balance status You are given the root of a binary tree. The root is at level `0`. For every node, output a record containing: - the node value, - the node's level, - whether the node is balanced. A node is balanced if the heights of its left and right subtrees differ by at most `1`. Empty subtrees have height `0`. Output the records in depth-first preorder traversal. Design the algorithm so that it runs in `O(n)` time for `n` nodes without repeatedly recomputing subtree heights.

Quick Answer: This question evaluates proficiency in designing efficient in-memory data structures and tree algorithms, specifically time-to-live cache behavior (expiration semantics and accurate unexpired counts) and per-node subtree-height computations for balance reporting, and it falls under the Coding & Algorithms domain.

Part 1: Time-Limited Cache Operation Simulator

Design a function that simulates an in-memory TTL (time-to-live) cache. Each key stores a value and an expiration time. Process the given operations in order. For a `put`, store or overwrite the key so that it expires at `nowMillis + ttlMillis`. For a `get`, return the stored value if the key is still unexpired; otherwise return `None` and treat the key as absent. For a `count`, return how many keys are currently unexpired. Return a list containing the results of every `get` and `count` operation in the order they occur. A key is considered expired when `nowMillis >= expiryTime`, so a TTL of `0` means the item is immediately expired.

Constraints

0 <= len(operations) <= 200000
Operation times are non-decreasing in the given list
0 <= ttlMillis <= 10^9
Keys are hashable Python literals; values are Python literals

Examples

Input: [('put', 'a', 10, 100, 0), ('get', 'a', 50), ('count', 50), ('get', 'a', 100), ('count', 100)]

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

Explanation: `a` is valid at time 50, but expired at time 100 because expiry is 100 and `nowMillis >= expiryTime` counts as expired.

Input: [('put', 'x', 1, 100, 0), ('put', 'x', 2, 200, 50), ('get', 'x', 120), ('count', 120), ('get', 'x', 250)]

Expected Output: [2, 1, None]

Explanation: The second `put` overwrites the first one. The old expiration should not remove the newer value.

Input: [('put', 'k', 'v', 0, 5), ('get', 'k', 5), ('count', 5)]

Expected Output: [None, 0]

Explanation: A TTL of 0 means the key expires immediately at time 5.

Input: []

Expected Output: []

Explanation: No operations means no outputs.

Input: [('put', 'a', 1, 5, 0), ('put', 'b', 2, 10, 3), ('count', 4), ('count', 5), ('count', 13), ('get', 'b', 13)]

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

Explanation: At time 4 both keys are valid, at time 5 `a` has expired, and at time 13 `b` has also expired.

Hints

A min-heap ordered by expiration time can help remove expired entries efficiently.
When a key is overwritten, older heap entries for that key become stale; store a version number to detect them.

Part 2: Preorder Tree Level and Balance Report

You are given a binary tree. The root is at level `0`. For every node, produce a record containing `(node_value, level, is_balanced)` and return all records in depth-first preorder traversal. A node is balanced if the heights of its left and right subtrees differ by at most `1`. An empty subtree has height `0`. The algorithm must run in `O(n)` time for `n` nodes and must not repeatedly recompute subtree heights.

Constraints

0 <= number of nodes <= 10000
Each non-empty node is a tuple of exactly 3 elements: `(value, left, right)`
Each `left` and `right` is either `None` or another valid node tuple

Examples

Input: (1, (2, (4, None, None), (5, None, None)), (3, None, None))

Expected Output: [(1, 0, True), (2, 1, True), (4, 2, True), (5, 2, True), (3, 1, True)]

Explanation: Every node has left and right subtree heights differing by at most 1.

Input: (1, (2, (3, None, None), None), None)

Expected Output: [(1, 0, False), (2, 1, True), (3, 2, True)]

Explanation: Node 1 is unbalanced because its left subtree height is 2 and right subtree height is 0.

Input: None

Expected Output: []

Explanation: An empty tree produces no records.

Input: (1, (2, (4, (8, None, None), None), None), (3, None, None))

Expected Output: [(1, 0, False), (2, 1, False), (4, 2, True), (8, 3, True), (3, 1, True)]

Explanation: Nodes 2 and 1 are unbalanced, while the lower nodes remain balanced.

Input: (42, None, None)

Expected Output: [(42, 0, True)]

Explanation: A single node is always balanced.

Hints

Compute subtree heights in a postorder traversal so each node's height is calculated once.
After storing whether each node is balanced, do a preorder traversal to emit records with levels.

Quick Overview