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