### Part 1: The Google Interview Cheat Sheet (First 5 Mins)

If you get stuck, follow these steps:

1.  **Clarify (3 min):** Ask about input size (for complexity), data types (negative numbers? duplicates?), and empty/null cases.
2.  **Brute Force (5 min):** State the obvious $O(N^2)$ or $O(2^n)$ solution aloud. Do NOT code it unless they ask.
3.  **Optimize (10 min):** Look for:
    *   **Bottlenecks:** Can a Hash Map reduce $O(N^2)$ to $O(N)$?
    *   **Unnecessary Work:** Can you use Two Pointers or Sliding Window?
    *   **Sorted Data:** If it's sorted, think **Binary Search**.
4.  **Dry Run (5 min):** Before coding, trace your logic with a small example on the whiteboard/doc.
5.  **Code (15 min):** Focus on clean Pythonic code.
6.  **Analyze (2 min):** State Time and Space complexity immediately.

# ------------------------------------------------------------------------------

def bisect_left(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:  # <= for bisect_right
            left = mid + 1
        else:
            right = mid
    return left
# --- top K
import heapq
nums = [10, 2, 5, 1, 9]
heapq.heapify(nums) # Transforms list into a heap in O(N)
smallest = heapq.heappop(nums) # Returns 1 (O(log N))
# --- BFS - Shortest Path
def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
# --- dijkstra - shortest path
import heapq
def dijkstra(adj, start):
    pq = [(0, start)] # (distance, node)
    dist = {node: float('inf') for node in adj}
    dist[start] = 0
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue
        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
# Time: O(E log V), Space: O(V + E)
# --- DFS - Connectivity/Pathfinding
def dfs(graph, node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
# --- DP - Longest Common Subsequence (LCS)
Problem: s1="abcde", s2="ace". Result: "ace" (3).
Logic: If s1[i] == s2[j], 1 + dp[i-1][j-1]. Else, max(dp[i-1][j], dp[i][j-1]).
dp[i][j] = (1 + dp[i-1][j-1] if s1[i] == s2[j] else max(dp[i-1][j], dp[i][j-1]))
# --- Tree traversals O(n)
In-order:
- is a Binary Search Tree (BST)? If you do an in-order traversal and the numbers aren't sorted, it's not a BST.
Pre-order:
- Creating a copy of a tree. If you insert nodes into a new tree in pre-order, you get an exact clone.
- directory structures
Post-order:
- Deleting a tree (you delete children before the parent).
- Calculating Tree Height or Diameter. You need the info from both children (bottom-up) before you can calculate the result for the current node.
# ---
1.  **Don't memorize code.** Memorize the **trigger**:
    *   "Shortest path in a grid?" -> **BFS**.
    *   "Sorted array?" -> **Binary Search** or **Two Pointers**.
    *   "Need to find duplicates/pairs?" -> **Hash Map (Dict)**.
    *   "Top K elements?" -> **Heap**.
    *   "Subsequences/Choices?" -> **Recursion or DP**.
2.  **Clean Code:** Use descriptive names (`queue`, `visited`, `distance`). Google cares about readability.
3.  **Check Constraints:** If the input $N$ is $10^5$, an $O(N^2)$ solution will fail. You need $O(N \log N)$ or $O(N)$.
# ---