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

Intermediate

May 2026

Summary

Meta SWE coding round with two problems back to back. Both were more involved than I expected for a single session, and the second one especially had some tricky edge cases I didn't fully think through in time.

Questions Asked (2)

Design an in-memory time-versioned key-value store that supports set(key, value, timestamp) and get(key, timestamp), where get returns the value at the largest stored timestamp less than or equal to the given timestamp.

Algorithms & Data StructuresSystem Design

Author's notes

I knew binary search was the move here pretty quickly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify requirements and constraints, then propose a design using a hash map from keys to time-ordered lists of (timestamp, value) pairs, with binary search for efficient get operations. Discuss trade-offs between different data structures and consider concurrency and memory management.

Pro tip: Mention that timestamps can be assumed monotonically increasing per key, allowing append-only lists and avoiding sorting overhead. Also, discuss how to handle out-of-order writes if they are possible.

1. Clarify Requirements

Ask about expected scale, timestamp ordering, concurrency needs, and whether updates can be out-of-order. Confirm that get should return the value at the largest timestamp <= given timestamp.

2. Choose Data Structures

Propose a hash map for O(1) key lookup, with each key mapping to a dynamic array or balanced BST of (timestamp, value) pairs. Explain that arrays support binary search for O(log n) get, while BSTs allow ordered operations.

3. Implement Operations

For set, append to the list if timestamps are increasing; otherwise, insert in sorted order. For get, binary search for the largest timestamp <= target and return the corresponding value.

4. Handle Edge Cases and Optimizations

Discuss handling missing keys, timestamps before the earliest entry, and memory growth. Consider compression, TTL, or periodic cleanup for old versions.

5. Address Concurrency and Scalability

Mention thread-safety using locks or concurrent data structures, and how the design scales with number of keys and versions. Discuss sharding if needed.

Key Points to Mention

Time complexity: O(1) average for set (if appending), O(log n) for get via binary search.
Space complexity: O(total number of versions) and potential need for compaction.
Use of binary search on sorted timestamps to find the floor entry.
Handling of duplicate timestamps (overwrite or keep latest).
Concurrency control: read-write locks or lock striping for thread safety.
Trade-offs between array (cache-friendly, simple) and balanced BST (efficient inserts if out-of-order).

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

Given N people's busy schedules as lists of non-overlapping sorted intervals, find all time slots when everyone is free.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one got me more than I'd like to admit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that each person's busy intervals are sorted and non-overlapping, then find the intersection of all free intervals by merging busy intervals across all people and computing the complement. Alternatively, use a sweep line or heap-based approach to efficiently find common free slots. Discuss time and space complexity and potential optimizations.

Pro tip: Mention that you can avoid merging all busy intervals by using a min-heap to track the earliest ending busy interval, which is more efficient when N is large. Also, confirm edge cases like empty schedules or no common free time.

1. Clarify the problem

Ask about input format, whether intervals are inclusive/exclusive, and if the output should be sorted. Confirm that each person's busy intervals are sorted and non-overlapping.

2. Choose an approach

Decide between merging all busy intervals and taking the complement, or using a sweep line with a heap to find common free slots. Explain the trade-offs.

3. Outline the algorithm

For the merge approach: flatten all busy intervals, sort by start time, merge overlapping intervals, then compute free slots between merged intervals. For the heap approach: push the first busy interval of each person into a min-heap, then iteratively advance the person with the earliest ending interval, tracking the maximum end time seen so far to identify gaps.

4. Analyze complexity

State time and space complexity. For merge approach: O(M log M) where M is total number of intervals. For heap approach: O(M log N) where N is number of people. Discuss which is better for large N.

5. Handle edge cases

Consider cases like no busy intervals, all busy, overlapping intervals across people, and no common free time. Also discuss if intervals can be very large or if there are many people.

Key Points to Mention

The importance of clarifying that intervals are sorted and non-overlapping per person.
The complement method: free intervals are gaps between merged busy intervals.
Using a min-heap to efficiently find the earliest ending busy interval across people.
Time complexity: O(M log M) for sorting all intervals vs O(M log N) for heap approach.
Space complexity: O(M) for storing all intervals or O(N) for heap.
Edge cases: empty schedules, no common free time, and intervals that touch at endpoints.

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