← AT&T Interview Insights

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

SeniorRejected
May 2026Remote

Summary

Technical phone screen for a Software Engineer role, one coding problem, rejection came the same afternoon. The problem looked like a standard LRU cache variant until it wasn't.

Questions Asked (1)

Q1

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

Algorithms & Data StructuresSystem DesignTechnical Trade-offs
Author's notes

I knew the standard LRU cache with a doubly linked list and hashmap cold.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then propose a design using a hash map for O(1) lookups and a doubly linked list for LRU ordering. Explain how to handle TTL and eviction, emphasizing the preference for removing expired entries first. Finally, discuss implementation details, edge cases, and trade-offs.

Pro tip: Mention that you would use a background thread or lazy expiration to clean up expired entries, but ensure that get operations check TTL to never return expired data. This shows awareness of concurrency and performance trade-offs.

1. Clarify Requirements and Constraints

Ask about expected load, concurrency needs, memory limits, and whether TTL is per-entry or global. Confirm that O(1) average for get and put is required.

2. Propose Data Structures

Use an unordered_map (hash map) for O(1) key lookup, mapping to nodes in a doubly linked list that maintains LRU order. Each node stores key, value, expiry timestamp, and pointers.

3. Design Core Operations

For get: check if key exists and not expired; if expired, remove and return miss; else move node to front (most recently used) and return value. For put: if key exists, update value and expiry, move to front; else insert new node at front, and if capacity exceeded, evict.

4. Handle Eviction with Expired Preference

When evicting, first scan from the back (least recently used) to find an expired entry; if found, remove it. If no expired entries, evict the LRU node. To keep O(1), consider maintaining a separate list or queue of expired entries, or accept O(n) worst-case for eviction but argue it's amortized O(1) if expirations are frequent.

5. Discuss Implementation and Trade-offs

Mention thread-safety (e.g., mutex or sharding), memory overhead, and alternative eviction policies. Highlight that lazy expiration on get ensures expired entries are never returned.

Key Points to Mention

  • Use of hash map + doubly linked list for O(1) get/put and LRU ordering.
  • TTL handling: store expiry timestamp and check on get; never return expired entries.
  • Eviction strategy: prefer removing expired entries before LRU eviction; discuss how to achieve efficiently.
  • Concurrency considerations: locking, sharding, or lock-free approaches for thread safety.
  • Edge cases: capacity 0, updating existing key, expired entry on put, and clock skew.
  • Trade-offs: memory vs. speed, background cleanup vs. lazy expiration, and worst-case vs. average complexity.

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