Katkat
Back

Solve two string DP/hash problems

AmazonData Scientist · Technical Screen
EasyData ScientistTechnical ScreenCoding & Algorithms

Last updated

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 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).