AT&T·Software Engineer·Technical Phone Screen·Senior

SeniorRejected

Jun 2026

Summary

Technical phone screen for a Software Engineer role that ended with a rejection letter the same afternoon. The problem itself was interesting but the interviewer's requirements turned out to be contradictory, and I couldn't figure out what they actually wanted in time.

Questions Asked (1)

Design and implement an in-memory LRU cache with per-entry TTL and bounded capacity in C++. Expired entries must never be returned. When evicting, expired entries should be removed before valid LRU entries. Target O(1) average time for get and put.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The contradiction here wrecked me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then describe the core data structures: a hash map for O(1) access and a doubly linked list for LRU ordering, with each entry storing a TTL timestamp. Explain how expiration is handled lazily on access and proactively during eviction, ensuring expired entries are never returned and are evicted before valid LRU entries.

Pro tip: Mention that using a steady clock (e.g., std::chrono::steady_clock) avoids issues with system time changes, and consider discussing trade-offs between lazy and active expiration.

1. Clarify Requirements and Constraints

Ask about expected cache size, TTL precision, thread-safety needs, and whether TTL is per-entry or global. Confirm that expired entries must be removed before LRU eviction.

2. Design Core Data Structures

Propose a hash map (unordered_map) mapping keys to nodes in a doubly linked list. Each node stores key, value, TTL timestamp, and pointers for list operations. The list maintains LRU order (most recently used at front).

3. Implement get and put Operations

For get: check if key exists and if entry is expired; if expired, remove it and return miss; else move node to front and return value. For put: if key exists, update value and TTL and move to front; else insert new node at front, and if capacity exceeded, evict.

4. Handle Expiration and Eviction

During eviction, first scan the list from the back (LRU end) to remove any expired entries. If still over capacity, remove the least recently used valid entry. Also, consider periodic cleanup or lazy removal on access.

5. Analyze Complexity and Trade-offs

Explain that get and put are O(1) average due to hash map and list operations. Discuss trade-offs: lazy expiration may leave expired entries until accessed, but proactive eviction ensures capacity is freed. Mention potential need for synchronization if thread-safe.

Key Points to Mention

Use of std::unordered_map for O(1) key lookup and std::list for O(1) LRU reordering.
Storing TTL as an absolute timestamp (e.g., using std::chrono::steady_clock) to avoid clock skew.
Lazy expiration on get: check TTL before returning value; if expired, remove and return miss.
Eviction policy: remove expired entries from the LRU end first, then evict valid LRU entries if needed.
Capacity management: ensure cache never exceeds max size; update size on insert and removal.
Thread-safety considerations: mutex or lock-free techniques if concurrent access is required.

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