Amazon Intern Software Engineer Interview Experience — BQ Plus Two Coding Questions in One Virtual Onsite

I interviewed for an Amazon intern VO (virtual onsite) last week — it was BQ plus two coding questions. I've done a lot of Amazon intern interviews by now, and I'd already seen writeups for the other rounds and the OA before this one. A few of the BQ questions were ones I'd seen before.

First, the BQ part:

1. How do you handle difficulties at work
2. How do you encourage your team when they hit a difficulty, and come up with a way to solve it
3. Why did you choose Amazon

The coding part:

Coding 1: You're given an array of strings 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, "-.-." + ".-" + "-..." concatenated). We call this concatenation process a word's "transformation." Perform the transformation on every word in words, and return the number of distinct transformations.

The approach: iterate over each word, iterate over each letter in it, build its code, and use a set to record the distinct codes, then return the size of the set. This one's simple — you all should have ground into it too.

Coding 2: Given a string s and a string dictionary wordDict, add spaces into s to build a sentence such that every word in the sentence is in the dictionary. Return all such possible sentences, in any order. Note that the same word in the dictionary may be reused multiple times across the segmentation.

Building on dynamic programming, we modify the dp array so each element is a vector. For an element j in dp[i], it represents a word spanning from s[j] to s[i]. That way, the ways to split s end up stored as these (j, i) tuples, and by searching backward through them starting from dp[s.size()] and stitching the pieces back together, we recover s. Since the size of dp[i] isn't necessarily 1 (i.e., there isn't necessarily only one way to split), this needs to be written recursively.