Advanced Algorithms and Data Structures

From Python fluency to interview strategy

In Intermediate Python for Google Interviews, you practiced core tools: loops, hashing patterns, mutability, and a steady practice routine.

Now we move up one layer: advanced algorithms and data structures. Google-style interviews often test whether you can recognize the hidden structure of a problem, choose the right tool, and explain the tradeoff clearly.

For a part-time coder, the goal is not to memorize every algorithm. The goal is to build a reliable mental checklist:

• Is this a graph, tree, range, ordering, or optimization problem?
• What operation must be fast: lookup, insert, delete, min/max, connectivity, shortest path?
• What changes if the input grows from 100 items to 1,000,000?

Today we focus on patterns that repeatedly appear in Google interview prep.

The advanced-algorithm map

Most hard-looking interview problems become manageable once you classify them.

Problem signal                  Likely tool
-----------------------------------------------------
Relationships / routes          Graph traversal
Hierarchy / recursion            Tree DFS/BFS
Repeated best/min/max            Heap / priority queue
Overlapping subproblems          Dynamic programming
Groups merging over time         Union-Find
Sorted search space              Binary search

A strong candidate does not just code. They say something like:

“This looks like a graph because items are connected by relationships. I’ll use BFS if I need the shortest number of steps, DFS if I need to explore components.”

That sentence shows both pattern recognition and control over complexity.

You are given a list of cities and direct flights between them. You need to determine the minimum number of flights from city A to city B.

Which approach is the best first choice?

BFS and DFS: two interview workhorses

A graph is just things connected to other things. In interviews, graphs may appear as:

• social networks
• grids
• word transformations
• prerequisite chains
• routes and dependencies

Use BFS when you care about the shortest number of moves in an unweighted graph.

Use DFS when you care about exploring a full region, detecting cycles, or trying possibilities deeply.

BFS: explore level by level
A -> B,C -> D,E,F

DFS: go deep before backtracking
A -> B -> D -> backtrack -> C

```python
from collections import deque

# A small unweighted graph.
graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": []
}

def bfs(start):
    seen = {start}
    order = []
    q = deque([start])

    while q:
        node = q.popleft()
        order.append(node)
        for nei in graph[node]:
            if nei not in seen:
                seen.add(nei)
                q.append(nei)
    return order

def dfs(start):
    seen = set()
    order = []

    def visit(node):
        seen.add(node)
        order.append(node)
        for nei in graph[node]:
            if nei not in seen:
                visit(nei)

    visit(start)
    return order

print("BFS:", bfs("A"))
print("DFS:", dfs("A"))
```

True or false?

In an unweighted graph, BFS is a natural choice when you need the minimum number of edges between two nodes.

When “best so far” matters

A heap is useful when you repeatedly need the smallest or largest item without fully sorting everything.

Python’s heapq gives a min-heap:

• heappush: insert in O(log n)
• heappop: remove smallest in O(log n)
• peek smallest: heap[0] in O(1)

Common interview uses:

• top K frequent/largest/smallest
• merging K sorted lists
• scheduling tasks
• Dijkstra’s shortest path when edges have weights

Below, we keep only the top 3 scores from a stream. This avoids sorting the full list every time.

```python
import heapq

scores = [72, 95, 81, 100, 67, 88, 94]
k = 3
heap = []

for score in scores:
    heapq.heappush(heap, score)
    if len(heap) > k:
        heapq.heappop(heap)  # remove the smallest among the kept scores

print("Top 3 scores, unordered in heap:", heap)
print("Top 3 scores, sorted descending:", sorted(heap, reverse=True))
```

Fill in the blank:

In Python’s heapq, inserting one item into a heap of size n takes _____ time.

DP is controlled remembering

Dynamic programming is useful when a recursive search repeats the same smaller questions.

A good DP signal:

“If I solve this subproblem once, I can reuse the result later.”

Two common forms:

• Top-down memoization: write recursion, cache results
• Bottom-up tabulation: build answers from small cases to large cases

Interview tip: before coding DP, define the state in plain English.

Example state:

dp[amount] = minimum number of coins needed to make this amount.

Then your transition asks:

If I use coin c, can I improve dp[amount] from dp[amount - c] + 1?

```python
coins = [1, 3, 4]
target = 6

# dp[x] = minimum coins needed to make amount x
INF = float("inf")
dp = [INF] * (target + 1)
dp[0] = 0

for amount in range(1, target + 1):
    for coin in coins:
        if amount - coin >= 0:
            dp[amount] = min(dp[amount], dp[amount - coin] + 1)

print("Coins:", coins)
print("Target:", target)
print("Minimum coins:", dp[target])
print("DP table:", dp)
```

Fast connectivity questions

Union-Find, also called Disjoint Set Union, tracks groups that merge over time.

It supports two key operations:

• find(x): which group is x in?
• union(a, b): merge the groups containing a and b

This appears in problems like:

• number of connected components
• friend circles
• redundant connection
• accounts merge
• islands merging as land is added

Mental model:

Before union(1, 2):    {1} {2} {3,4}
After union(1, 2):     {1,2} {3,4}

In interviews, Union-Find is often chosen when edges arrive and you repeatedly ask, “Are these two things already connected?”

Which problem statement most strongly suggests dynamic programming?

Your advanced-algorithm checklist

When you see a new problem, pause before coding.

Ask:

1. What is the hidden structure? Graph, tree, array, sorted space, groups, choices?
2. What operation must be fast? Lookup, min/max, merge, shortest path, repeated subproblem?
3. What is the target complexity? Can O(n²) pass, or do we need O(n log n) / O(n)?
4. What invariant stays true? A heap keeps the best K, BFS explores by distance, DP reuses solved states.
5. Can I explain the tradeoff out loud? This matters in Google interviews.

You now have the algorithm vocabulary needed for harder practice. Later, the course will shift from single-machine coding problems into the System Design Primer for Google Interviews, where the scale and tradeoffs become broader.