Amazon SDE Intern VO Interview Experience: Morse Code and Word Break II

Last week I had my Amazon intern VO. It consisted of behavioral questions (BQ) plus two coding problems. I’ve done quite a few Amazon intern interviews before, and the other rounds and OA were similar

Last week I had my Amazon intern VO. It consisted of behavioral questions (BQ) plus two coding problems. I’ve done quite a few Amazon intern interviews before, and the other rounds and OA were similar to previous interview experiences I had seen. We call this concatenation process the word’s translation. Translate every word in words and return the number of distinct word translations. The idea is straightforward: Iterate through each word. For each word, iterate through its letters and build the corresponding Morse code string. Use a set to store unique translations.

Return the size of the set. This is a relatively simple problem that you’ve probably seen while practicing. Coding 2 Given a string s and a dictionary of strings wordDict, add spaces in s to construct sentences such that every word in the sentence exists in the dictionary.

Return all possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation. The solution is based on dynamic programming. We modify the DP array so that each dp[i] is a vector. For each element j in dp[i], it represents a valid word from s[j] to s[i]. In other words, we store valid (j, i) splits. After building the DP structure, we start from dp[s.size()] and backtrack through these (j, i) pairs to reconstruct all possible sentences. Since dp[i] may contain multiple valid splits (i.e., more than one way to segment), we need to use recursion (or DFS) to generate all combinations.