How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Data Engineer candidates at Amazon during technical interviews.

Solve Two String Problems | Amazon Coding Question

Quick Overview

This task evaluates string manipulation and encoding for generating unique Morse representations, along with sentence segmentation and combinatorial enumeration for producing all valid word-break sentences, focusing on transformation, deduplication, and decomposition skills.

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. Unique Morse Code Transformations You are given an array of lowercase English words, `words`. Each letter `'a'` through `'z'` maps to its standard Morse code representation. The translation of a word is formed by concatenating the Morse code of each of its letters in order. For example, the word `"cab"` translates to `"-.-..--..."` because: - `c -> -.-.` - `a -> .-` - `b -> -...` Return the number of distinct word translations among all words in the array. 2. Word Break II You are given a string `s` and a dictionary of valid words, `wordDict`. Insert spaces into `s` to form all possible sentences such that every segmented word appears in `wordDict`. Return all possible valid sentences in any order. Notes: - A dictionary word may be reused multiple times. - If multiple segmentations are possible, return all of them.

Quick Answer: This task evaluates string manipulation and encoding for generating unique Morse representations, along with sentence segmentation and combinatorial enumeration for producing all valid word-break sentences, focusing on transformation, deduplication, and decomposition skills.

Part 1: Unique Morse Code Transformations

Given a list of lowercase English words, convert each word into Morse code by replacing every letter with its standard Morse representation and concatenating the results. Return how many distinct Morse-code translations appear in the list.

Constraints

0 <= len(words) <= 100
1 <= len(words[i]) <= 12 for every word when the list is non-empty
Each word contains only lowercase English letters

Examples

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

Expected Output: 2

Explanation: gin and zen share one translation, while gig and msg share another.

Input: (["a"],)

Expected Output: 1

Explanation: A single word always contributes exactly one translation.

Input: ([],)

Expected Output: 0

Explanation: With no words, there are no translations.

Input: (["a", "a", "a"],)

Expected Output: 1

Explanation: Repeated identical words do not create new distinct Morse strings.

Hints

Store the Morse code for letters a to z in an array so you can index it with ord(ch) - ord('a').
Use a set to keep only unique translated strings.

Part 2: Word Break II

Given a string s and a dictionary of valid words wordDict, insert spaces into s to form every possible sentence such that each segmented word appears in the dictionary. Return all valid sentences sorted lexicographically for consistent testing. If no sentence can be formed, return an empty list.

Constraints

0 <= len(s) <= 20
0 <= len(wordDict) <= 1000
1 <= len(wordDict[i]) <= 10 for every dictionary word when the list is non-empty
s and all words in wordDict contain only lowercase English letters
A 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 exactly 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: Three different valid segmentations exist.

Input: ("catsandog", ["cats", "dog", "sand", "and", "cat"])

Expected Output: []

Explanation: No full segmentation reaches the end of the string.

Input: ("", ["a", "b"])

Expected Output: []

Explanation: For this problem, empty input returns no sentences.

Input: ("a", ["a", "aa"])

Expected Output: ["a"]

Explanation: The whole string itself is a valid dictionary word.

Hints

Think of the problem as: from each starting index, what sentences can be formed from the suffix beginning there?
Use memoization so you do not recompute all sentence combinations for the same index repeatedly.

Quick Overview