← Grammarly Interview Insights

Grammarly·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Grammarly SWE interview, technical phone screen focused on data structures. One question, pretty clean problem but the optimal path requires you to actually know binary search cold.

Questions Asked (1)

Q1

Design a time-based key-value store that supports storing multiple values per key at different timestamps, and retrieving the most recent value at or before a given timestamp.

Algorithms & Data StructuresSystem Design
Author's notes

I got a working solution going with a linear scan first, which they accepted but you could tell they wanted more.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the requirements: operations include set(key, value, timestamp) and get(key, timestamp), where get returns the value with the largest timestamp <= given timestamp. Then propose a design using a hash map from key to a list of (timestamp, value) pairs, keeping each list sorted by timestamp (either by appending since timestamps are increasing, or by inserting in order). For get, use binary search to find the rightmost timestamp <= the query timestamp.

Pro tip: Mention that timestamps are strictly increasing for set operations, so you can append to the list in O(1) and avoid sorting; this shows attention to problem constraints and can lead to a more efficient solution.

1. Clarify requirements and constraints

Ask about the range of timestamps, whether they are unique per key, and if set operations are guaranteed to have increasing timestamps. Confirm the expected time complexity for get and set.

2. Choose data structures

Propose a hash map where each key maps to a list (or array) of (timestamp, value) pairs. Explain that the list will be kept sorted by timestamp, either by appending (if timestamps are increasing) or by inserting in order.

3. Design set operation

For set, append the new (timestamp, value) pair to the list for the key. If timestamps are not guaranteed increasing, insert in the correct position to maintain sorted order.

4. Design get operation

For get, retrieve the list for the key and use binary search to find the largest timestamp <= the given timestamp. Return the corresponding value, or empty string if none exists.

5. Analyze complexity and edge cases

Discuss time complexity: set O(1) if appending, O(n) if inserting; get O(log n) due to binary search. Mention edge cases: non-existent key, timestamp before all stored timestamps, and duplicate timestamps (if allowed).

Key Points to Mention

  • Use a hash map for O(1) key lookup.
  • Store values in a list sorted by timestamp to enable binary search.
  • Leverage strictly increasing timestamps to append in O(1) for set.
  • Use binary search (e.g., bisect) for get to achieve O(log n) time.
  • Handle edge cases: key not found, no timestamp <= query, and empty store.
  • Discuss trade-offs: memory vs. speed, and potential for using a balanced BST if timestamps are not increasing.

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