Citadel·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026

Summary

Citadel system design round, one question the whole time. The problem sounds clean on paper but there's a lot of surface area once you start thinking about thread safety and how the eviction callback interacts with internal state.

Questions Asked (1)

Design a cache class that accepts a user-supplied eviction policy function. When the cache is full and a new item is added, the eviction function determines which key to remove. The same class should support LRU, LFU, FIFO, or any custom policy without modifying the core cache code.

System DesignAPI & IntegrationsTechnical Trade-offs

Author's notes

I started with a basic map and a list of keys, then realized the eviction callback needs visibility into cache internals to make any real decision.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and defining the cache interface with a pluggable eviction policy. Then design the core cache as a composition of a storage map and an eviction policy object, ensuring the policy is notified on every access and insertion. Finally, discuss trade-offs like thread safety, policy state management, and performance overhead.

Pro tip: Emphasize that the eviction policy should be an interface with methods like `onGet`, `onPut`, and `evict`, and that the cache should delegate decisions to it. This shows you understand the Strategy pattern and separation of concerns.

1. Clarify Requirements and Constraints

Ask about expected cache size, concurrency needs, and whether policies need to be swapped at runtime. Confirm that the policy is user-supplied and that the cache should not know about specific policies.

2. Define Interfaces and Data Structures

Design an EvictionPolicy interface with methods to track accesses and select a victim. The cache will use a map for O(1) lookups and delegate eviction decisions to the policy.

3. Implement Core Cache Logic

On get, update the policy's access records and return the value. On put, if the cache is full, call the policy to get a key to evict, remove it, then insert the new item and update the policy.

4. Provide Example Policies

Show how LRU, LFU, and FIFO can be implemented as separate classes implementing the EvictionPolicy interface, demonstrating the flexibility of the design.

5. Discuss Trade-offs and Extensions

Address thread safety (e.g., using locks or concurrent structures), performance overhead of policy updates, and how to handle custom policies that may need additional state.

Key Points to Mention

Strategy pattern: encapsulate eviction algorithms behind a common interface.
Separation of concerns: cache handles storage and retrieval, policy handles eviction decisions.
Policy interface methods: e.g., `keyAccessed(key)`, `keyInserted(key)`, `selectVictim()`.
Thread safety: synchronize cache operations and policy state, or use concurrent data structures.
Performance: O(1) average for get/put, but policy operations may add overhead (e.g., LFU frequency updates).
Extensibility: new policies can be added without modifying cache code, adhering to Open/Closed principle.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.