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
-
Short Introduction
-
Small discussion on projects.
-
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!
Round 2: 2nd Technical Interview
-
Introduction
-
10-15 min discussion on internships, projects. What was my role during the internship specifically? Technologies used in projects, why one over the other?
-
Coding problems (3):
a) Given a target node and an integer k, return a list of all the values of nodes that at distance k.
Example:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output: [7,4,1]
Explaination: You can find 7 and 4 via going down the descendants of TreeNode* 5 and can find 1 via the parent of 5;
Illustration:
5->2->7
5->2->4
5->3->1
Approach:
First create the parent pointers using a hashmap, then use a bfs traversal starting with target node in the queue and a distance 0. Then, add the 3-directional siblings of queue's front to the queue and incremented the distance by 1 at every iteration of queue. We break out of the bfs when either queue is empty or diatance == k. Finally, all the elements left in the queue are our required elements.
Summary:
Solved the question, it took half an hour to give the approach and code. Also, made a small mistake in the code which I was able to resolve with interviewer's guidance.
Problem Link: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
b) Given a list of numbers representing length of ropes. Connect the ropes with minimum cost, if cost to connect two ropes is equal to the sum of their lengths.
Example:
Input: [1, 2, 3, 6, 8]
Output: 41
Explaination: Cost of all the joins : 3 + 6 + 12 + 20 = 41
Illustration:
1 + 2 = 3
3 + 3 = 6
6 + 6 = 12
12 + 8 = 20
Approach:
Create a priority queue (min heap) and all the elements in it. Add the two smallest ropes from the priority queue, add their sum to the cost as well as insert their summation back into the priority queue. Finally when there is only one lement in the priority queue, return the accumulated cost.
Summary:
Gave the exact approach within the first 30 seconds of the question. The interviewer seemed to like my fast response but then again gave me another question.
c) Given an integer 1 <= n <= 10^5 and integer 'm'. The task is to tell the max step we can reach starting from 1, if at every step 'x', our 'm' reduces by pow(x, 2). And we can not move ahead if m becomes 0.
Example:
Input: n = 10^5, m = 10
Output: 3
Explaination: m at every step:
1 : 10 - 1 = 9 -> move ahead
2 : 9 - 4 = 5 -> move ahead
3 : 5 - 9 = -4 -> return;
Approach:
Gave a linear approach but the interviewer wasn't happy with the O(n) time complexity and asled me optimize it. With the help of a couple of hints, I came with a binary search solution which reduced the time complexity to O(log(n)). After which, I managed to further optimize it to a O(log(sqrt(m)) solution.
Summary:
The interview seemed to satisfied with the last version of code that I wrote, so all's well that ends well.
Synopsis:
Solved all the given problems, though took some extra time. The interviewer did gave me a few hints here and there and I was able to understand and utilise them. So, overall, it turned out to be yet another pleasant interview.
Round 3: Technical + Cultural Fit Interview
-
Introduction (4 min) : Interviwer's and then mine.
-
Coding problem (1):
a) Given a string 's' and a string 't'; find the smallest substring in 's' that contains 't' as a subsequence.
Example:
Input: s = "amazonindia", t = "main"
Output: mazonin
Explaination: "mazonin" is smallest substring from striing 's' that contains all the letters of string 't'- 'm', 'a', 'i', 'n'.
Summary:
Solved the question, it took half an hour to give the approach and code. Also explained a sliding window based optimised approach but didn't code that completely.
Problem Link: Not on leetcode. Try googling : find-the-smallest-window-in-a-string-containing-all-characters-of-another-string
3. Behavioural Questions (3):
This section began with a thorough discussion of my internships, including :
* What were my day-to-day responsibilites in the internships?
* What technologies did I work with and some basic questions around them, like why prefer one framework over another, etc.?
* Any highlights during internship period such as accomplishents or learnings?
Then came the Amazon's well known Behavioural Questions based on their Peculiar Leadership Principles. They also do cross-questioning in this section. Mine were based on the following leadership principles:
* Customer Obsession
* Bias for Action
Synopsis:
Solved the given coding problem. The interviewer was pleasant, had some interactive discussions around internships and leadership principles. Rembered to incorporate STAR (Situation-Task-Action-Result) methodolgy in my answers. So, all-in-all a decent interview experience.
P.s. : Received the FTE offer in April, joined as an SDE-1 few months later!