Synthesis and Application

Final lesson: synthesis

Now that we've covered Introduction to Data Structures, Graphs, Recursion, Hashmaps, and Trees, you're ready for the part that feels most like real problem solving: choosing and combining tools.

In interviews and real projects, the question is rarely, "Can you implement a graph?" More often, it is:

• What shape does this data have?
• What operations must be fast?
• Which structure makes the solution simpler?
• How do we analyze the tradeoffs?

Think of this lesson like a detective's case board plus a basketball playbook: clues connect, roles form hierarchies, and quick lookups can change the whole strategy.

The scouting assistant problem

Imagine you're building a small tool for a basketball coaching staff.

The app needs to answer questions like:

• Who is connected to whom? Use a graph for passing, friendships, or practice partnerships.
• What are this player's stats? Use a hashmap for fast lookup by name or ID.
• Who reports to whom? Use a tree for coaching staff, roster groups, or tournament brackets.
• Can a problem be split into smaller versions of itself? Use recursion when the structure naturally nests or branches.

The key is not memorizing labels. The key is matching the shape of the question to the shape of the structure.

Graph + hashmap in one solution

In earlier lessons, you saw graphs as adjacency lists and hashmaps as key-value stores. In real solutions, they often work together.

Here, the graph answers: Who is connected to this player?

The hashmap answers: What do we know about each player?

Together, they let us find a connected practice group and then choose the highest scorer in that group.

```python
# Graph: practice connections
connections = {
    "Ari": ["Bea", "Cam"],
    "Bea": ["Ari", "Dee"],
    "Cam": ["Ari"],
    "Dee": ["Bea"],
    "Eli": []
}

# Hashmap: fast lookup by player name
stats = {
    "Ari": {"ppg": 14},
    "Bea": {"ppg": 18},
    "Cam": {"ppg": 11},
    "Dee": {"ppg": 21},
    "Eli": {"ppg": 9}
}

def connected_group(start):
    visited = set()
    stack = [start]

    while stack:
        player = stack.pop()
        if player in visited:
            continue

        visited.add(player)
        for neighbor in connections[player]:
            stack.append(neighbor)

    return visited

group = connected_group("Ari")
best = max(group, key=lambda name: stats[name]["ppg"])

print("Practice group:", sorted(group))
print("Highest scorer in group:", best, stats[best]["ppg"], "ppg")
```

You are scanning a long list of player IDs and need to quickly check whether each ID has appeared before.

Which structure is the best first choice?

From traversal to answers

In Graphs: Concepts and Operations, you learned traversal basics. In synthesis mode, traversal becomes a way to answer practical questions.

For example: "What is the shortest chain of passes from Ari to Finn?"

Because each edge represents one pass, breadth-first search is a natural fit for shortest path in an unweighted graph.

```python
from collections import deque

passes = {
    "Ari": ["Bea", "Cam"],
    "Bea": ["Dee"],
    "Cam": ["Eli"],
    "Dee": ["Finn"],
    "Eli": ["Finn"],
    "Finn": []
}

def shortest_path(graph, start, target):
    queue = deque([[start]])
    visited = {start}

    while queue:
        path = queue.popleft()
        current = path[-1]

        if current == target:
            return path

        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])

    return None

path = shortest_path(passes, "Ari", "Finn")
print("Shortest pass chain:", " -> ".join(path))
print("Number of passes:", len(path) - 1)
```

True or false:

For any real-world problem, there is always one clearly best data structure, and using more than one usually means the solution is poorly designed.

A practical selection guide

When you're stuck, ask these questions in order:

1. Do I need fast lookup by a key?
   Reach for a hashmap or set.

2. Is the data about relationships between things?
   Think graph.

3. Is the data naturally hierarchical?
   Think tree.

4. Can the problem be solved by solving smaller similar subproblems?
   Consider recursion.

5. What operation dominates the runtime?
   Optimize for that operation first.

This is the bridge from "I know the definitions" to "I can solve unfamiliar problems."

Fill in the blank:

The average-case time complexity for retrieving a value from a Python dictionary by key is ___.

Fill in the blank: _____________

Same goal, better structure

A common growth pattern in problem solving is:

1. First, write the obvious solution.
2. Identify the slow operation.
3. Add the data structure that removes the bottleneck.

Here, we find whether any player registered twice. The nested-loop version works, but the set-based version scales much better.

```python
players = ["Ari", "Bea", "Cam", "Dee", "Bea", "Eli"]

def has_duplicate_slow(names):
    for i in range(len(names)):
        for j in range(i + 1, len(names)):
            if names[i] == names[j]:
                return True
    return False

def has_duplicate_fast(names):
    seen = set()
    for name in names:
        if name in seen:
            return True
        seen.add(name)
    return False

print("Slow duplicate check:", has_duplicate_slow(players))
print("Fast duplicate check:", has_duplicate_fast(players))
```

What you can do now

You've completed the course's first full pass through foundational data structures.

You can now:

• Explain why data structure choice changes code quality and performance.
• Model relationships with graphs.
• Use recursion when a problem naturally breaks into smaller versions.
• Use hashmaps for efficient retrieval and membership checks.
• Represent hierarchy with trees.
• Combine these tools to solve more realistic problems.

The next time you face a coding challenge, start like a detective: identify the evidence, map the relationships, decide what must be fast, and choose the structure that makes the solution almost inevitable.