← Perplexity Interview Insights

Perplexity·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say
May 2026

Summary

Interviewed for a software engineering role at Perplexity and got a system design question that was more nuanced than I expected. The core idea sounds simple but the edge cases pile up fast.

Questions Asked (1)

Q1

Design a key-value store where every set, get, and delete operation is associated with a timestamp. A get at time t should return the most recent value from any set or delete with timestamp <= t, where delete acts as a tombstone.

System DesignAlgorithms & Data StructuresTechnical Trade-offs
Author's notes

I started with the obvious thing, a sorted list per key where each entry stores the timestamp, the operation type, and the value.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: is this a single-node or distributed system? What are the expected read/write patterns and consistency needs? Then propose a versioned data model where each key maps to a list of (timestamp, value) pairs, with deletes represented as tombstones, and discuss efficient retrieval using binary search or tree structures.

Pro tip: Mention that tombstones can be garbage-collected after a safe time window if you can bound the maximum clock skew or query staleness, showing awareness of real-world storage trade-offs.

1. Clarify Requirements and Scope

Ask about scale, consistency, latency, and whether this is a single-node or distributed system. Confirm that timestamps are provided by the client or generated by the system.

2. Design the Data Model

Propose storing each key's history as a list of (timestamp, value) entries, where deletes are tombstones (e.g., null value). Ensure entries are sorted by timestamp.

3. Implement Operations

For set/delete, append a new entry with the given timestamp. For get, binary search for the largest timestamp <= t; if it's a tombstone, return not found, else return the value.

4. Optimize and Scale

Discuss indexing (e.g., B-tree, LSM-tree), compaction, and garbage collection of old versions. Consider distributed partitioning and replication if needed.

5. Address Trade-offs and Edge Cases

Talk about memory vs. read performance, handling out-of-order timestamps, clock skew, and concurrency control.

Key Points to Mention

  • Versioned data model with timestamp-indexed entries per key
  • Tombstones for deletes and how they affect get operations
  • Efficient lookup using binary search or tree structures
  • Garbage collection of old versions and tombstones
  • Handling out-of-order timestamps and clock skew
  • Trade-offs between memory usage and query latency

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