Got it! Since you’ve already solved 100 LeetCode questions and are preparing for Amazon’s coding OA, let’s focus on more advanced strategies and problem types that are specifically common in Amazon assessments. I’ll also highlight some important patterns, pitfalls, and performance optimization tips for those high-value problems that can often appear in Amazon’s OA.

Advanced Cheat Sheet for Amazon Coding OA:

1. Top Amazon Problem Categories

• Greedy Algorithms: Amazon loves greedy problems because they test your ability to balance short-term vs long-term decisions. Watch out for optimization problems that seem to have obvious greedy solutions but may require careful handling of edge cases. Pro Tips:
  • Examples:
    • Reorganize String: You have to arrange characters such that no two adjacent characters are the same. This is a common greedy + heap problem.
    • Maximum Units on a Truck: Select items with a greedy strategy while keeping track of capacity.
  • Use heaps/priority queues to dynamically keep track of the best option.
  • Watch out for situations where sorting by a key before greedy selection simplifies the problem.

from heapq import heappush, heappop

def reorganize_string(S):
    heap = []
    count = Counter(S)
    for key, value in count.items():
        heappush(heap, (-value, key))  # Max heap by frequency
    result = []
    while len(heap) > 1:
        first, second = heappop(heap), heappop(heap)
        result.append(first[1])
        result.append(second[1])
        if first[0] + 1 < 0:
            heappush(heap, (first[0] + 1, first[1]))
        if second[0] + 1 < 0:
            heappush(heap, (second[0] + 1, second[1]))
    if heap:
        result.append(heap[0][1])
    return "".join(result) if len(result) == len(S) else ""

2. Heap + Sorting

• Pattern: Sorting or keeping track of the largest/smallest elements using a heap is frequent in Amazon problems, especially when you need to keep track of multiple conditions while processing data.
• Examples:
  • K Closest Points to Origin: Use a max heap to track the smallest elements dynamically.
  • Top K Frequent Words/Elements: Maintain the most frequent elements in a min-heap, but handle ties (e.g., by lexicographical order).

Pro Tips:

• When the problem involves “top K,” a heap is almost always the right choice.
• For distance/weight-based problems, don’t forget to square the components if using Euclidean distance.

def k_closest(points, K):
    heap = []
    for (x, y) in points:
        dist = -(x*x + y*y)  # Use negative for max-heap simulation        if len(heap) == K:
            heappushpop(heap, (dist, x, y))
        else:
            heappush(heap, (dist, x, y))
    return [(x, y) for (dist, x, y) in heap]

3. Graph Algorithms:

• Pattern: Amazon OAs often include graph-related problems that test your knowledge of DFS/BFS, topological sorting, and Dijkstra’s algorithm.
• Examples:
  • Course Schedule: Implement topological sorting (Kahn’s Algorithm or DFS-based).
  • Number of Islands: Use DFS/BFS to traverse the grid and count distinct islands.

Pro Tips:

• Think about grid traversal problems as graph problems where each cell is a node, and neighbors are connected via edges.
• DFS for deep problems where you need to explore as far as possible (e.g., backtracking). BFS when you need to find the shortest path (e.g., minimum steps).

def num_islands(grid):
    def dfs(i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == '0':
            return        grid[i][j] = '0'        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    count = 0    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1    return count

4. Dynamic Programming (DP) - Amazon Specific Approaches