Scribd
Upload
8 views4 pages

Algorithm Practice Questions & Solutions

The document provides a list of algorithm questions commonly asked in Amazon interviews, along with their approaches and links to practice problems on LeetCode and GeeksforGeeks. Each question includes a brief description of the method to solve it, such as using binary search, dynamic programming, or greedy algorithms. The topics range from finding the Kth smallest element to counting distinct subsequences and solving the Josephus problem.

Uploaded by

Bhumika Patwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views4 pages

Algorithm Practice Questions & Solutions

The document provides a list of algorithm questions commonly asked in Amazon interviews, along with their approaches and links to practice problems on LeetCode and GeeksforGeeks. Each question includes a brief description of the method to solve it, such as using binary search, dynamic programming, or greedy algorithms. The topics range from finding the Kth smallest element to counting distinct subsequences and solving the Josephus problem.

Uploaded by

Bhumika Patwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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: [Link]
GFG: [Link]

2. Find Transition Point

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

GFG: [Link]

3. Floor of Square Root

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

LeetCode: [Link]
GFG: [Link]

4. Element Appearing Once

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

LeetCode: [Link]
GFG: [Link]

5. Index of Extra Element

Approach: Binary search for mismatch between arrays.

GFG: [Link]

6. Merge Sort for Linked List

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

LeetCode: [Link]
GFG: [Link]

7. Union of Two Linked Lists

Approach: Insert into set then sort.

GFG: [Link]
8. Merge K Sorted Arrays

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

LeetCode: [Link]
GFG: [Link]

9. Diagonal Sum in Binary Tree

Approach: Use hashmap with diagonal levels in recursive traversal.

GFG: [Link]

10. Josephus Problem

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

GFG: [Link]

11. Number of Paths in Matrix

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

LeetCode: [Link]
GFG: [Link]

12. Sort a Stack

Approach: Use recursion to sort the stack.

GFG: [Link]

13. N Meetings in One Room

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

GFG: [Link]

14. Max Length Chain

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

LeetCode: [Link]
GFG: [Link]

15. Minimum Platforms

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

GFG: [Link]
16. Minimum Spanning Tree

Approach: Prim's or Kruskal's algorithm.

LeetCode: [Link]
GFG: [Link]

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

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

GFG: [Link]

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

Approach: Recursive DP or combinatorics based on allowed counts.

GFG: [Link]

19. Unique BSTs

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

LeetCode: [Link]
GFG: [Link]

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

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

GFG: [Link]

21. Distinct Occurrences

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

LeetCode: [Link]
GFG: [Link]

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

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

GFG: [Link]

23. Count Number of Hops

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

LeetCode: [Link]
GFG: [Link]
24. Maximum Profit with At Most K Transactions

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

LeetCode: [Link]
GFG:
[Link]

You might also like