Quick Overview

This question evaluates a candidate's ability to design reversible string encodings that handle arbitrary characters and edge cases, testing competency in string manipulation, data serialization, and robustness.

Implement delimiter-free string codec

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Design an encoder/decoder for a list of strings. - Implement two functions: - `encode(strings: List[str]) -> str` - `decode(blob: str) -> List[str]` - The encoding must be reversible for any input strings (strings may be empty and may contain arbitrary characters). - You are **not allowed to use special delimiter symbols** (i.e., you should not rely on a separator character that might appear in the data). - The encoded output should be a single string. Explain your approach and analyze time/space complexity.

Quick Answer: This question evaluates a candidate's ability to design reversible string encodings that handle arbitrary characters and edge cases, testing competency in string manipulation, data serialization, and robustness.

Design a reversible codec for a list of strings without relying on any separator character that could also appear inside the data. Because this platform expects a single callable, implement a function `solution(operation, data)` with two behaviors: - If `operation == "encode"`, `data` is a list of strings and you must return one encoded string. - If `operation == "decode"`, `data` is an encoded string and you must return the original list of strings. A correct approach is to store each string as a fixed-width length header followed immediately by the raw string contents. For example, with a 10-character zero-padded length field, `"cat"` becomes `"0000000003cat"`. Since the length header always uses exactly 10 characters, the decoder always knows where the next string starts and how many characters to read, even if the original strings contain digits, punctuation, spaces, or are empty.

Constraints

  • 0 <= number of strings <= 10^4
  • 0 <= length of each string <= 10^6
  • All characters are allowed inside the original strings, including digits, spaces, punctuation, and empty strings
  • The input to `decode` is guaranteed to be a valid string produced by the encoder
  • Use a delimiter-free strategy; do not depend on separator symbols appearing nowhere in the data

Examples

Input: ("encode", ["lint", "code", "love", "you"])

Expected Output: "0000000004lint0000000004code0000000004love0000000003you"

Explanation: Each word is stored as a 10-digit length followed by the word itself.

Input: ("decode", "0000000004lint0000000004code0000000004love0000000003you")

Expected Output: ["lint", "code", "love", "you"]

Explanation: Reading 10 characters at a time for lengths reconstructs the original list.

Hints

  1. If a separator can appear inside the data, store each string's length instead of searching for a marker.
  2. Make decoding simpler by using a fixed-size length header, so you always know exactly where to read the next length.

Loading coding console...