Here’s a list of 50 common Amazon coding interview questions with solutions in Java,

including explanations and time complexities:

1. Two Sum

Problem: Given an array of integers, return indices of the two numbers that add up to a
specific target.

import [Link];

public class TwoSum {

public static int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();

for (int i = 0; i < [Link]; i++) {

int complement = target - nums[i];

if ([Link](complement)) {
return new int[]{[Link](complement), i};
}
[Link](nums[i], i);
}
return new int[]{};
}

public static void main(String[] args) {

int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
[Link]("Indices: " + result[0] + ", " + result[1]);
}
}

Explanation:

1.​ Create a HashMap to store elements and their indices.

2.​ Iterate through the array:
○​ Compute the complement (target - nums[i]).
 ○​ Check if it exists in the map.
○​ If yes, return indices.
○​ Otherwise, add the element to the map.

Time Complexity: O(n) (as we traverse the array once and perform O(1) lookups).

2. Reverse a String

Problem: Reverse a given string.

public class ReverseString {

public static String reverse(String s) {
char[] chars = [Link]();
int left = 0, right = [Link]() - 1;

while (left < right) {

char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
left++;
right--;
}
return new String(chars);
}

public static void main(String[] args) {

[Link](reverse("amazon"));
}
}

Time Complexity: O(n) (as we swap elements in a single pass).

3. Merge Two Sorted Lists

Problem: Merge two sorted linked lists into a single sorted linked list.

class ListNode {
 int val;
ListNode next;
ListNode(int val) { [Link] = val; }
}

public class MergeSortedLists {

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;

while (l1 != null && l2 != null) {

if ([Link] < [Link]) {
[Link] = l1;
l1 = [Link];
} else {
[Link] = l2;
l2 = [Link];
}
current = [Link];
}

if (l1 != null) [Link] = l1;

if (l2 != null) [Link] = l2;

return [Link];
}
}

Time Complexity: O(n + m) (as we traverse both lists once).

4. Maximum Subarray (Kadane’s Algorithm)

Problem: Find the largest sum contiguous subarray.

public class MaxSubarray {

public static int maxSubArray(int[] nums) {
int maxSum = nums[0], currentSum = nums[0];
 for (int i = 1; i < [Link]; i++) {
currentSum = [Link](nums[i], currentSum + nums[i]);
maxSum = [Link](maxSum, currentSum);
}
return maxSum;
}

public static void main(String[] args) {

int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
[Link](maxSubArray(nums));
}
}

Time Complexity: O(n) (as we traverse the array once).

5. Find Missing Number

Problem: Find the missing number in an array of size n containing numbers 0 to n.

public class MissingNumber {

public static int findMissing(int[] nums) {
int n = [Link];
int totalSum = n * (n + 1) / 2;
int arraySum = 0;

for (int num : nums) {

arraySum += num;
}
return totalSum - arraySum;
}

public static void main(String[] args) {

int[] nums = {3, 0, 1};
[Link](findMissing(nums));
}
}
Time Complexity: O(n) (as we iterate once).

6. Valid Parentheses

Problem: Check if a string contains valid parentheses.

import [Link];

public class ValidParentheses {

public static boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : [Link]()) {
if (c == '(' || c == '{' || c == '[') {
[Link](c);
} else {
if ([Link]()) return false;
char top = [Link]();
if ((c == ')' && top != '(') ||
(c == '}' && top != '{') ||
(c == ']' && top != '[')) {
return false;
}
}
}
return [Link]();
}

public static void main(String[] args) {

[Link](isValid("()[]{}"));
}
}

Time Complexity: O(n) (as we traverse the string once).

7. Rotate an Array

Problem: Rotate an array to the right by k places.

public class RotateArray {
public static void rotate(int[] nums, int k) {
k %= [Link];
reverse(nums, 0, [Link] - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, [Link] - 1);
}

private static void reverse(int[] nums, int left, int right) {

while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}

public static void main(String[] args) {

int[] nums = {1, 2, 3, 4, 5, 6, 7};
rotate(nums, 3);
for (int num : nums) [Link](num + " ");
}
}

Time Complexity: O(n).

I'll continue listing the remaining Amazon coding challenges with their Java solutions,
explanations, and time complexity.

8. Merge Intervals

Problem: Given an array of intervals, merge overlapping intervals.

import [Link].*;
public class MergeIntervals {
public static int[][] merge(int[][] intervals) {
[Link](intervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();

for (int[] interval : intervals) {

if ([Link]() || [Link]([Link]() - 1)[1] < interval[0]) {
[Link](interval);
} else {
[Link]([Link]() - 1)[1] = [Link]([Link]([Link]() -
1)[1], interval[1]);
}
}
return [Link](new int[[Link]()][]);
}

public static void main(String[] args) {

int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
int[][] result = merge(intervals);
for (int[] interval : result) {
[Link]([Link](interval));
}
}
}

Time Complexity: O(n log n) (due to sorting).

9. Find the First and Last Position of an Element in a Sorted Array

Problem: Find the starting and ending position of a given target in a sorted array.

public class SearchRange {

public static int[] searchRange(int[] nums, int target) {
return new int[]{findBound(nums, target, true), findBound(nums, target, false)};
}

private static int findBound(int[] nums, int target, boolean first) {

int left = 0, right = [Link] - 1, result = -1;
 while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid;
if (first) right = mid - 1;
else left = mid + 1;
} else if (nums[mid] < target) left = mid + 1;
else right = mid - 1;
}
return result;
}

public static void main(String[] args) {

int[] nums = {5,7,7,8,8,10};
int target = 8;
int[] result = searchRange(nums, target);
[Link]("Start: " + result[0] + ", End: " + result[1]);
}
}

Time Complexity: O(log n) (binary search).

10. Valid Anagram

Problem: Check if two strings are anagrams.

import [Link];

public class ValidAnagram {

public static boolean isAnagram(String s, String t) {
if ([Link]() != [Link]()) return false;
char[] sArr = [Link]();
char[] tArr = [Link]();
[Link](sArr);
[Link](tArr);
return [Link](sArr, tArr);
}
 public static void main(String[] args) {
[Link](isAnagram("anagram", "nagaram"));
}
}

Time Complexity: O(n log n) (sorting).

11. Subarray Sum Equals K

Problem: Find the number of subarrays that sum to k.

import [Link];

public class SubarraySum {

public static int subarraySum(int[] nums, int k) {
int count = 0, sum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
[Link](0, 1);

for (int num : nums) {

sum += num;
if ([Link](sum - k)) count += [Link](sum - k);
[Link](sum, [Link](sum, 0) + 1);
}
return count;
}

public static void main(String[] args) {

int[] nums = {1, 1, 1};
[Link](subarraySum(nums, 2));
}
}

Time Complexity: O(n).

12. Product of Array Except Self

Problem: Given an array nums, return an array output where output[i] is the
product of all elements except nums[i].

public class ProductExceptSelf {

public static int[] productExceptSelf(int[] nums) {
int n = [Link];
int[] result = new int[n];

int left = 1;
for (int i = 0; i < n; i++) {
result[i] = left;
left *= nums[i];
}

int right = 1;
for (int i = n - 1; i >= 0; i--) {
result[i] *= right;
right *= nums[i];
}

return result;
}

public static void main(String[] args) {

int[] nums = {1, 2, 3, 4};
int[] result = productExceptSelf(nums);
for (int num : result) {
[Link](num + " ");
}
}
}

Time Complexity: O(n).

13. Search in Rotated Sorted Array

Problem: Search a given target in a rotated sorted array.

public class SearchRotatedArray {

public static int search(int[] nums, int target) {
int left = 0, right = [Link] - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (nums[mid] == target) return mid;

if (nums[left] <= nums[mid]) {

if (target >= nums[left] && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}

public static void main(String[] args) {

int[] nums = {4,5,6,7,0,1,2};
[Link](search(nums, 0));
}
}

Time Complexity: O(log n) (binary search).

14. Climbing Stairs (Fibonacci)

Problem: Given n steps, find the number of ways to reach the top.

public class ClimbStairs {

public static int climbStairs(int n) {
if (n <= 2) return n;
 int prev = 1, current = 2;
for (int i = 3; i <= n; i++) {
int next = prev + current;
prev = current;
current = next;
}
return current;
}

public static void main(String[] args) {

[Link](climbStairs(5));
}
}

Time Complexity: O(n).

You're welcome! I'll continue listing 20 of the hardest Amazon coding challenges with
Java solutions, explanations, and in-line comments.

6. Word Search
Problem: Given a 2D board and a word, determine if the word exists in the grid.

public class WordSearch {

public static boolean exist(char[][] board, String word) {
// Iterate over each cell
for (int i = 0; i < [Link]; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, 0, i, j)) return true;
}
}
return false;
}

private static boolean dfs(char[][] board, String word, int index, int i, int j) {
// If all characters are found
if (index == [Link]()) return true;
 // Check boundaries and character match
if (i < 0 || i >= [Link] || j < 0 || j >= board[0].length || board[i][j] !=
[Link](index))
return false;

// Mark the cell as visited

char temp = board[i][j];
board[i][j] = '*';

// Explore all directions

boolean found = dfs(board, word, index + 1, i + 1, j) ||
dfs(board, word, index + 1, i - 1, j) ||
dfs(board, word, index + 1, i, j + 1) ||
dfs(board, word, index + 1, i, j - 1);

// Backtrack
board[i][j] = temp;
return found;
}

public static void main(String[] args) {

char[][] board = {{'A','B','C','E'}, {'S','F','C','S'}, {'A','D','E','E'}};
[Link](exist(board, "ABCCED")); // Output: true
}
}

Time Complexity: O(m × n × 4^L) (where m, n are board dimensions, and L is word
length).​
Space Complexity: O(L) (recursive stack).

7. Find Kth Largest Element in an Array

Problem: Find the Kth largest element in an unsorted array.

import [Link];

public class KthLargest {

public static int findKthLargest(int[] nums, int k) {
 // Min-heap to store the k largest elements
PriorityQueue<Integer> heap = new PriorityQueue<>();

for (int num : nums) {

[Link](num); // Add element
if ([Link]() > k) [Link](); // Remove the smallest in heap
}
return [Link](); // The top element is the Kth largest
}

public static void main(String[] args) {

int[] nums = {3,2,1,5,6,4};
[Link](findKthLargest(nums, 2)); // Output: 5
}
}

Time Complexity: O(n log k)​

Space Complexity: O(k)

8. Alien Dictionary (Topological Sort)

Problem: Given a list of words sorted lexicographically in an alien language, determine
the order of the characters.

import [Link].*;

public class AlienDictionary {

public static String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
Map<Character, Integer> inDegree = new HashMap<>();

// Initialize graph
for (String word : words) {
for (char c : [Link]()) {
[Link](c, new HashSet<>());
[Link](c, 0);
}
}
 // Build graph using word pairs
for (int i = 0; i < [Link] - 1; i++) {
String word1 = words[i], word2 = words[i + 1];
int minLen = [Link]([Link](), [Link]());

if ([Link](word2) && [Link]() > [Link]()) return "";

for (int j = 0; j < minLen; j++) {

char c1 = [Link](j), c2 = [Link](j);
if (c1 != c2) {
if (.contains(c2)) {
[Link](c1).add(c2);
[Link](c2, [Link](c2) + 1);
}
break;
}
}
}

// Topological sort using BFS

StringBuilder order = new StringBuilder();
Queue<Character> queue = new LinkedList<>();

for (char c : [Link]()) {

if ([Link](c) == 0) [Link](c);
}

while (![Link]()) {
char c = [Link]();
[Link](c);
for (char neighbor : [Link](c)) {
[Link](neighbor, [Link](neighbor) - 1);
if ([Link](neighbor) == 0) [Link](neighbor);
}
}

return [Link]() == [Link]() ? [Link]() : "";

}
 public static void main(String[] args) {
String[] words = {"wrt","wrf","er","ett","rftt"};
[Link](alienOrder(words)); // Output: "wertf"
}
}

Time Complexity: O(V + E)​

Space Complexity: O(V)

9. Serialize and Deserialize Binary Tree

Problem: Convert a binary tree into a string and vice versa.

import [Link].*;

class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { [Link] = val; }
}

public class Codec {

public String serialize(TreeNode root) {
if (root == null) return "null,";
return [Link] + "," + serialize([Link]) + serialize([Link]);
}

public TreeNode deserialize(String data) {

Queue<String> nodes = new LinkedList<>([Link]([Link](",")));
return buildTree(nodes);
}

private TreeNode buildTree(Queue<String> nodes) {

String val = [Link]();
if ([Link]("null")) return null;
TreeNode node = new TreeNode([Link](val));
[Link] = buildTree(nodes);
[Link] = buildTree(nodes);
 return node;
}

public static void main(String[] args) {

Codec codec = new Codec();
TreeNode root = new TreeNode(1);
[Link] = new TreeNode(2);
[Link] = new TreeNode(3);
[Link] = new TreeNode(4);
[Link] = new TreeNode(5);

String serialized = [Link](root);

[Link]("Serialized: " + serialized);
TreeNode deserialized = [Link](serialized);
[Link]("Deserialized Root Value: " + [Link]);
}
}

Time Complexity: O(n)​

Space Complexity: O(n)