Quick 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.

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.

Quick Answer: 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

  1. Brute-force re-scanning after every removal is O(n^2/k). Maintain run lengths instead so each character is processed once.
  2. Keep a stack of (character, run_count). When the next character equals the top, increment its count; otherwise push a fresh (character, 1).
  3. 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.
  4. 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

  1. Because set timestamps are strictly increasing per key, each key's timestamp list stays sorted automatically — no sorting needed.
  2. A get is a floor query: find the rightmost stored timestamp that is <= the query timestamp.
  3. Use binary search (bisect_right then step back one index) instead of a linear scan to keep get at O(log m).
  4. If bisect_right returns 0, the query timestamp precedes every stored timestamp, so return the empty string.

Loading coding console...