Solve two string problems
Company: Amazon
Role: Data Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are asked to solve the following two coding problems.
1. **Count unique Morse code translations**
You are given an array of lowercase English words, `words`.
Each letter maps to standard Morse code as follows:
- `a -> .-`
- `b -> -...`
- `c -> -.-.`
- `d -> -..`
- `e -> .`
- `f -> ..-.`
- `g -> --.`
- `h -> ....`
- `i -> ..`
- `j -> .---`
- `k -> -.-`
- `l -> .-..`
- `m -> --`
- `n -> -.`
- `o -> ---`
- `p -> .--.`
- `q -> --.-`
- `r -> .-.`
- `s -> ...`
- `t -> -`
- `u -> ..-`
- `v -> ...-`
- `w -> .--`
- `x -> -..-`
- `y -> -.--`
- `z -> --..`
The translation of a word is the concatenation of the Morse codes of its letters. For example, `"cab"` becomes `"-.-..--..."` because `c -> -.-.`, `a -> .-`, and `b -> -...`.
Return the number of **distinct** word translations among all words in the input array.
2. **Return all valid word-break sentences**
You are given a string `s` and a dictionary of words `wordDict`.
Insert spaces into `s` to form all possible sentences such that every token is a word in `wordDict`. The same dictionary word may be reused multiple times.
Return **all** valid sentences in any order.
Example:
- `s = "catsanddog"`
- `wordDict = ["cat", "cats", "and", "sand", "dog"]`
- Output: `["cats and dog", "cat sand dog"]`
Design correct and efficient algorithms for both problems, and be prepared to discuss time and space complexity.
Quick Answer: This prompt evaluates string-processing competencies: the Morse translation task tests mapping and uniqueness detection through encoding and deduplication, while the word-break task assesses segmentation and combinatorial enumeration requiring dynamic programming and memoization skills.
