Practice problems

Four problems, from a direct application to modeling tricks that come up in interviews. Try each one before reading the approach. All solutions use only the Python standard library.

Problem 1: Broadcast time

A cluster has n servers numbered 0..n-1 and one-way links (u, v, t): a message sent from u reaches v after t milliseconds. Server s starts a broadcast and every server forwards the message as soon as it arrives. Return the time when the last server receives it, or -1 if some server never does.

Approach: the arrival time at each server is its shortest distance from s, so run Dijkstra once and take the maximum. Any infinite distance means an unreachable server.

import heapq
from math import inf

def broadcast_time(n, links, s):
    adj = [[] for _ in range(n)]
    for u, v, t in links:
        adj[u].append((v, t))
    dist = [inf] * n
    dist[s] = 0
    heap = [(0, s)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, t in adj[u]:
            if d + t < dist[v]:
                dist[v] = d + t
                heapq.heappush(heap, (d + t, v))
    worst = max(dist)
    return -1 if worst == inf else worst

print(broadcast_time(4, [(0, 1, 2), (0, 2, 5), (1, 2, 1), (2, 3, 2)], 0))  # 5

Problem 2: One discount ticket

You travel from city 0 to city n - 1 over two-way roads (u, v, c). You own one ticket that halves the price of a single road (rounded down). What is the minimum total cost?

Approach: expand the state to (city, ticket_used). The state graph has 2n vertices; every road gives an edge that keeps the flag, and while the ticket is unused it also gives an edge at half price that sets the flag. Dijkstra on the state graph answers the question. The same trick handles "at most k free edges" with k + 1 layers.

import heapq
from math import inf

def cheapest_trip(n, roads):
    adj = [[] for _ in range(n)]
    for u, v, c in roads:
        adj[u].append((v, c))
        adj[v].append((u, c))
    dist = [[inf, inf] for _ in range(n)]
    dist[0][0] = 0
    heap = [(0, 0, 0)]                       # (cost, city, used)
    while heap:
        d, u, used = heapq.heappop(heap)
        if d > dist[u][used]:
            continue
        for v, c in adj[u]:
            moves = [(d + c, used)]
            if not used:
                moves.append((d + c // 2, 1))
            for nd, nu in moves:
                if nd < dist[v][nu]:
                    dist[v][nu] = nd
                    heapq.heappush(heap, (nd, v, nu))
    return min(dist[n - 1])

print(cheapest_trip(4, [(0, 1, 10), (1, 3, 10), (0, 2, 3), (2, 3, 30)]))  # 15

Problem 3: Fewest walls to break

A grid contains (open) and (wall). You start at the top-left corner, which is open, and move in four directions. Entering a wall cell means breaking it. What is the smallest number of walls you must break to reach the bottom-right corner?