Last week I ran an assisted Amazon virtual onsite (VO) interview for someone else. It was a behavioral round plus two coding questions.
First, the behavioral part:
- How do you handle difficulties at work?
- When your team runs into difficulties, how do you encourage them and come up with a way to solve the problem?
- Why did you choose Amazon?
Then 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 representation of each letter. For example, "cab" can be written as "-.-..--..." (that is, "-.-." + ".-" + "-..." concatenated together). We call this concatenation process a "word translation." Translate every word in words, and return the number of distinct translations.
The approach: iterate through each word, iterate 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've probably all grinded it before too.
Coding 2: Given a string s and a string dictionary wordDict, add spaces into s to build a sentence where every word in the sentence appears in the dictionary. Return all possible sentences, in any order. Note that the same word in the dictionary can be reused multiple times in a segmentation.
Building on top of dynamic programming, we modify the dp array so each element is a vector. For dp[i], each element j in it represents a word running from s[j] to s[i]. So the segmentation results for s end up stored as these (j, i) pairs, and by starting from dp[s.size()] and searching backward through these (j, i) pairs, splicing things together, you get s back out. Since dp[i] isn't necessarily size 1 (there isn't necessarily just one way to split), you need to write this recursively.
Coding 2 is basically a follow-up to Coding 1, and it counts as the hard one. The assisted session, as always, reliably got him through as usual.
Discussion
Loading comments…