Amazon·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

Jul 2026

Summary

Amazon SWE coding round with a string compression problem that looked deceptively simple but had enough edge cases to keep you honest. The encoding rules were a bit unusual and I had to think carefully about when to apply RLE versus just leaving characters as-is.

Questions Asked (1)

Given a string, implement an encoder and decoder using a hybrid run-length encoding strategy: apply RLE only when there are 8 or more consecutive identical characters, otherwise keep the raw characters. Any leftover run that doesn't hit 8 should still use RLE if it can.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The tricky part was the 'bbbbbbbbbbb' case, 11 b's that should come out as '8b3b'.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the encoding format first, then design a two-pass algorithm: one pass to identify runs of 8 or more identical characters, and another to build the encoded string with markers. Implement encode and decode as inverse operations, ensuring the decoder can unambiguously parse the encoded format.

Pro tip: Define a clear escape mechanism for the marker character itself, and discuss how to handle edge cases like runs that are exactly 8 or longer than 9 (e.g., 10+ characters) to show attention to detail.

1. Clarify requirements and format

Ask about the expected output format, whether the marker character can appear in input, and how to handle runs longer than 9. Confirm that runs of exactly 8 should be encoded.

2. Design encoding scheme

Choose a marker (e.g., '#') and define the encoded run as marker + count + character. For raw characters, output them as-is, but escape the marker if it appears in the input.

3. Implement encoder

Scan the string, count consecutive identical characters. If count >= 8, emit marker + count + char; otherwise, emit the raw characters (with escaping for the marker).

4. Implement decoder

Scan the encoded string. When encountering the marker, read the count and character, then expand; otherwise, output the character as-is (handling escape sequences).

5. Test and discuss trade-offs

Test with edge cases: runs of 7, 8, 9, 10+, marker in input, empty string. Discuss time/space complexity and potential improvements.

Key Points to Mention

Choice of marker character and escaping mechanism to avoid ambiguity
Handling runs of exactly 8 and runs longer than 9 (e.g., multi-digit counts)
Time and space complexity: O(n) for both encode and decode
Edge cases: empty string, no runs, marker in input, runs at start/end
Inverse property: decode(encode(s)) == s for all valid inputs
Trade-offs: simplicity vs. compression efficiency, and potential for other RLE variants

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.