Complex Data Structure Design Questions

Designing custom data structures to meet stringent performance, memory, or concurrency goals. Candidates should be able to explain implementations such as O one LRU caches, prefix trees for type ahead, segment trees and binary indexed trees for efficient range queries, bloom filters and other probabilistic structures for space efficient membership testing, and how to adapt these designs for concurrent access or persistence. Discuss tradeoffs, expected complexity, and when to use approximation or batching to meet production constraints.