Quick Overview

This question set evaluates string-processing and algorithmic problem-solving skills, including encoding and transformation for unique representations and dynamic programming, memoization, and backtracking for enumerating all valid segmentations.

Solve two string DP/hash problems

Company: Amazon

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

Solve the following two coding questions. ## 1) Unique Morse Code Transformations You are given an array of strings `words` (lowercase English letters). Using the **standard International Morse code mapping** for letters `a`–`z`, each word can be translated by concatenating the Morse codes of its letters. Example: `"cab" -> "-.-." + ".-" + "-..." = "-.-..--..."`. **Task:** Return the number of **distinct** Morse-code translations among all words in `words`. **Output:** an integer count. ## 2) Word Break II (All segmentations) You are given a string `s` and a dictionary `wordDict` (a list/set of strings). **Task:** Insert spaces into `s` to form **all possible sentences** such that: - Every token is in `wordDict`. - The same dictionary word may be reused multiple times. Return **all valid sentences** in any order. **Output:** a list of strings, where each string is one valid spaced sentence. Notes: - If no segmentation is possible, return an empty list. - You should handle cases where there are many solutions efficiently (avoid repeated recomputation).

Overview: This question set evaluates string-processing and algorithmic problem-solving skills, including encoding and transformation for unique representations and dynamic programming, memoization, and backtracking for enumerating all valid segmentations.

Read the full Amazon Data Scientist interview experience this question came from

Part 1: Unique Morse Code Transformations

You are given a list of lowercase English words. Translate each word into Morse code by concatenating the code for each letter, then return how many distinct translated strings exist. Use the standard Morse mapping for letters `a` to `z`: `['.-', '-...', '-.-.', '-..', '.', '..-.', '--.', '....', '..', '.---', '-.-', '.-..', '--', '-.', '---', '.--.', '--.-', '.-.', '...', '-', '..-', '...-', '.--', '-..-', '-.--', '--..']`.

Constraints

  • `0 <= len(words) <= 1000`
  • `0 <= len(words[i]) <= 20`
  • Each character in every word is a lowercase English letter from `a` to `z`.

Examples

Input: (['gin', 'zen', 'gig', 'msg'],)

Expected Output: 2

Explanation: `'gin'` and `'zen'` map to the same Morse string, and `'gig'` and `'msg'` map to another one.

Input: (['a'],)

Expected Output: 1

Explanation: A single word always contributes exactly one translation.

Hints

  1. Store the 26 Morse encodings in an array so letter `c` can be found by index `ord('c') - ord('a')`.
  2. A hash set is enough to track unique translated strings.

Part 2: Word Break II (All Segmentations)

You are given a string `s` and a dictionary `wordDict`. Insert spaces into `s` to form all possible sentences such that every token is in `wordDict`. A dictionary word may be reused multiple times. Return all valid sentences in any order. If no segmentation is possible, return an empty list. For this problem, if `s` is empty, return an empty list.

Constraints

  • `0 <= len(s) <= 20`
  • `0 <= len(wordDict) <= 1000`
  • Each word in `wordDict` has length at least 1.
  • All strings contain only lowercase English letters.
  • The same dictionary word may be reused multiple times.

Examples

Input: ('catsanddog', ['cat', 'cats', 'and', 'sand', 'dog'])

Expected Output: ['cat sand dog', 'cats and dog']

Explanation: There are two valid ways to split the string.

Input: ('pineapplepenapple', ['apple', 'pen', 'applepen', 'pine', 'pineapple'])

Expected Output: ['pine apple pen apple', 'pine applepen apple', 'pineapple pen apple']

Explanation: All three segmentations are valid and reuse of dictionary words is allowed.

Hints

  1. Think in terms of suffixes: what sentences can be formed starting at index `i`?
  2. Use memoization so each starting index is solved once instead of recomputing the same suffix repeatedly.

Loading coding console...