Katkat
Back

Implement tree ops and LRU cache

SoFiSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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/