← Grammarly Interview Insights

Grammarly·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026Remote

Summary

Had a technical phone screen for a software engineer role at Grammarly. The whole thing centered on one data structures problem, which felt pretty focused but also left me wondering if I'd done enough.

Questions Asked (1)

Q1

Design a time-based key-value store that supports storing multiple values per key at different timestamps, and retrieving the value associated with the largest timestamp that doesn't exceed a given query timestamp.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I got the brute-force working pretty fast, just scanning through stored values linearly, and part of me thought that was enough.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the requirements and constraints first, then propose a design using a hash map from keys to sorted lists of (timestamp, value) pairs. Explain how to implement set and get operations efficiently, leveraging binary search for retrieval, and discuss trade-offs between different data structures.

Pro tip: Mention that timestamps are strictly increasing per key, so appending to the list maintains sorted order, and binary search can be used for O(log n) retrieval. Also, discuss handling of edge cases like querying before the first timestamp or after the last.

1. Clarify Requirements and Constraints

Ask about expected operations, data size, timestamp range, and concurrency requirements. Confirm that timestamps are strictly increasing per key and that get should return the value with the largest timestamp <= query timestamp.

2. Choose Data Structures

Propose a hash map for O(1) key lookup, mapping each key to a list of (timestamp, value) pairs. Since timestamps are increasing, the list remains sorted, enabling binary search.

3. Implement Set Operation

For set(key, value, timestamp), append the new (timestamp, value) to the list for that key. If the key doesn't exist, create a new list. This is O(1) amortized.

4. Implement Get Operation

For get(key, timestamp), retrieve the list for the key. If empty, return empty string. Use binary search to find the largest timestamp <= the query timestamp. If found, return the corresponding value; else return empty string.

5. Analyze Complexity and Trade-offs

Discuss time complexity: set O(1), get O(log n) where n is number of timestamps for that key. Space O(total number of set calls). Mention alternatives like balanced BST or skip list, and trade-offs with memory and concurrency.

Key Points to Mention

  • Use a hash map from key to list of (timestamp, value) pairs.
  • Timestamps are strictly increasing per key, so appending maintains sorted order.
  • Binary search for get operation to achieve O(log n) time.
  • Handle edge cases: query timestamp before first entry, after last entry, or key not present.
  • Time complexity: set O(1), get O(log n); space O(n) for n set calls.
  • Consider concurrency and potential need for locking if multi-threaded.

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