← Navan Interview Insights

Navan·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026Remote

Summary

Navan technical phone screen with a data structures problem. Pretty standard stuff but the binary search angle tripped me up more than I expected.

Questions Asked (1)

Q1

Design a time-based key-value store that supports storing a value with a timestamp and retrieving the value at or before a given timestamp.

Algorithms & Data StructuresSystem Design
Author's notes

I knew the per-key list approach pretty fast, the set operation was trivial.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: operations are set(key, value, timestamp) and get(key, timestamp) returning the value with the largest timestamp ≤ given timestamp. Then propose a hash map from key to a list of (timestamp, value) pairs, keeping timestamps sorted, and use binary search for efficient retrieval.

Pro tip: Mention that timestamps are strictly increasing for each key, so appending maintains sorted order; also discuss trade-offs between binary search and tree-based structures for concurrent or distributed scenarios.

1. Clarify requirements and constraints

Ask about expected operations, timestamp uniqueness, concurrency needs, and scale (number of keys, timestamps per key).

2. Choose data structures

Propose a hash map for O(1) key lookup, with each key mapping to a dynamic array of (timestamp, value) pairs kept sorted by timestamp.

3. Implement set operation

Append the new (timestamp, value) to the key's list; since timestamps are strictly increasing, the list remains sorted.

4. Implement get operation

Use binary search to find the largest timestamp ≤ the given timestamp and return its value, or empty if none exists.

5. Analyze complexity and discuss extensions

State time complexities: O(1) for set, O(log n) for get; space O(n). Mention potential optimizations like using a balanced BST or handling concurrency.

Key Points to Mention

  • Hash map for key lookup and array for timestamp-ordered values
  • Binary search to find the floor timestamp efficiently
  • Timestamps are strictly increasing per key, so appending maintains sorted order
  • Time complexity: O(1) set, O(log n) get; space O(n)
  • Edge cases: no timestamp ≤ given, duplicate timestamps (if allowed), empty store
  • Scalability considerations: sharding, concurrency, or using a tree-based structure

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