Implement encode/decode for list of strings
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a list of strings (may include digits and symbols). Implement two methods:
- `encode(List<String> input) -> String`: converts the list into a single encoded string.
- `decode(String encoded) -> List<String>`: converts the encoded string back into the original list.
Use the following encoding scheme: for each string `s`, append `<len><s><sep>` to the output, where `<len>` is the decimal length of `s` (number of characters), and `<sep>` is the character `#`.
Example:
Input: `["foo", "lis", "jljl", "12345678901"]`
Lengths are `3, 3, 4, 11`, so the encoded string is:
`"3foo#3lis#4jljl#1112345678901#"`
Implement both functions so that for any valid input list, `decode(encode(input))` returns the original list.
Quick Answer: This question evaluates a candidate's proficiency in string manipulation and serialization techniques, focusing on designing an invertible encode/decode scheme for lists of strings.
Implement a serializer and deserializer for a list of strings. On this platform, write one function `solution(mode, data)`:
- If `mode == "encode"`, `data` is a list of strings and you must return one encoded string.
- If `mode == "decode"`, `data` is an encoded string and you must return the original list.
Use this encoding rule for each string `s`: append `str(len(s)) + s + "#"` to the result. Here `len(s)` is the number of characters in `s`, and `#` is the record separator.
Example: `["foo", "lis", "jljl", "12345678901"]` becomes `"3foo#3lis#4jljl#1112345678901#"`.
Your implementation must satisfy `solution("decode", solution("encode", arr)) == arr` for every valid input.
Note: original strings may contain digits, spaces, and other symbols, but they will not contain `#`.
Constraints
- 0 <= number of strings <= 10^4
- The total number of characters across all input strings is at most 2 * 10^5
- Each original string may contain digits, spaces, and symbols, but it does not contain '#'
- For `decode`, the input string is guaranteed to be a valid encoding produced by the same scheme
Examples
Input: ("encode", ["foo", "lis", "jljl", "12345678901"])
Expected Output: "3foo#3lis#4jljl#1112345678901#"
Explanation: Each string is written as `<length><string>#`: `3foo#`, `3lis#`, `4jljl#`, and `1112345678901#`.
Input: ("decode", "3foo#3lis#4jljl#1112345678901#")
Expected Output: ["foo", "lis", "jljl", "12345678901"]
Explanation: Split at each `#`, then recover the length prefix inside each block.
Hints
- When decoding, first find the next `#`. Everything before it belongs to exactly one encoded block.
- If a block before `#` has total length `m`, and the length prefix has `d` digits, then the original string length must be `m - d`.