We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Election Results

Number: 3078

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given a Votes table with columns "voter" and "candidate" where each person may vote for one or more candidates (or not vote by storing a null candidate), each voter’s vote is split equally among all candidates they vote for. Compute the total vote weight for each candidate and return the candidate(s) with the maximum total vote. If multiple candidates tie with the highest vote, output all of them in ascending order by name.

Key Insights

  • Group votes by voter since each voter's vote is split equally among the candidates they select.
  • Skip records where the candidate is null (indicating the voter chose not to vote).
  • For each voter, compute the weight as 1 divided by the number of candidates they voted for, then add that weight to each voted candidate’s total.
  • Finally, determine the maximum vote weight and output all candidate names with that weight, sorted in ascending order.

Space and Time Complexity

Time Complexity: O(n) where n is the number of rows in the Votes table, as we iterate through the votes and then through the grouped candidates. Space Complexity: O(n) due to storing mappings from voters to candidates and candidates to their vote totals.

Solution

The approach involves two phases:

  1. Group the votes by each voter so that for every voter, we can count the number of candidates they have voted for. This allows us to calculate the vote weight for each candidate from that voter by dividing 1 by the number of candidates they chose.
  2. Traverse the grouped votes to aggregate the score for each candidate. Then, find the maximum score and filter the candidates who have this score. Since there may be ties, we sort the candidate names in ascending order before returning them.

Key data structures include dictionaries (or hash maps) for grouping and aggregating votes. The algorithm thus achieves linear time complexity relative to the number of votes.

Code Solutions

# Python solution for Election Results problem

from collections import defaultdict

def election_results(votes):
    # Group votes by voter.
    voter_to_candidates = defaultdict(list)
    for vote in votes:
        voter = vote["voter"]
        candidate = vote["candidate"]
        # Skip null candidates (voter did not vote)
        if candidate is not None:
            voter_to_candidates[voter].append(candidate)
    
    # Aggregate vote weight for each candidate.
    candidate_scores = defaultdict(float)
    for voter, candidates in voter_to_candidates.items():
        if candidates:
            weight = 1.0 / len(candidates)
            for candidate in candidates:
                candidate_scores[candidate] += weight
    
    # Find the maximum vote score.
    if not candidate_scores:
        return []
    max_votes = max(candidate_scores.values())
    
    # Collect candidates with the maximum vote score.
    winners = [candidate for candidate, score in candidate_scores.items() if score == max_votes]
    return sorted(winners)

# Example usage:
votes = [
    {"voter": "Kathy", "candidate": None},
    {"voter": "Charles", "candidate": "Ryan"},
    {"voter": "Charles", "candidate": "Christine"},
    {"voter": "Charles", "candidate": "Kathy"},
    {"voter": "Benjamin", "candidate": "Christine"},
    {"voter": "Anthony", "candidate": "Ryan"},
    {"voter": "Edward", "candidate": "Ryan"},
    {"voter": "Terry", "candidate": None},
    {"voter": "Evelyn", "candidate": "Kathy"},
    {"voter": "Arthur", "candidate": "Christine"}
]

print(election_results(votes))
← Back to All Questions