Katkat
Back

Implement TTL Cache and Tree Balance Reporting

NetflixSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.