Quick Overview

This question evaluates proficiency with tree-based mutable data structures and cache design, specifically maintaining aggregated state in a full binary tree after leaf updates and implementing an LRU cache supporting O(1) get/put operations.

Implement tree ops and LRU cache

Company: SoFi

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

##### Question Implement set(index) and clear(index) for the leaves of a full binary tree initially filled with 0s, where a parent node becomes 1 only when both children are 1; clearing a leaf should update ancestors accordingly. LeetCode 146. LRU Cache: Design and implement a data structure that supports get(key) and put(key, value) in O( 1) time while evicting the least-recently-used item when the capacity is exceeded. https://leetcode.com/problems/lru-cache/description/

Overview: This question evaluates proficiency with tree-based mutable data structures and cache design, specifically maintaining aggregated state in a full binary tree after leaf updates and implementing an LRU cache supporting O(1) get/put operations.

You are given a full binary tree with n leaves (n is a power of two). Initially, all leaves are 0. Each internal node's value is 1 if and only if both its children are 1, otherwise 0. You must process a sequence of operations on the leaves: set(i) sets leaf i to 1, and clear(i) sets leaf i to 0 (0-indexed). After each operation, update ancestors accordingly and report the value at the root (0 or 1). Implement a function that takes n and a list of operations and returns a list of the root values after each operation.

Constraints

  • 1 <= n <= 200000
  • n is a power of two
  • 1 <= len(ops) <= 200000
  • Each operation is a pair (cmd, i) where cmd is 'set' or 'clear' and 0 <= i < n
  • Updates should be O(log n) per operation; overall O(len(ops) log n)

Hints

  1. Model the updates with a segment tree using bitwise AND as the merge function.
  2. Store values in an array of size 2*n with leaves at indices [n .. 2*n-1].
  3. On updating a leaf, recompute ancestors up to the root, and you can stop early if a node's value does not change.

Loading coding console...

Show the approach

Approach

Use a segment tree where leaves store the given leaf values and each internal node stores the bitwise AND of its two children. A 'set' or 'clear' operation updates one leaf and then recomputes the AND values on the path to the root. The root value after each operation is the AND of all leaves, which we append to the result.

Time complexity:
O(q log n), where q = len(ops)
Space complexity:
O(n)