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 SoFi.

What role is this question designed for?

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

Implement tree ops and LRU cache | SoFi Coding Question

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)

Solution

def process_tree_ops(n, ops):
    # Segment tree storing AND over leaves
    size = n
    if size <= 0:
        return []
    # 1-based indexing for convenience; index 0 unused
    tree = [0] * (2 * size)

    def update(idx, val):
        # idx: leaf index [0..n-1], val: 0 or 1
        p = idx + size
        if tree[p] == val:
            return
        tree[p] = val
        p //= 2
        while p >= 1:
            new_val = tree[2 * p] & tree[2 * p + 1]
            if tree[p] == new_val:
                break
            tree[p] = new_val
            p //= 2

    res = []
    for op in ops:
        # Accept both tuple and list forms
        cmd, i = op[0], op[1]
        if cmd == 'set':
            update(i, 1)
        elif cmd == 'clear':
            update(i, 0)
        else:
            raise ValueError("Unknown command: %s" % cmd)
        res.append(tree[1])  # root value
    return res

Explanation

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).

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.

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.