Online assessment (April 5):
- Similar to Top K Keywords, but with an exclude list
- Critical Routers
Virtual Onsite (April 13):
Note: I interviewed for 2 teams simultaneously
- Hiring manager 1 (plus shadow interviewer)
- 50 minutes LPs
- 10 minutes questions
- Hiring manager 2
- 30 minutes LPs
- 20 minutes system design (design Instagram)
- 10 minutes questions
- Hour break (no lunch interviews during virtual)
- Bar Raiser (external team member, and meeting name was "Bar Raiser")
- 30 minutes LPs
- 15 minutes coding question (described below)
- 15 minutes questions
- Future member of team 1 (plus shadow)
- 30 minutes LPs
- 20 minutes coding question (described below)
- 10 minutes questions
- Future member of team 2
- 20 minutes LPs
- 15 minutes coding question part 1
- 15 minutes coding question part 2
- 10 minutes questions
Coding question 1
Couldn't find a similar LeetCode. Given a list that has ascending values and then descending values, implement a function to find a value X. For example, given the input list [1, 2, 3, 4, 7, 10, 6, 5], find the value 4.
My approach: the key is that it's (kinda) sorted. For each sub-list, a binary search will find the target value in O(logN). Find the max value by binary search (if left/right are lower/higher, then go right; if they're higher/lower, then go left). Then search the left sublist with a binary search and the right with the inverse logic.
Got this fairly quick (seemed easy for a bar raiser), and it left some extra time for questions. Felt good having done well on the bar raiser first.
Coding question 2
The problem description was something like getting a list of [course, prerequisite] combinations, and determining if it's possible to complete all courses. Example: [0, 1] implies that course 1 needs to be taken before course 0. An input list of [[0, 1], [1, 2], [2, 1]] returns False because it's impossible to satisfy all courses' prerequisites.
My approach: this sounds like a "detecting cycles" problem. Build the graph, then for each node, do a traversal and see if we get back to the same node. If so, return False. I built a Course class that had prerequisites as a member, but talked myself in circles with the direction of the edges when building the graph (do I keep track of prerequisites or "follow-up" courses?). Burned a good 10 minutes going back and forth, and the interviewer wasn't helpful in talking me through it. Saw that time was approaching, so I quickly pseudocoded the rest of the answer (the graph traversal), but didn't get close to actually getting working code here.
Coding question 3
Part 1
Determine if a string is a [Valid Anagram]https://leetcode.com/problems/valid-anagram/) of another.
My approach: walk through the string and keep track of character frequencies. Walk through the second string and do the same, then compare the frequency dictionaries. The dictionary comparison is basically free (O(26) for lower case, vs O(2N) for the frequency counters.
Part 2
Given a string s and string p, find all substrings of s that are anagrams of p.
My approach: blanked on a non-brute-force solution when talking through it verbally so I started implementing that. Double nested for loop, building substrings and using the previous isAnagram function to determine if it's an anagram of p. After implementing the brute force, interviewer asked if there was a better way, and I mentioned that we're doing duplicate work by checking substrings that have already been partially checked. I suggested a sliding window and optimized further by keeping track of the frequency dictionaries as we go, instead of doing the O(N) computation in isAnagram() each time. Time was tight, so the code wasn't perfect, but the pseudocode was there and interviewer seemed happy.
Received the call today (April 20) that they would not be proceding with an offer. No feedback, per Amazon policy.