Status: 4th year ECE student at Tier 2 college
Position: SDE1 at Amazon
Round: 1
Location: India
Date: Feb 2022
Opportunity type: On Campus

Round 1: 1st Technical Interview

1. Short Introduction

2. Small discussion on projects.

3. Coding problem:
   Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Used a hashset to store all the strings in the wordList and another for keeping track of all the visited strings. Then, starting from beginWord, with the help of a bfs traversal, added all the sibling strings (i.e. strings with only one transformation from current string) which were present in our hashset and not present in visited set to the queue. After that, just repeated these steps until we either reached the endWord or we exhausted all the elements in the hashset and emptied the queue.

Synopsis:
Solved the question, it took me 20 minutes to come up with the approach and another 20 to code and explain. The interview did have some follow-up questions about the complexity of the code which I did manage to answer correctly. The interviewer was also kind and supportive, so overall it turned out to be a really good experience!

Will update on the status of further rounds. Happy Coding! :)


Edit: Got an invite for round 2. You may find my round 2 experience here.