Round 1: Online Assessment
Questions: Link to OA questions: Amazon OA SDE-1 Results Awaited
Round 2: First Coding Round
Questions:
Q1. Merge Intervals (Optimal Solution)
The problem is a classic: given a set of intervals, merge all overlapping intervals and return the result. While the typical solution has a time complexity of O(nlogn), I was asked to optimize further using a counting sort-like approach.
# Example intervals intervals = [[1, 3], [2, 6], [8, 10], [15, 18]] # Merged Output: [[1, 6], [8, 10], [15, 18]]
Q2. Find Convergent Point on a Graph
You are given a directed graph represented as an adjacency list. Find a node (if any) that can be reached directly from every other node but has no outgoing edges. This is essentially finding a "sink" node.
# Adjacency list of the graph adj_list = {1: [3], 2: [3], 3: [], 4: [3]} # Convergent Point: Node 3
Candidate's Approach
-
Merge Intervals:
- Brute force: Sort the intervals by their start times and then merge overlapping intervals (O(nlogn)).
- Optimal approach: Use counting sort to process intervals in linear time (O(n)).
-
Find Convergent Point:
- Count in-degrees and out-degrees to find the sink node.
- Use DFS/BFS to explore paths to find the convergent point.
Interviewer's Feedback
No feedback provided.
Round 3: Second Coding Round
Questions:
Q1. Find Largest Element in Every Window of Size 'k'
Given an array, find the largest element in every sliding window of size 'k'.
arr = [1, 3, -1, -3, 5, 3, 6, 7] k = 3 # Output: [3, 3, 5, 5, 6, 7]
Q2. Find Two Sum in a BST
Given a Binary Search Tree (BST) and a target, find two nodes whose sum equals the target.
# BST elements: 5, 3, 6, 2, 4, 7 target = 9 # Output: True (Nodes 4 and 5 sum to 9)
Candidate's Approach
-
Find Largest Element in Every Window:
- Use a max-heap to maintain the largest elements in the current window.
- Time complexity: O(nlogk).
-
Find Two Sum in a BST:
- In-order traversal to create a sorted array and use two-pointer technique.
- Alternatively, use hashing to check for complements during traversal.
Interviewer's Feedback
No feedback provided.
Round 4: Third Coding Round
Questions:
Q1. Behavioral Question:
Tell me a time where you were not able to meet a deadline.
For this, I discussed a project where unexpected technical difficulties delayed the progress. I explained how I communicated the delay early, collaborated with the team for solutions, and worked overtime to mitigate the delay.
Q2. Push All Zeros to the End of Array
Write a function to move all zeroes in an array to the end while maintaining the order of the non-zero elements.
Candidate's Approach
- Push All Zeros to the End:
- Use a two-pointer approach to traverse the array and swap non-zero elements with the position tracked by the second pointer.
- Time complexity: O(n), space complexity: O(1).
Interviewer's Feedback
No feedback provided.