Status: ME from Tier 1 CS 3+ yrs Exp
Position: Software Engineer 3 at Walmart
Location: Bangalore
I interviewed for SDE II role for AWS in Sept-Oct 2022 for multiple locations in the EU/UK. There were a total of 6 rounds: 1 OA + 1 Telephonic + 4 interviews. The entire process took more than a moth.
Online Assesment:
2 questions, medium difficulty level.
Telephonic Round:
It consisted of current project related questions and 2 Amazon LP and than he asked 1 DSA questions. Basically it was a graph based question which can be solved using both DFS and BFS. It was like an adjacency list for a social network was given like below:
A -> B, C, E, F
B -> C, A
C -> A, B, D
D -> C
....
You'll have to find the distance between 2 nodes. Discussions around time and space complexity. Then he tried to complicate things a bit by saying how would you store the graph if it was for a large social networking site like Facebook. what would you choose BFS or DFS and why?
I coded a BFS based solution as in BFS we move level by level and once we find the node we are sure that it's the minimum distance. Initially I suggested DFS and we would keep a variable min_dist and keep updating it. But this wouldn't perform well in the worst case and BFS would perform better!
Result: Cleared this round and moved to virtual onsite interviews.
1st Round: (LP + HLD)
First Round was with the Hiring Manager. He asked many many LP questions and a lot about my previous experience. Then in the last 20-25 mins he asked me the HLD for a video streaming platform like Netflix. We had a really good discussion and covered topics like video encoding, storage, showing last 10 videos watched by user, top 10 recommendations based on view count and how to scale this for millions of users. I discussed some concepts like load balancing, sharding, event queues, caching, etc. He extended the interview for 5 mins and I really enjoyed the discussion. I felt this round went awesome.
2nd Round: (LP + DSA)
First 30 mins lots and lots of LP questions. Niether he was able to understand my answers nor was I able to understand what he was not able to understand. He was rude and his English was not good so communication was a problem. Next after 30 mins we moved onto a coding question.
If the input word array/list is:
['car','super','supercar','hero','superhero','superherocar','spring','flower','springflower','winter','cool']
Please return me the array as below:
[['car','super', 'supercar'],
['super', 'hero', 'superhero'],
['car','super','hero','superherocar'],
['spring', 'flower','springflow']]
Variation of https://leetcode.com/problems/concatenated-words
I gave a brute force solution using hashmap for this. That was not the solution he was looking for as expected and coming up with a trie based optimised approach in 15-20 mins I don't think was really feasible for me.
3nd Round: (LP + DSA)
A good discussion around projects and my work experience along with a ton of LP questions. The discussion was good and the interviewer seemed satisfied with my answers. Next we moved onto a DSA based question in which he said that assume that we are building a gaming application in which if we have cities and suppose a user is at city A and wants to go to city B. Then we must return True or False indicating that the user can reach from city A to B or not. So I suggested we would construct a graph and then do iterative BFS based approach using adjacency list which would have a time complexity of O(V + E). But he said that's not the solution he was looking for and he wanted me to optimise it since in a gaming application such high latencies won't be accepted. He wanted a O(1) solution he mentioned. So to optimise a bit further I suggested caching the results for user pairs which would speed up things. He was fine with it but he constantly pushed me for a O(1) solution. I wasn't able to come up with a O(1) solution. so he asked me to code the caching based BFS solution. He seemed fine with it.
Let me know in the comments if you know of a O(1) solution.
4th Interview: (LP + DSA)
In this round mostly focus was on my previous work, we had detailed discussion and then focus shifted to LP.
He also asked 1 DSA question which is the same as this :
Create a number pool 1...infinity which has 2 methods..
CheckIn(someNumber) and checkout()
Checkout should give the min number checked in.
Checkin should add to numberPool if number doesnt exist.
Intially all numbers 1..infinity are available.
eg:
- checkout() gives 1
- checkout() gives 2
- Checkin(1)
- checkout() gives 1 now.
I asked some clarifying questions like what happens if user tries to checkin a duplicate number, what should be returned if the pool is empty, etc. I coded a min-heap based solution and covered all edge cases. Then we had a discussion regarding time complexity. Finally at the end I asked some general questions and we concluded the interview. This round went pretty good as well.
It has been 10 days and I haven't received any feedback/rejection mail. I did multiple follow ups but no reply from them. Now I don't even care about the result just would be good to get a feedback. In total I spent 7 hours for this process. I think the online round was for 2 hours then 1 hour phone screen and then 4 hours virtual onsite interviews. It's really pathetic that after being through 7 hours of interview you get ghosted. Do let me know in the comments if you had similar experience. Thank you for reading!