Stable Internships

Category

Famous Algorithms

Difficulty

Medium

Problem Statement

Given a set of interns and a set of teams, where each intern has a ranked preference list of teams and each team has a ranked preference list of interns, find a stable matching between interns and teams. A matching is stable if there is no unmatched intern-team pair who would both prefer each other over their current match. This is the classic Stable Matching (Gale-Shapley) problem.

Intuition

The Gale-Shapley algorithm works by having one side (say, interns) "propose" to their most preferred unmatched team. Teams tentatively accept the best proposal they have received so far, rejecting the rest. Rejected interns then propose to their next choice. This process continues until everyone is matched.

The algorithm guarantees a stable matching: no intern-team pair exists where both would prefer each other over their assigned partner. The proposing side gets the best stable matching for them, while the receiving side gets their worst stable matching.

Approach

1. Initialize all interns and teams as unmatched.
2. While there exists an unmatched intern: a. The intern proposes to the highest-ranked team they have not yet proposed to. b. If the team is unmatched, they tentatively accept. c. If the team is already matched but prefers this intern over their current match:
   • The team switches to the new intern.
   • The previously matched intern becomes unmatched. d. Otherwise, the team rejects the proposal.
3. Return the final matching.

Pseudocode

function stableInternships(interns, teams):
    n = number of interns (and teams)
    // interns[i] = ranked list of team preferences for intern i
    // teams[j] = ranked list of intern preferences for team j

    // Precompute team preference rankings for O(1) comparison
    teamRanks = 2D array
    for j from 0 to n - 1:
        for rank from 0 to n - 1:
            teamRanks[j][teams[j][rank]] = rank

    nextProposal = array of n zeros  // next team index to propose to for each intern
    teamMatch = array of n, all -1   // current intern matched to each team
    freeInterns = stack of all intern indices

    while freeInterns is not empty:
        intern = freeInterns.pop()
        team = interns[intern][nextProposal[intern]]
        nextProposal[intern] += 1

        if teamMatch[team] == -1:
            teamMatch[team] = intern
        else:
            currentIntern = teamMatch[team]
            if teamRanks[team][intern] < teamRanks[team][currentIntern]:
                teamMatch[team] = intern
                freeInterns.push(currentIntern)
            else:
                freeInterns.push(intern)

    // Build result
    result = []
    for team from 0 to n - 1:
        result.append([teamMatch[team], team])
    return result

Time & Space Complexity

• Time: O(n^2), where n is the number of interns/teams. In the worst case, each intern proposes to every team. Precomputing rankings takes O(n^2).
• Space: O(n^2) for the preference lists and ranking matrices.

Key Insights

• The Gale-Shapley algorithm always terminates and produces a stable matching. This is proven by the fact that each intern proposes to each team at most once, giving at most n^2 proposals.
• The matching is "proposer-optimal": interns get the best partner they could in any stable matching.
• The matching is "receiver-pessimal": teams get the worst partner they could in any stable matching.
• Precomputing team ranking lookups (converting preference lists to rank maps) enables O(1) comparison during proposals.
• The algorithm is deterministic: the same input always produces the same output.

Edge Cases

• n = 1: trivial matching of the single intern to the single team.
• All interns have the same preference order: the algorithm still terminates and produces a stable matching.
• All teams have the same preference order: the top-preferred intern gets their first choice, etc.
• A scenario where no stable matching exists: this cannot happen; the Gale-Shapley algorithm always finds one.