Recover Sorted Digits from Scrambled English Number Words
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A string contains a shuffled collection of letters from the English digit names `zero`, `one`, `two`, `three`, `four`, `five`, `six`, `seven`, `eight`, and `nine`. Recover the digits and return them in ascending order, preserving repetitions.
Implement `recover_digits(letters: string) -> string`.
### Constraints & Assumptions
- Input has at most 100000 lowercase ASCII letters and is guaranteed to be a valid multiset of complete English digit names. The empty input represents no digits.
- Word boundaries and letter order have been lost. This is not substring segmentation of concatenated intact words.
- Output contains only `0` through `9`, sorted nondecreasingly, with one digit per recovered word.
- Aim for O(input length + output length) time and constant-sized counting state, apart from output.
### Examples
```text
letters = "owoztneoer"
result = "012"
```
```text
letters = "fviefuro"
result = "45"
```
The reported follow-up replaces English digit names with arbitrary customer-provided words for digits 0–9. Explain whether your reasoning still works, what would establish unique recoverability, and how you would detect or report ambiguous mappings. Do not assume arbitrary words contain a distinguishing letter. For example, assigning word `a` to one digit and word `aa` to another can make the same letter multiset represent different digit sequences.
```hint Use structure specific to the fixed vocabulary
Some letters initially occur in only one digit name. After removing those words' contributions, other letters can become distinguishing.
```
Overview: Recover sorted digits from scrambled English number-word letters, including repeats, and analyze why arbitrary customer vocabularies may lose unique recoverability.
Read the full Microsoft Software Engineer interview experience this question came from
A string contains a shuffled collection of letters from the English digit names `zero`, `one`, `two`, `three`, `four`, `five`, `six`, `seven`, `eight`, and `nine`. Recover the digits and return them in ascending order, preserving repetitions.
Implement `recover_digits(letters: string) -> string`.
### Constraints & Assumptions
- Input has at most 100000 lowercase ASCII letters and is guaranteed to be a valid multiset of complete English digit names. The empty input represents no digits.
- Word boundaries and letter order have been lost. This is not substring segmentation of concatenated intact words.
- Output contains only `0` through `9`, sorted nondecreasingly, with one digit per recovered word.
- Aim for O(input length + output length) time and constant-sized counting state, apart from output.
### Examples
```text
letters = "owoztneoer"
result = "012"
```
```text
letters = "fviefuro"
result = "45"
```
The reported follow-up replaces English digit names with arbitrary customer-provided words for digits 0–9. Explain whether your reasoning still works, what would establish unique recoverability, and how you would detect or report ambiguous mappings. Do not assume arbitrary words contain a distinguishing letter. For example, assigning word `a` to one digit and word `aa` to another can make the same letter multiset represent different digit sequences.
```hint Use structure specific to the fixed vocabulary
Some letters initially occur in only one digit name. After removing those words' contributions, other letters can become distinguishing.
```
Constraints
- 0 <= input length <= 100000; letters are lowercase ASCII.
- The input is guaranteed to be a valid multiset of complete fixed English digit names zero through nine.
- Letter order and word boundaries are arbitrary; empty input represents no digits.
- Return digits in nondecreasing order, preserving multiplicity.
Examples
Input: ('owoztneoer',)
Expected Output: '012'
Explanation: The letters contain zero, one and two without intact boundaries.
Input: ('fviefuro',)
Expected Output: '45'
Explanation: Shared f is resolved after removing four.