Reverse Words While Preserving Spaces
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a C++ function that reverses the order of words in a string.
Assume a word is any maximal sequence of non-space characters, and the input contains only the space character `' '` as whitespace.
**Part 1:** Return the words in reverse order, with leading and trailing spaces removed and exactly one space between adjacent words in the result.
**Part 2 (follow-up):** Modify the solution so that the original pattern of space blocks is preserved exactly. That means the lengths of the leading spaces, the spaces between word slots, and the trailing spaces must stay the same; only the word tokens should be reversed.
Example:
- Input: `" hello world again "`
- Part 1 output: `"again world hello"`
- Part 2 output: `" again world hello "`
Also be prepared to:
- write several edge-case test cases,
- analyze the time and space complexity of your approach,
- and discuss how to optimize the implementation.
Quick Answer: This question evaluates proficiency in string manipulation, tokenization, whitespace handling, and careful edge-case reasoning when reversing word order while either normalizing or preserving space patterns.
Reverse Words with Normalized Spaces
Reverse word order, trim leading/trailing spaces, and use exactly one space between words.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: (' hello world again ',)
Expected Output: 'again world hello'
Explanation: Prompt example part 1.
Input: ('single',)
Expected Output: 'single'
Explanation: One word.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.
Reverse Words Preserving Space Blocks
Reverse only word tokens while preserving every original space block length and position.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: (' hello world again ',)
Expected Output: ' again world hello '
Explanation: Prompt example part 2.
Input: ('a b',)
Expected Output: 'b a'
Explanation: Simple swap.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.