Online Assessment Practice
Practice solving Amazon OA-style problems under timed conditions. simulates the real OA experience: 2 coding problems in 70 minutes.
OA Format
2
Coding Problems
70
Minutes Total
~10⁸
Operations/second
Time Allocation Strategy
Problem 1 (Easy/Medium): 20-25 minutes
Solve quickly, leave time for Problem 2
Problem 2 (Medium/Hard): 25-30 minutes
The harder problem, allocate more time
Buffer: 10-15 minutes
Edge case testing, code review, debugging
OA Timer
Amazon Online Assessment Simulation
Remaining
Problem 1: Merge k Sorted Lists
Given an array of k linked-lists sorted in ascending order, merge all into a single sorted list.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Constraints:
- k == lists.length
- 0 <= lists[i].length <= 500
Show Solution (after attempting)
Divide and conquer - pairwise merge lists
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
return mergeLists(lists, 0, lists.length - 1);
}
private ListNode mergeLists(ListNode[] lists, int lo, int hi) {
if (lo == hi) return lists[lo];
int mid = lo + (hi - lo) / 2;
ListNode left = mergeLists(lists, lo, mid);
ListNode right = mergeLists(lists, mid + 1, hi);
return mergeTwo(left, right);
}
private ListNode mergeTwo(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) { l1.next = mergeTwo(l1.next, l2); return l1; }
else { l2.next = mergeTwo(l1, l2.next); return l2; }
}
}Time: O(N log k) | Space: O(log k)
Problem 2: Search a 2D Matrix
Write an efficient algorithm that searches for a value in an m x n matrix. Each row is sorted and the first integer of each row is greater than the last integer of the previous row.
Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true
Constraints:
- m, n >= 1
- m*n <= 10^4
Show Solution (after attempting)
Binary search treating matrix as 1D array
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int low = 0, high = m * n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int val = matrix[mid / n][mid % n];
if (val == target) return true;
else if (val < target) low = mid + 1;
else high = mid - 1;
}
return false;
}
}Time: O(log(m*n)) | Space: O(1)
Problem 3: N-Queens
The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Return the number of distinct solutions.
Example 1:
Input: n = 4
Output: 2
Constraints:
- 1 <= n <= 9
Show Solution (after attempting)
Backtracking: place queens row by row, check validity before placing
class Solution {
public int totalNQueens(int n) {
return backtrack(0, n, new ArrayList<>());
}
private int backtrack(int row, int n, List<Integer> queens) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
if (isValid(queens, row, col)) {
queens.add(col);
count += backtrack(row + 1, n, queens);
queens.remove(queens.size() - 1);
}
}
return count;
}
private boolean isValid(List<Integer> queens, int row, int col) {
for (int r = 0; r < row; r++) {
int c = queens.get(r);
if (c == col || Math.abs(r - row) == Math.abs(c - col)) return false;
}
return true;
}
}Time: O(n!) | Space: O(n) recursion depth
Problem 4: Traveling Salesman Problem
Given n cities and distances between them, find the shortest possible route that visits each city exactly once and returns to the starting city. This is the classic TSP problem.
Example 1:
Input: dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
Output: 80
Constraints:
- n == dist.length
- 1 <= n <= 12
- dist[i][j] is the distance from city i to city j
- dist[i][j] == dist[j][i]
Show Solution (after attempting)
Bitmask DP. dp[mask][i] = minimum cost to visit all cities in mask, ending at city i. For each state, try extending to unvisited cities.
class Solution {
public int tsp(int[][] dist) {
int n = dist.length;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
dp[1][0] = 0; // Start at city 0
for (int mask = 1; mask < (1 << n); mask++) {
for (int u = 0; u < n; u++) {
if (dp[mask][u] == Integer.MAX_VALUE) continue;
if ((mask & (1 << u)) == 0) continue;
for (int v = 0; v < n; v++) {
if ((mask & (1 << v)) != 0) continue;
int newMask = mask | (1 << v);
dp[newMask][v] = Math.min(dp[newMask][v],
dp[mask][u] + dist[u][v]);
}
}
}
int fullMask = (1 << n) - 1;
int result = Integer.MAX_VALUE;
for (int u = 0; u < n; u++) {
result = Math.min(result, dp[fullMask][u] + dist[u][0]);
}
return result;
}
}Time: O(2^n * n^2) | Space: O(2^n * n)