Asked at Two Sigma
Theory: Algorithms Under a Complexity BoundRead the problem, hints and solution here. The editor needs a bigger screen: open this page on a laptop to write and run your code.
Available in Python and C++. You are solving it in Python. Switch to C++
Implement decode_feed(encoded), which decodes a string in a vendor's
run-length scheme and returns the decoded string.
A legacy market data vendor compresses its symbol directory with a custom run-length scheme. The spec, recovered from a fax, is short but exact.
An encoded string is a sequence of tokens with no separators. There are two token kinds:
~, then one or more lowercase
letters. The letter run extends until the next digit, the next ^, or the
end of the input. The token emits the letter run repeated count times:
3~ab emits ababab.^ followed by exactly one digit 1-9. It emits a
copy of the previous token's entire emission with every letter shifted
forward in the alphabet by that digit, wrapping z back to a: after
3~ab emitted ababab, the token ^2 emits cdcdcd. "Entire emission"
means everything that one token emitted, the whole repeated block, not
the whole decoded output so far. The shifted copy becomes the new
"previous emission", so shift tokens chain: each one shifts what the
token immediately before it emitted. In 2~ab^1^1, the first ^1 emits
bcbc and the second ^1 emits cdcd.The decoded output is the concatenation of every token's emission, in order. The input is always valid: it starts with a repeat token, counts are at least 1, and letter runs are non-empty.
def decode_feed(encoded: str) -> str: ...decode_feed("3~ab")
# 'ababab' (repeat "ab" three times)
decode_feed("2~ab^1")
# 'ababbcbc' ("abab", then "abab" shifted by 1)
decode_feed("2~ab^1^1")
# 'ababbcbccdcd' ("abab", then "bcbc", then "bcbc" shifted by 1)
decode_feed("1~zq2~x")
# 'zqxx' (letters end where the next count starts)12~q); decoded output stays under \(10^6\) characters.z to a.