Amazon Data Engineer Interview Experience — BQ Plus Two Coding Questions in a Referral VO

Last week's Amazon VO, done through a referral, was BQ plus two coding questions.

First the BQ part:

1. How do you handle it when you run into difficulties at work?
2. When your team runs into difficulties, how do you encourage them and come up with a way to solve it?
3. Why did you choose Amazon?

Coding part:

Coding 1: You're given a string array words. Each word can be written as the concatenation of the Morse code for each of its letters. For example, "cab" can be written as "-.-..--..." (that is, the concatenation of "-.-." + ".-" + "-..."). We call this concatenation process a "word translation." Perform the word translation on every word in words, and return the number of distinct translations.

The idea here: go through each word, go through each letter of the word, build up its code, use a set to record the distinct codes, then return the size of the set. This one's simple — you all have probably grinded it before too.

Coding 2: Given a string s and a string dictionary wordDict, add spaces into s to build a sentence so that every word in the sentence appears in the dictionary. Return all such possible sentences, in any order.

Note that the same word in the dictionary can be reused multiple times across the segmentation.

Building on the DP approach, we modify the dp array so each element is a vector. For the element j inside dp[i], it represents a word running from s[j] to s[i]. That way, the ways to split s get stored in these (j, i) pairs. Starting from dp[s.size()] and searching backward through these (j, i) pairs, then stitching them back together, gives you s. Since the size of dp[i] isn't necessarily 1 (i.e. there isn't necessarily just one way to split it), you need to write this recursively.

T2 is basically a follow-up to T1, and it counts as a hard one. The referral round stayed steady as always, though — I still got the pass.