🎓 A1Learner
🔍

DSA Beginner Capstone

The DSA Beginner Capstone is a mixed set of five original problems. Each problem hides its pattern, so the first job is naming the right family.

Problem 1, hashing

A booth scans raffle tickets and needs the first number scanned twice. The seen-before cue points to a set.

seen = set()
for ticket in [9, 4, 9]:
    if ticket in seen:
        print("Repeat found:", ticket)
    seen.add(ticket)

Problem 2, two pointers

Parcel weights are already sorted and one pair must reach a target total. Sorted pair data points to pointers closing from both ends.

weights = [3, 6, 10, 14]
target = 16
left = 0
right = len(weights) - 1
while left < right:
    total = weights[left] + weights[right]
    if total == target:
        print("Pair:", [weights[left], weights[right]])
        break
    if total < target:
        left += 1
    else:
        right -= 1

Problem 3, stack

A typing app treats a star as an undo key for the last letter. Last-in removal points to a stack.

stack = []
for char in "ab*c":
    if char == "*":
        stack.pop()
    else:
        stack.append(char)
print("Cleaned:", "".join(stack))

Problem 4, breadth-first search

A ferry map links each stop to its neighbours. The fewest-rides cue points to breadth-first search with a queue.

from collections import deque

graph = {
    "Pier": ["Arch", "Bank"],
    "Arch": ["Pier", "Cave"],
    "Bank": ["Pier", "Cave"],
    "Cave": ["Arch", "Bank"],
}
distance = {"Pier": 0}
queue = deque(["Pier"])
while queue:
    stop = queue.popleft()
    for nxt in graph[stop]:
        if nxt not in distance:
            distance[nxt] = distance[stop] + 1
            queue.append(nxt)
print("Hops to Cave:", distance["Cave"])

Problem 5, dynamic programming

A walkway count grows by adding the counts for two shorter walkways. Smaller counts stored in a table point to dynamic programming.

table = [1, 1]
for n in range(2, 6):
    table.append(table[n - 1] + table[n - 2])
print("Ways table:", table)

Example

from collections import deque


def first_repeat(tickets):
    seen = set()
    for ticket in tickets:
        if ticket in seen:
            return ticket
        seen.add(ticket)
    return -1


def pair_with_sum(weights, target):
    left = 0
    right = len(weights) - 1
    while left < right:
        total = weights[left] + weights[right]
        if total == target:
            return [weights[left], weights[right]]
        if total < target:
            left += 1
        else:
            right -= 1
    return []


def clean_typing(text):
    stack = []
    for char in text:
        if char == "*":
            if stack:
                stack.pop()
        else:
            stack.append(char)
    return "".join(stack)


def shortest_hops(graph, start, goal):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        stop = queue.popleft()
        if stop == goal:
            return distance[stop]
        for nxt in graph.get(stop, []):
            if nxt not in distance:
                distance[nxt] = distance[stop] + 1
                queue.append(nxt)
    return -1


def tile_ways(length):
    table = [0] * (length + 1)
    table[0] = 1
    if length >= 1:
        table[1] = 1
    for n in range(2, length + 1):
        table[n] = table[n - 1] + table[n - 2]
    return table[length]


ferry = {
    "Dock": ["Market", "Library"],
    "Market": ["Dock", "Hill"],
    "Library": ["Dock", "Hill", "Station"],
    "Hill": ["Market", "Library", "Depot"],
    "Station": ["Library", "Depot"],
    "Depot": ["Hill", "Station"],
    "Island": [],
}

checks = [
    ("Problem 1 - Hashing: first repeat ticket",
     "[14, 7, 22, 7, 31, 22]", 7,
     first_repeat([14, 7, 22, 7, 31, 22])),
    ("Problem 1 - Hashing: first repeat ticket",
     "[5, 9, 12, 20]", -1,
     first_repeat([5, 9, 12, 20])),
    ("Problem 2 - Two pointers: pair with sum",
     "weights [3, 6, 10, 14, 18, 25], target 24", [6, 18],
     pair_with_sum([3, 6, 10, 14, 18, 25], 24)),
    ("Problem 2 - Two pointers: pair with sum",
     "weights [2, 5, 9, 13], target 20", [],
     pair_with_sum([2, 5, 9, 13], 20)),
    ("Problem 3 - Stack: cleaned typing",
     '"writ*te"', "write", clean_typing("writ*te")),
    ("Problem 3 - Stack: cleaned typing",
     '"abc**d"', "ad", clean_typing("abc**d")),
    ("Problem 4 - BFS: fewest ferry hops",
     "Dock to Depot", 3, shortest_hops(ferry, "Dock", "Depot")),
    ("Problem 4 - BFS: fewest ferry hops",
     "Dock to Island", -1, shortest_hops(ferry, "Dock", "Island")),
    ("Problem 5 - DP: tiling a walkway",
     "length 6", 13, tile_ways(6)),
    ("Problem 5 - DP: tiling a walkway",
     "length 10", 89, tile_ways(10)),
]

passed = 0
for label, shown, expected, got in checks:
    ok = got == expected
    if ok:
        passed += 1
    print(label)
    print("  Input:", shown)
    print("  Expected:", expected, "| Got:", got, "|",
          "PASS" if ok else "FAIL")
print("Score:", str(passed) + "/" + str(len(checks)), "passed")

Key points

  • Naming the pattern family comes before writing any code.
  • A seen-before question over one pass points to hashing with a set.
  • A pair search inside sorted data points to two pointers at the ends.
  • An undo step that removes the last item points to a stack.
  • A fewest hops question on unweighted links points to breadth-first search.
  • A count built from two smaller counts points to a dynamic programming table.

In this example, the program defines one tested function for each of the five problems. first_repeat stores scanned tickets in a set and returns the first repeat. pair_with_sum closes two pointers over sorted weights until the target is met. clean_typing pushes letters on a stack and pops one for each star. shortest_hops spreads a queue over the ferry map and returns the hop count. tile_ways fills a table where each count adds the two counts before it. The harness runs ten fixed cases and prints expected and got for each one.

Note

The scorecard prints input, expected and got for every case.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Which list matches each capstone problem to its pattern family?