Implement string reduction and time map
Company: Grammarly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
In a coding interview, you are asked to solve two algorithm problems.
1. **String reduction with adjacent duplicates**
- Basic version: Given a string `s`, repeatedly remove any adjacent pair of equal characters until no such pair remains. Return the final string.
- Follow-up: Given a string `s` and an integer `k`, repeatedly remove any group of `k` adjacent equal characters until no more removals are possible. Return the final string.
- Example follow-up: if `s = "deeedbbcccbdaa"` and `k = 3`, the answer is `"aa"`.
2. **Time-based key-value store**
- Design a data structure that supports:
- `set(key, value, timestamp)`: store a value for a key at a given timestamp.
- `get(key, timestamp)`: return the value associated with the largest timestamp less than or equal to the given timestamp for that key. If no such timestamp exists, return an empty string.
- Assume timestamps passed to `set` are strictly increasing for each key.
- Implement both operations efficiently.
Write working code for both problems and explain the time and space complexity of your approach.
Overview: This question evaluates skills in string-processing algorithms and time-based data structure design, measuring competency in correctness, efficiency, and handling repeated pattern removals and temporal key-value retrieval.
String Reduction with K Adjacent Duplicates
Given a string `s`, repeatedly remove any group of `k` adjacent equal characters until no more removals are possible, then return the final string.
When `k = 2` this reduces to the classic problem of removing adjacent equal pairs until none remain. The general version removes runs of exactly `k` identical characters; after a removal, characters that become newly adjacent may form a new removable group.
Use a stack of `(character, count)` entries: for each incoming character, increment the count if it matches the top of the stack, otherwise push a new entry; whenever a count reaches `k`, pop that entry. The result is the concatenation of the remaining characters.
Example: `s = "deeedbbcccbdaa"`, `k = 3` -> `"aa"`.
Constraints
- 1 <= len(s) (the empty string is also valid input and returns the empty string)
- 2 <= k
- s consists of lowercase English letters
- Removals cascade: characters made adjacent by a removal may form a new group of size k
Examples
Input: ("deeedbbcccbdaa", 3)
Expected Output: "aa"
Explanation: Remove 'eee', then 'ccc', leaving 'ddbbbdaa'; remove the merged 'bbb', leaving 'dddaa'; remove 'ddd', leaving 'aa'.
Input: ("abbaca", 2)
Expected Output: "ca"
Explanation: k=2 basic case: remove 'bb' to get 'aaca', remove 'aa' to get 'ca'.
Hints
- Brute-force re-scanning after every removal is O(n^2/k). Maintain run lengths instead so each character is processed once.
- Keep a stack of (character, run_count). When the next character equals the top, increment its count; otherwise push a fresh (character, 1).
- As soon as a run_count hits exactly k, pop that entry — this automatically merges the now-adjacent runs on either side on the next iteration.
- Rebuild the answer by expanding each surviving (character, count) entry into character * count.
Time-Based Key-Value Store
Design a key-value store that records multiple values for a key at different timestamps and supports a floor lookup by time.
Support two operations:
- `set(key, value, timestamp)`: store `value` for `key` at time `timestamp`.
- `get(key, timestamp)`: return the value whose timestamp is the largest one that is less than or equal to the query `timestamp` for that key. If there is no such timestamp (or the key was never set), return the empty string `""`.
Timestamps passed to `set` for a given key are strictly increasing, so each key's timestamp list is already sorted — `get` is a binary search (floor) over that list.
This function harness models a session: you are given a list of operation names (`"set"` / `"get"`) and a parallel list of argument tuples. `set` arguments are `[key, value, timestamp]` and `get` arguments are `[key, timestamp]`. Replay the operations in order and return a list with one entry per operation: `None` for each `set`, and the returned value (a string, possibly `""`) for each `get`.
Constraints
- Timestamps passed to set for a given key are strictly increasing
- get returns the value for the largest timestamp <= the query timestamp
- get returns "" when the key is unknown or every stored timestamp is greater than the query
- 1 <= number of operations
Examples
Input: (["set", "get", "get", "set", "get", "get"], [["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]])
Expected Output: [null, "bar", "bar", null, "bar2", "bar2"]
Explanation: get(foo,1)=bar (exact). get(foo,3)=bar (floor of 3 is timestamp 1). After set at 4: get(foo,4)=bar2 (exact). get(foo,5)=bar2 (floor of 5 is timestamp 4).
Input: (["set", "set", "get", "get", "get", "get", "get"], [["love", "high", 10], ["love", "low", 20], ["love", 5], ["love", 10], ["love", 15], ["love", 20], ["love", 25]])
Expected Output: [null, null, "", "high", "high", "low", "low"]
Explanation: get at 5 precedes the first timestamp (10) -> "". At 10 -> high. At 15 floors to 10 -> high. At 20 -> low. At 25 floors to 20 -> low.
Hints
- Because set timestamps are strictly increasing per key, each key's timestamp list stays sorted automatically — no sorting needed.
- A get is a floor query: find the rightmost stored timestamp that is <= the query timestamp.
- Use binary search (bisect_right then step back one index) instead of a linear scan to keep get at O(log m).
- If bisect_right returns 0, the query timestamp precedes every stored timestamp, so return the empty string.
Community answers
Answer by hchen.fred
def solution(operations, args):
# operations: list of "set" / "get"
# args: parallel list; set -> [key, value, timestamp], get -> [key, timestamp]
# return a list: None for each set, the get result string for each get
# { foo: [(high, 10), (low, 20)] }
#. 5, 10, 15, 20, 25
# 10, 20 mid = 0 + 1-0/2 = 0 mid index = 0, timestamp for example is 15
# 1 3 5 7, 9
# for example timestamp is 8
store = {}
def set(key, value, timestamp):
if key not in store:
store[key] = [(value, timestamp)]
print(store)
else:
store[key].append((value, timestamp))
def get(key, timestamp):
if key not in store:
return ""
if timestamp < store[key][0][1]:
return ""
if timestamp > store[key][-1][1]:
return store[key][-1][0]
timestamps = store[key]
left = 0
right = len(timestamps) - 1
while left <= right:
mid = left + (right - left) // 2
if timestamps[mid][1] == timestamp:
return timestamps[mid][0]
elif timestamps[mid][1] < timestamp:
left = mid + 1
elif timestamps[mid][1] > timestamp:
right = mid - 1
return timestamps[right][0]
result = []
for op, arg in zip(operations, args):
if op == "set":
set(arg[0], arg[1], arg[2])
result.append(None) # becomes null in the judge
else:
result.append(get(arg[0], arg[1]))
return result