How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Grammarly.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Grammarly during technical interviews.

Implement string reduction and time map | Grammarly Coding Question

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

Input: ("aabbcc", 2)

Expected Output: ""

Explanation: Every character is part of an adjacent pair; all are removed, leaving the empty string.

Input: ("pbbcggttciiippooaais", 2)

Expected Output: "ps"

Explanation: Cascading pair removals collapse the whole interior, leaving only the boundary characters 'p' and 's'.

Input: ("", 3)

Expected Output: ""

Explanation: Empty input yields empty output.

Input: ("a", 2)

Expected Output: "a"

Explanation: A single character can never form a group of size k, so it survives.

Input: ("aaa", 3)

Expected Output: ""

Explanation: Exactly k identical characters form one removable group.

Input: ("aaaa", 3)

Expected Output: "a"

Explanation: The first three 'a's form a group and are removed; one 'a' remains and cannot be removed.

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.

Input: (["get"], [["missing", 1]])

Expected Output: [""]

Explanation: Querying a key that was never set returns the empty string.

Input: (["set", "get"], [["a", "x", 100], ["a", 50]])

Expected Output: [null, ""]

Explanation: The only stored timestamp (100) is greater than the query (50), so there is no qualifying value -> "".

Input: (["set", "set", "set", "get", "get"], [["k", "v1", 1], ["k", "v2", 2], ["k", "v3", 3], ["k", 2], ["k", 100]])

Expected Output: [null, null, null, "v2", "v3"]

Explanation: get(k,2)=v2 (exact). get(k,100) floors to the largest timestamp 3 -> v3.

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.

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.