← Coursera Interview Insights

Coursera·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Coursera software engineer interview with a simulation problem that looks approachable until you actually try to implement it cleanly under pressure. One question, but it had enough moving parts to keep me busy.

Questions Asked (1)

Q1

Given a list of ranked ballots where each ballot is an ordered list of candidate names, implement Instant Runoff Voting. Each round, count the first active candidate on each ballot. If someone clears 50%, they win. Otherwise eliminate the candidate with the fewest votes, breaking ties by keeping the lexicographically smallest name alive. Return the winner.

Algorithms & Data Structures
Author's notes

My first instinct was to mutate the ballots directly and I immediately regretted it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the rules and edge cases, then outline a round-by-round simulation using a vote-counting data structure. Discuss how to efficiently eliminate candidates and update counts, and analyze time complexity.

Pro tip: Mention that you can optimize by only redistributing ballots from the eliminated candidate rather than recounting all ballots each round, and discuss how to handle ties and majority thresholds precisely.

1. Clarify requirements and edge cases

Confirm the majority threshold (strictly >50% or >=50%), tie-breaking rules, and what happens if all candidates tie or if a ballot has no active candidates. Also clarify input format and constraints.

2. Design data structures

Choose structures to store ballots, active candidates, and vote counts. Consider using a dictionary for counts and a set for active candidates, and precomputing each ballot's candidate order for quick lookup.

3. Simulate rounds

In each round, count first active candidates, check for majority, and if none, find the candidate(s) with fewest votes. Apply tie-breaking (lexicographically smallest stays) and eliminate the chosen candidate.

4. Optimize vote redistribution

Instead of recounting all ballots each round, only update counts for ballots whose first active candidate was eliminated. This reduces time complexity from O(R*B*C) to O(B*C) overall.

5. Analyze complexity and test

Derive time and space complexity, and walk through edge cases like single candidate, all tied, and ballots with eliminated candidates. Test with small examples.

Key Points to Mention

  • Majority threshold: strictly greater than 50% of active votes (or clarify if >=50%).
  • Tie-breaking: when eliminating, keep the lexicographically smallest name alive (i.e., eliminate the largest lexicographically among tied).
  • Efficient vote counting: maintain counts and update only affected ballots upon elimination.
  • Data structures: use hash maps for counts, sets for active candidates, and precomputed rankings per ballot.
  • Edge cases: no majority possible, all candidates tied, ballots with no remaining active candidates.
  • Time complexity: O(B * C) with optimization, where B is number of ballots and C is number of candidates.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.