Microsoft

"You are building a garbage collector for a low-latency runtime that cannot tolerate 'stop-the-world' pauses": The interviewer asked me how to reclaim dead heap objects while application threads continue mutating pointers concurrently; I detailed the Tricolor Marking algorithm, explained how to maintain the strong tricolor invariant using a Yuasa deletion barrier, and walked through concurrent sweeping via free-lists to bound tail latency. "A financial ledger needs to prove that a transaction existed at a specific time without revealing any other user's balance": I was tasked with designing a tamper-evident audit trail for append-only logs; I implemented a Sparse Merkle Tree combined with cryptographic audit paths, showing how a client can verify inclusion in $O(\log N)$ hashing operations using only a root hash and a minimal sibling proof vector. "Design an eviction policy for an in-memory cache where item access patterns exhibit sudden, short bursts that defeat standard LRU": The interviewer challenged me to prevent cache pollution from one-off sequential table scans; I walked through the 2Q and LIRS (Low Inter-reference Recency Set) cache algorithms, demonstrating how splitting the cache into hot and cold pools with ghost entry tracking preserves long-term working sets against recency bias.