Best solutions for Amazon interview tasks.

Amazon as all other companies doesn’t share information about the tasks they use during their interviewing process. But internet is full of lists of the tasks which collecting the people who participating in the interview. IMHO the most comprehensive and the most actual list is collected here. So I decided it would be nice idea to collect solutions for these task in one set of articles. I’m going to write detailed explanations for each solution how it works and why I believe it is the best. I will use C++17 programming language. Each time when I finish a new article I will change corresponding string in the table of contents to a hyperlink to the article.

Small explanation about difficulty of the tasks. As you can see each task is market like [New Grad], [Experienced] and so on. As I understand it doesn’t show difficulty of the task, it shows a level of position which was proposed by Amazon to a person who was interviewed. There are many difficult tasks marked [Intern] or [New Grad].

AMCAT is an automatic testing system from Amazon like Leetcode or HackerRank. You can do tests in AMCAT only if a recruiter from Amazon send you a special hyperlink.

Number of stars means frequency of the question on interviews.

Descriptions of the tasks from Amazon may be slightly different than the similar solutions on Leetcode or other websites. I will describe such cases I know.

You might be interested to read a similar set of articles about the best solutions for Microsoft interview tasks here and solutions for very nice set of lessons from Codility here.

Table of contents.

1. Top K Frequently Mentioned Keywords ⭐⭐⭐ [Experienced]
2. Zombie in Matrix (Min hours to send file to all available servers) ⭐⭐⭐ [Experienced]
3. Critical Routers ⭐⭐ [New Grad | Experienced]
4. Product Suggestions ⭐⭐ [New Grad | Experienced]
5. Number of Clusters ⭐⭐ [Experienced]
6. Reorder Data in Log Files [Experienced]
7. Optimal Utilization [Experienced]
8. Min Cost to Connect Ropes / Min Time to Merge Files [Experienced]
9. Treasure Island / Min Distance to Remove the Obstacle (BFS) [Experienced]
10. Treasure Island II
11. Find Pair With Given Sum ⭐⭐ [Experienced, Intern]
12. Copy List with Random Pointer ⭐⭐ [New Grad]
13. Merge Two Sorted Lists ⭐⭐ [New Grad | Intern]
14. Subtree of Another Tree ⭐⭐ [New Grad]
15. Search a 2D Matrix II ⭐⭐ [New Grad]
16. Critical Connections ⭐ [New Grad]
17. Favorite Genres ⭐⭐ [New Grad]
18. Two Sum — Unique Pairs ⭐⭐ [New Grad]
19. Spiral Matrix ⭐ [New Grad]
20. Count substrings with exactly K distinct chars ⭐ [Intern]
21. Max Of Min Altitudes ⭐⭐ [Intern]
22. Longest Palindromic Substring ⭐⭐ [Intern]
23. Substrings of size K with K distinct chars ⭐⭐ [Intern]
24. Most Common Word ⭐⭐ [Intern]
25. K Closest Points to Origin ⭐ [Intern]
26. Generate Parentheses ⭐ [Intern]
27. Min Cost to Connect All Nodes (a.k.a. Min Cost to Add New Roads)
28. Min Cost to Repair Edges (MST)
29. Prison Cells After N Days
30. Partition Labels
31. Subtree with Maximum Average
32. Load Balancer [Experienced]
33. Battleship
34. Point of Lattice ⭐ [Experienced]
35. Merge Intervals ⭐
36. Roll Dice ⭐
37. Longest string without 3 consecutive characters
38. Longest string made up of only vowels
39. https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/ [Intern]
40. Nth GP [Intern]