Meta·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Did a Meta SWE coding round that had multiple levels of difficulty, each adding more constraints on top of the last. Made it through the earlier parts okay but Level 3 introduced timestamp and TTL requirements and I just couldn't get through all the test cases in time.

Questions Asked (1)

Implement a series of cache-like functions that support timestamp tracking and time-to-live (TTL) expiration logic.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The earlier levels were manageable but once TTL came into the picture I slowed way down.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: what operations are needed (get, put, etc.), how timestamps are provided (system time or injected), and the exact TTL semantics (e.g., expire after write or access). Then design a data structure that combines a hash map for O(1) key lookup with a mechanism to track expiration, such as a min-heap or a linked list ordered by expiry time, and discuss trade-offs between different approaches.

Pro tip: Mention that using a min-heap for expiration can lead to O(log n) operations, but a more efficient approach is to use a combination of a hash map and a doubly linked list ordered by expiry time, achieving O(1) for get and put, and lazy deletion for expired entries. Also, discuss how to handle time efficiently by using a monotonic clock and avoiding system time changes.

1. Clarify Requirements

Ask about the exact operations (e.g., get, put, delete), whether timestamps are provided or use system time, and the TTL semantics (expire after write or access). Also clarify expected time complexity and any constraints.

2. Choose Data Structures

Select a hash map for O(1) key access and a secondary structure to track expiration order, such as a min-heap or a doubly linked list sorted by expiry time. Discuss trade-offs: heap gives O(log n) for expiration but simpler, while linked list can give O(1) for expiration if we maintain order.

3. Implement Core Operations

Write functions for get and put. For get, check if the key exists and if it's expired; if expired, remove it and return null. For put, insert or update the key with its expiry time and add to the expiration tracking structure.

4. Handle Expiration

Implement lazy expiration: on each access, check if the item is expired and remove it if so. Optionally, implement active expiration with a background thread or periodic cleanup, but discuss the trade-offs (e.g., complexity vs. memory).

5. Analyze and Optimize

Analyze time and space complexity of each operation. Discuss potential optimizations, such as using a timing wheel for efficient expiration or batching expirations to reduce overhead.

Key Points to Mention

Time complexity: aim for O(1) for get and put, and discuss how expiration affects it.
Space complexity: O(n) for storing n items, plus overhead of expiration tracking.
Trade-offs between eager vs. lazy expiration: eager uses more CPU but less memory, lazy uses less CPU but may hold expired items.
Handling of time: use a monotonic clock to avoid issues with system time changes.
Concurrency: if multi-threaded, discuss locking or lock-free approaches.
Edge cases: expired items on get, updating TTL on put, and handling of null values.

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