The round is one function with one graded follow-up, on the 45-minute phone screen. One report, from a candidate who went on to the onsite. Everything operates on the encoded string; decoding it defeats the question.
The original data B A A E E E C is encoded as B1A2E3C1: each character followed by how many times it repeats.
Given — the two functions as reported, char Find(int p) and char FindbyValue(char target, int left, int right), both working on the encoded data. In Python they are methods on an object built from the encoded string:
class RunLengthString:
def __init__(self, encoded: str): ...
def find(self, p: int) -> str:
"""The character at index p of the ORIGINAL data, without decoding."""
def find_by_value(self, target: str, left: int, right: int) -> str | None:
"""Follow-up: within original indices [left, right], the character larger than target."""
Part 1 — find()
Parse the runs, remembering that counts can have more than one digit, and walk them accumulating lengths until the run that contains position p. Prefix sums over the run lengths turn each later query into a binary search.
Part 2 — find_by_value()
The original data is now assumed sorted. Locate the runs containing left and right with the same prefix sums, and the answer is the first run character in that range that is lexicographically greater than the target.
The reported wall — none is reported. The candidate passed this screen and lost the loop later. Treat it as a fluency check on parsing and prefix sums.
Implement char FindByValue(char target, int left, int right): find the lexicographically larger character in the original data range [left, right], assuming the encoded input is sorted. (when: After candidate correctly implements Find(p))
| Approach | Notes |
|---|---|
| Prefix sum array precomputation | Build an array of cumulative counts from the encoded string upfront; allows O(log n) lookup via binary search for Find(p), but uses O(k) extra space where k is the number of distinct runs. |