Amazon Algorithm Questions with Explanations & Practice Links

1. Kth Smallest Element

Approach: Use QuickSelect (avg O(n)) or Min-Heap (O(k + (n-k)logk)).

LeetCode: https://leetcode.com/problems/kth-largest-element-in-an-array/
GFG: https://www.geeksforgeeks.org/kth-smallestelement-in-an-array/

2. Find Transition Point

Approach: Binary search to find the first occurrence of 1 in sorted binary array.

GFG: https://www.geeksforgeeks.org/find-transition-point-binary-array/

3. Floor of Square Root

Approach: Binary search between 1 and x to find floor(sqrt(x)).

LeetCode: https://leetcode.com/problems/sqrtx/
GFG: https://www.geeksforgeeks.org/square-root-of-an-integer/

4. Element Appearing Once

Approach: XOR of all elements works if all others occur twice.

LeetCode: https://leetcode.com/problems/single-element-in-a-sorted-array/
GFG: https://www.geeksforgeeks.org/find-the-element-that-appears-once/

5. Index of Extra Element

Approach: Binary search for mismatch between arrays.

GFG: https://www.geeksforgeeks.org/index-of-an-extra-element/

6. Merge Sort for Linked List

Approach: Split using slow-fast pointers, then merge recursively.

LeetCode: https://leetcode.com/problems/sort-list/
GFG: https://www.geeksforgeeks.org/merge-sort-for-linked-list/

7. Union of Two Linked Lists

Approach: Insert into set then sort.

GFG: https://www.geeksforgeeks.org/union-of-two-linked-lists/
8. Merge K Sorted Arrays

Approach: Use min-heap (priority queue) for efficient merging.

LeetCode: https://leetcode.com/problems/merge-k-sorted-lists/
GFG: https://www.geeksforgeeks.org/merge-k-sorted-arrays/

9. Diagonal Sum in Binary Tree

Approach: Use hashmap with diagonal levels in recursive traversal.

GFG: https://www.geeksforgeeks.org/diagonal-sum-binary-tree/

10. Josephus Problem

Approach: Recursive: josephus(n, k) = (josephus(n-1, k) + k) % n

GFG: https://www.geeksforgeeks.org/josephus-problem/

11. Number of Paths in Matrix

Approach: DP with dp[i][j] = dp[i-1][j] + dp[i][j-1].

LeetCode: https://leetcode.com/problems/unique-paths/
GFG: https://www.geeksforgeeks.org/count-ways-reach-nth-stair/

12. Sort a Stack

Approach: Use recursion to sort the stack.

GFG: https://www.geeksforgeeks.org/sort-a-stack-using-recursion/

13. N Meetings in One Room

Approach: Greedy: Sort by end time and select non-overlapping meetings.

GFG: https://www.geeksforgeeks.org/n-meetings-in-one-room/

14. Max Length Chain

Approach: Sort by second element and apply LIS-style DP.

LeetCode: https://leetcode.com/problems/maximum-length-of-pair-chain/
GFG: https://www.geeksforgeeks.org/maximum-length-chain-of-pairs/

15. Minimum Platforms

Approach: Sort arrival and departure, use two pointers or heap.

GFG: https://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/
16. Minimum Spanning Tree

Approach: Prim's or Kruskal's algorithm.

LeetCode: https://leetcode.com/problems/connecting-cities-with-minimum-cost/
GFG: https://www.geeksforgeeks.org/minimum-spanning-tree/

17. Count Subsequences of a^i b^j c^k

Approach: Use running counts for a, ab, and abc subsequences.

GFG: https://www.geeksforgeeks.org/count-subsequences-form-ai-bj-ck/

18. Count Strings (at most 1 'b' and 2 'c')

Approach: Recursive DP or combinatorics based on allowed counts.

GFG: https://www.geeksforgeeks.org/count-strings-can-formed-using-b-c-given-constraints/

19. Unique BSTs

Approach: Catalan number: Cn = (2n)! / ((n+1)! * n!)

LeetCode: https://leetcode.com/problems/unique-binary-search-trees/
GFG: https://www.geeksforgeeks.org/total-number-of-possible-binary-search-trees-with-n-keys/

20. Count Ways to Nth Stair (Order Doesn't Matter)

Approach: Count partitions of n into 1 and 2, order doesn't matter.

GFG: https://www.geeksforgeeks.org/count-ways-reach-nth-stair/

21. Distinct Occurrences

Approach: DP: subsequenceCount(S, T) using 2D dp table.

LeetCode: https://leetcode.com/problems/distinct-subsequences/
GFG: https://www.geeksforgeeks.org/count-distinct-occurrences-as-a-subsequence/

22. Reach a Given Score (3, 5, 10)

Approach: DP to count combinations of 3, 5, 10 to reach target.

GFG: https://www.geeksforgeeks.org/count-number-ways-reach-given-score-game/

23. Count Number of Hops

Approach: DP: f(n) = f(n-1)+f(n-2)+f(n-3)

LeetCode: https://leetcode.com/problems/climbing-stairs/
GFG: https://www.geeksforgeeks.org/count-number-of-ways-to-cover-a-distance/
24. Maximum Profit with At Most K Transactions

Approach: DP for max profit at i-th day with k transactions.

LeetCode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
GFG:
https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/