Perplexity·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Interviewed for a software engineer role at Perplexity and got a system design question that looked deceptively straightforward on the surface. The core challenge was around a time-aware key-value store, which ended up being more nuanced than I expected once we got into the weeds on data structure choices and complexity tradeoffs.

Questions Asked (1)

Design a key-value store where set, get, and delete operations are each associated with a timestamp. A get at time t should return the most recent value from any set or delete whose timestamp is <= t, with deletes acting as tombstones.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

My first instinct was to just use a dict and I had to stop myself.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and assumptions, then propose a data structure that supports efficient timestamp-based operations. Discuss trade-offs between different approaches and outline how to handle edge cases and concurrency.

Pro tip: Emphasize that deletes are tombstones and explain how to avoid returning deleted values. Also, mention that timestamps can be used for versioning and that the store can be implemented with a balanced BST or a list of versions per key.

1. Clarify Requirements

Ask about expected operation frequency, timestamp granularity, concurrency needs, and whether timestamps are monotonically increasing. Confirm that deletes are tombstones and that get returns the latest value at or before time t.

2. Choose Data Structure

Propose storing a list of (timestamp, value) pairs per key, sorted by timestamp, with deletes represented as a special tombstone value. Alternatively, use a balanced BST or skip list for efficient range queries.

3. Design Operations

For set/delete, append the new (timestamp, value) pair to the key's list. For get, perform a binary search to find the latest timestamp <= t, and return the value if it's not a tombstone.

4. Analyze Complexity

Discuss time and space complexity: O(log n) for get via binary search, O(1) amortized for set/delete if appending, but O(n) space per key. Mention possible optimizations like periodic compaction.

5. Address Edge Cases and Trade-offs

Cover cases like get before any set, multiple sets at same timestamp, and concurrency. Discuss trade-offs between memory usage and query speed, and alternatives like LSM trees or versioned stores.

Key Points to Mention

Tombstones for deletes and how to handle them in get
Binary search for efficient timestamp lookup
Time and space complexity of operations
Handling of same timestamp for multiple operations
Concurrency control and consistency guarantees
Possible optimizations like compaction or using a balanced BST

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