Preparing for an interview? Check out Cracking the Coding Interview
Published on

Amazon SDE-1 Contractual || Bangalore || Offer

Author
  • Shared Anonymously

I recently appeared for an SDE-1 interview at Amazon. The process started with an online assessment (OA), followed by three coding rounds. Here's a breakdown of the interview process.

Link to OA questions: https://leetcode.com/discuss/interview-question/5328967/amazon-oa-sde-1-results-awaited

Then there were 3 coding rounds, last one was combining the HM+Coding. Here are the questions
First coding round:
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.
Approach:
Brute force: Sort the intervals by their start times and then merge overlapping intervals. This takes O(nlogn) due to sorting.
Optimal approach:
Instead of sorting, you can leverage counting sort, which works when the range of values in the intervals is known and relatively small. This allows processing intervals in linear time,
O(n), by mapping the start and end points of intervals and merging accordingly.

# 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.
Approach:

In-degree & out-degree:
Iterate through the adjacency list and count the in-degree and out-degree of each node. The node with in-degree equal to the total number of nodes minus one and out-degree zero is the convergent point.

DFS/BFS traversal:
This approach involves exploring paths to find a node where no further traversal is possible, and all other nodes can reach it.

# Adjacency list of the graph  
adj_list = {1: [3], 2: [3], 3: [], 4: [3]}  
  
# Convergent Point: Node 3  

Second coding round:
Q1. Find Largest Element in Every Window of Size 'k'
Given an array, find the largest element in every sliding window of size '\uD835\uDC58'. The sliding window moves from left to right by one element at a time.
Approach (Using Max-Heap):
Max-Heap: Use a max-heap.
Sliding Window: As we slide the window from left to right across the array, we add the current element to the heap.
Heap Maintenance: Remove any elements that fall outside the current window. The heap’s top (maximum element) is the largest value in the current window.
Time Complexity: Each insertion and deletion from the heap takes O(logk), and we do this n times, so the time complexity is O(nlogk).

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.
Approach:
In-order traversal:
Perform an in-order traversal to convert the BST into a sorted array, then use the two-pointer technique to find the two elements whose sum equals the target.

Hashing:
While traversing the BST, store the nodes’ values in a hash set. For each node, check if the complement (target - node value) exists in the set.

# BST elements: 5, 3, 6, 2, 4, 7  
target = 9  
# Output: True (Nodes 4 and 5 sum to 9)  

Third coding round:
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. Highlighting the lessons learned and steps taken to improve future task estimation and project management.

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.

Approach:
Use a two-pointer approach:
Traverse the array with one pointer.
Each time you encounter a non-zero, swap it with the element at the second pointer (which tracks the position for non-zero values).
Time complexity is O(n) and space complexity is O(1).

Guys I've 2 YOE at semi-product based company in Bangalore, I've recently joined a startup with 18 base, and total 19 CTC. Should I go to Amazon for SDE-1 in 12 months contract where they're offering almost 22-23 base only, nothing else. Is it worth it?

ReportMark as Helpful