0

Design a voting system

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Design a voting system

Companies: Amazon

Difficulty: Easy

Problem statement

Model polls with options, voters and ballots: cast one vote per voter, change it before closing, and tally results.

Requirements

  • An organizer creates a poll with a question and at least two distinct options.
  • A poll moves through DRAFT -> OPEN -> CLOSED. Votes are accepted only while it is OPEN.
  • Each voter holds at most one ballot per poll (single choice). They can change their vote, or retract it, any time before the poll closes. Re-voting for the same option is a no-op.
  • An eligibility rule decides who may vote: open to everyone, or a fixed allow list.
  • Anyone can tally results at any time; the tally says whether it is final (poll closed). Ties report every top option. Concurrent votes must never double count or lose a vote.
  • Out of scope: authentication and identity proofing, ranked-choice or multi-select ballots (see Extensions), anonymity guarantees, persistence and distribution across machines, UI.

Core objects

  • PollStatus (enum): DRAFT, OPEN, CLOSED. VotingError: the one exception for rule violations.
  • Option: an immutable choice in a poll (id + label).
  • Voter: an immutable identity that casts ballots (id + name).
  • Ballot: one voter's current choice in one poll, with when it was first cast and last changed. Immutable; a change replaces it.
  • EligibilityPolicy (ABC): decides whether a voter may vote. OpenToAll and AllowList implement it.
  • Poll: owns its options, status, ballots and running counts; enforces one-ballot-per-voter and the status rules under a lock.
  • TallyResult: an immutable snapshot of counts, total, winners and finality.

Class design

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"option","x":0,"y":160,"width":240,"height":90,"label":{"text":"Option\nid, label"}},
 {"type":"rectangle","id":"ballot","x":0,"y":300,"width":240,"height":110,"label":{"text":"Ballot\nvoter_id, option_id\ncast_at, updated_at"}},
 {"type":"rectangle","id":"poll","x":420,"y":180,"width":280,"height":180,"label":{"text":"Poll\nstatus, ballots\ncounts, lock\ncast(), retract()\nopen(), close(), tally()"}},
 {"type":"rectangle","id":"tally","x":880,"y":160,"width":240,"height":100,"label":{"text":"TallyResult\ncounts, winners\nfinal"}},
 {"type":"rectangle","id":"elig","x":880,"y":300,"width":240,"height":110,"label":{"text":"EligibilityPolicy\n(abstract)\nis_eligible(voter)"}},
 {"type":"rectangle","id":"open","x":760,"y":540,"width":180,"height":70,"label":{"text":"OpenToAll"}},
 {"type":"rectangle","id":"allow","x":1000,"y":530,"width":200,"height":90,"label":{"text":"AllowList\nids"}},
 {"type":"arrow","id":"poll-option","x":420,"y":205,"width":-180,"height":0,"start":{"id":"poll"},"end":{"id":"option"},"label":{"text":"has 2+"}},
 {"type":"arrow","id":"poll-ballot","x":420,"y":335,"width":-180,"height":5,"start":{"id":"poll"},"end":{"id":"ballot"},"label":{"text":"has 0+"}},
 {"type":"arrow","id":"poll-tally","x":700,"y":210,"width":180,"height":0,"start":{"id":"poll"},"end":{"id":"tally"},"label":{"text":"creates"},"strokeStyle":"dashed"},
 {"type":"arrow","id":"poll-elig","x":700,"y":340,"width":180,"height":0,"start":{"id":"poll"},"end":{"id":"elig"},"label":{"text":"uses"}},
 {"type":"arrow","id":"open-elig","x":850,"y":540,"width":110,"height":-130,"start":{"id":"open"},"end":{"id":"elig"},"label":{"text":"extends"}},
 {"type":"arrow","id":"allow-elig","x":1100,"y":530,"width":-40,"height":-120,"start":{"id":"allow"},"end":{"id":"elig"},"label":{"text":"extends"}}
]}

Key flows

Poll lifecycle

{"type":"excalidraw","elements":[
 {"type":"ellipse","id":"start","x":0,"y":5,"width":100,"height":60,"label":{"text":"start"}},
 {"type":"rectangle","id":"draft","x":260,"y":0,"width":160,"height":70,"label":{"text":"DRAFT"}},
 {"type":"rectangle","id":"open","x":600,"y":0,"width":160,"height":70,"label":{"text":"OPEN"}},
 {"type":"rectangle","id":"closed","x":940,"y":0,"width":160,"height":70,"label":{"text":"CLOSED"}},
 {"type":"ellipse","id":"end","x":1280,"y":5,"width":100,"height":60,"label":{"text":"end"}},
 {"type":"arrow","id":"create","x":100,"y":35,"width":160,"height":0,"start":{"id":"start"},"end":{"id":"draft"},"label":{"text":"Poll(...)"}},
 {"type":"arrow","id":"do-open","x":420,"y":35,"width":180,"height":0,"start":{"id":"draft"},"end":{"id":"open"},"label":{"text":"open()"}},
 {"type":"arrow","id":"do-close","x":760,"y":35,"width":180,"height":0,"start":{"id":"open"},"end":{"id":"closed"},"label":{"text":"close()"}},
 {"type":"arrow","id":"finish","x":1100,"y":35,"width":180,"height":0,"start":{"id":"closed"},"end":{"id":"end"}},
 {"type":"arrow","id":"vote","x":640,"y":0,"width":80,"height":0,"start":{"id":"open"},"end":{"id":"open"},"points":[[0,0],[0,-60],[80,-60],[80,0]]},
 {"type":"text","id":"vote-note","x":580,"y":-100,"text":"cast / change / retract","fontSize":16}
]}

Any other transition (reopening, voting in a draft) raises VotingError.

Cast or change a vote (Poll.cast)

  1. Poll asks its EligibilityPolicy whether the Voter may vote, and checks the option id exists. Both are immutable, so this happens before taking the lock.
  2. Under the poll lock, require status OPEN.
  3. Look up the voter's existing Ballot. Same option: return it unchanged.
  4. Different option (or none yet): decrement the old option's count, store a new Ballot that keeps the original cast_at and sets updated_at, increment the new option, return the ballot.

Ballots are keyed by voter id, so a second vote is a change, never a second ballot. Steps 3–4 share one lock, so concurrent votes from one voter cannot both count. Retract pops the ballot and decrements its option under the same lock.

Tally (Poll.tally): under the lock, copy the running counts per option and read the status. Outside the lock, compute total and winners (all options sharing the max count, if it is above zero). Counts are maintained incrementally, so a tally is O(options), not O(ballots).

Code

from __future__ import annotations
import threading
from abc import ABC, abstractmethod
from collections import Counter
from dataclasses import dataclass
from datetime import datetime, timezone
from enum import Enum


class PollStatus(Enum):
    DRAFT = "draft"
    OPEN = "open"
    CLOSED = "closed"


class VotingError(Exception):
    """Raised for any rule violation."""


@dataclass(frozen=True)
class Option:
    id: str
    label: str


@dataclass(frozen=True)
class Voter:
    id: str
    name: str


@dataclass(frozen=True)
class Ballot:
    voter_id: str
    option_id: str
    cast_at: datetime
    updated_at: datetime


class EligibilityPolicy(ABC):
    @abstractmethod
    def is_eligible(self, voter: Voter) -> bool: ...


class OpenToAll(EligibilityPolicy):
    def is_eligible(self, voter: Voter) -> bool:
        return True


class AllowList(EligibilityPolicy):
    def __init__(self, voter_ids: set[str]) -> None:
        self._ids = frozenset(voter_ids)

    def is_eligible(self, voter: Voter) -> bool:
        return voter.id in self._ids


@dataclass(frozen=True)
class TallyResult:
    counts: dict[str, int]  # option label -> votes
    total: int
    winners: list[str]      # every option tied for the top count
    final: bool             # True once the poll is closed


class Poll:
    def __init__(self, question: str, labels: list[str],
                 policy: EligibilityPolicy | None = None) -> None:
        if len(labels) < 2 or len(set(labels)) != len(labels):
            raise VotingError("a poll needs at least two distinct options")
        self.question = question
        self.options = {f"opt{i}": Option(f"opt{i}", label)
                        for i, label in enumerate(labels, 1)}
        self.policy = policy or OpenToAll()
        self.status = PollStatus.DRAFT
        self._ballots: dict[str, Ballot] = {}
        self._counts: Counter[str] = Counter()
        self._lock = threading.Lock()

    def open(self) -> None:
        with self._lock:
            self._require(PollStatus.DRAFT)
            self.status = PollStatus.OPEN

    def close(self) -> None:
        with self._lock:
            self._require(PollStatus.OPEN)
            self.status = PollStatus.CLOSED

    def cast(self, voter: Voter, option_id: str) -> Ballot:
        if not self.policy.is_eligible(voter):
            raise VotingError(f"{voter.id} is not eligible for this poll")
        if option_id not in self.options:
            raise VotingError(f"unknown option {option_id}")
        now = datetime.now(timezone.utc)
        with self._lock:
            self._require(PollStatus.OPEN)
            old = self._ballots.get(voter.id)
            if old is not None and old.option_id == option_id:
                return old  # same choice again: no-op
            if old is not None:
                self._counts[old.option_id] -= 1
            ballot = Ballot(voter.id, option_id, old.cast_at if old else now, now)
            self._ballots[voter.id] = ballot
            self._counts[option_id] += 1
            return ballot

    def retract(self, voter: Voter) -> None:
        with self._lock:
            self._require(PollStatus.OPEN)
            old = self._ballots.pop(voter.id, None)
            if old is None:
                raise VotingError(f"{voter.id} has no vote to retract")
            self._counts[old.option_id] -= 1

    def tally(self) -> TallyResult:
        with self._lock:
            counts = {o.label: self._counts[o.id] for o in self.options.values()}
            final = self.status is PollStatus.CLOSED
        top = max(counts.values())
        winners = [label for label, n in counts.items() if n == top and n > 0]
        return TallyResult(counts, sum(counts.values()), winners, final)

    def _require(self, status: PollStatus) -> None:
        if self.status is not status:
            raise VotingError(f"poll is {self.status.value}, needs {status.value}")


if __name__ == "__main__":
    poll = Poll("Team lunch?", ["Pizza", "Sushi", "Tacos"])
    alice, bob = Voter("u1", "Alice"), Voter("u2", "Bob")
    poll.open()
    poll.cast(alice, "opt1")
    poll.cast(bob, "opt2")
    poll.cast(bob, "opt1")  # Bob changes his mind
    poll.close()
    print(poll.tally())     # Pizza 2, Sushi 0, Tacos 0; winners ['Pizza']; final
    # poll.cast(alice, "opt3") now raises VotingError: poll is closed, needs open

Design patterns

  • Strategy — EligibilityPolicy lets each poll plug in who may vote (OpenToAll, AllowList) without Poll knowing the rule. New rules (org members, account age) are new classes.
  • Immutable value objects — Option, Voter, Ballot and TallyResult are frozen: a changed vote replaces the ballot, and a returned tally cannot drift.
  • The lifecycle is a small enum guarded by _require, not the full State pattern. With three states and two transitions, State classes would add code without removing any branching. Promote it if states gain distinct behavior (for example a PAUSED state, or scheduled open and close).

Extensions

  • Multi-select or ranked choice: replace option_id in Ballot with selections: tuple[str, ...], and add a TallyStrategy (plurality, approval, instant runoff). Plurality and approval can still use running counts. Instant runoff needs the stored ballots, so tally() hands the ballots to the strategy.
  • Scheduled open and close: add opens_at and closes_at. cast treats the poll as closed when now >= closes_at, so correctness does not depend on a timer firing. A scheduler calls close() only to make the tally final.
  • Audit trail and anonymity: append every cast, change and retract to an event log (VoteEvent), and derive counts from it if needed. For anonymous polls, keep the voter-to-ballot map for dedupe, but expose only counts. Never return ballots to anyone other than their voter.
  • Scale across machines: the per-poll lock becomes a database constraint. Store ballots with a unique key (poll_id, voter_id), upsert the choice, and update counts in the same transaction, or rebuild them with GROUP BY option_id. For very hot polls, shard counters per option and sum them on read.

Interviewer expectations

Mid-level (L4)

  • Clean Poll, Option, Voter, Ballot classes with one ballot per voter enforced by a map keyed on voter id.
  • Changing a vote moves the count from the old option to the new one; closed polls reject votes.
  • Working tally, with a sensible answer for ties.

Senior (L5)

  • An explicit lifecycle with guarded transitions, and a validation order: eligibility, option, then status under the lock.
  • Thread safety: check-and-update of a ballot is atomic per poll; tally returns a consistent snapshot.
  • Running counts for O(options) tallies, and a pluggable eligibility rule. Idempotent re-votes.

Staff (L6+)

  • Maps the in-memory invariant to storage: a unique (poll_id, voter_id) key, a transactional upsert, and counters that can be rebuilt from ballots.
  • Discusses anonymity against auditability, ballot stuffing and identity, and deadlines enforced at read time rather than by timers.
  • Shows how ranked choice and approval voting fit behind a tally strategy without changing the cast path.

Sign in to comment, vote or remix.