Here’s a detailed cheat sheet for Amazon’s SDE Online Assessment, designed to be as comprehensive and useful as possible. It covers common coding patterns, problem types, data structures, algorithms, and useful Python snippets.

1. Arrays and Strings

Common Patterns:

• Sliding Window: Used for problems involving subarrays or substrings.
  • Example problems: Find longest substring without repeating characters, maximum sum of k-length subarray.
  • Key concept: Maintain a window that expands or contracts based on conditions.

def sliding_window(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

• Two Pointers: For finding pairs, triplets, or sections of sorted arrays/strings.
  • Example problems: Two sum (sorted), valid palindrome, container with most water.

def two_pointers(arr):
    left, right = 0, len(arr) - 1    while left < right:
        # Use pointers to compare elements        left += 1        right -= 1

String Manipulation Tricks:

• Reverse a string: s[::-1]
• Join list into string: ''.join(list)
• Use ord() and chr() for character manipulations.

2. Linked Lists

Common Patterns:

• Fast and Slow Pointers: Detecting cycles or finding the middle of a list.
  • Example problems: Detect cycle, find middle of linked list.

def detect_cycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next        fast = fast.next.next        if slow == fast:
            return True    return False

• Reversing a Linked List: Essential for many linked list problems.
  • Example problems: Reverse a linked list, reorder list, add two numbers (without extra space).

def reverse_linked_list(head):
    prev, curr = None, head
    while curr:
        next_node = curr.next        curr.next = prev
        prev = curr
        curr = next_node
    return prev