Atlassian | Voting application interview question
Anonymous User
3021
AtlassianHash TableDSAInterview

Can anyone help me with this question.

Given a list of votes for the candidates
{c1, c2, c1, c2, c1, c2, c3 ,c4, c4}
we need to determine the winner based on the total number of votes for each candidate.

Question:

  1. In case of tie, what are all the different stategies we can follow?
  2. Which among the suggested strategy is the best ? I googled and read that weighted strategy is a suitable one, but need help me with its implementation.

Sample solution that GPT provided when asked for weighted strategy. Here, between c1 and c2, if c2 received first vote later, c2 is considered as winner. (Not sure if this is the right approach)

import java.util.*;

class Candidate {
String name;
int totalVotes;
List<Integer> voteIndices;

public Candidate(String name) {
    this.name = name;
    this.totalVotes = 0;
    this.voteIndices = new ArrayList<>();
}

// Method to add a vote
public void addVote(int index) {
    totalVotes++;
    voteIndices.add(index);
}

// Compare method for sorting candidates based on votes and vote indices
public int compareTo(Candidate other) {
    // First compare total votes
    if (this.totalVotes != other.totalVotes) {
        return Integer.compare(other.totalVotes, this.totalVotes); // Higher votes wins
    }

    // If total votes are the same, compare weighted votes (from latest to earliest)
    int minLength = Math.min(this.voteIndices.size(), other.voteIndices.size());
    for (int i = 0; i < minLength; i++) {
        int thisVoteIndex = this.voteIndices.get(i);
        int otherVoteIndex = other.voteIndices.get(i);
        if (thisVoteIndex != otherVoteIndex) {
            return Integer.compare(otherVoteIndex, thisVoteIndex); // Later vote wins
        }
    }

    return Integer.compare(other.voteIndices.size(), this.voteIndices.size()); // Fallback for identical indices
}
}

public class VotingSystem {
public static void main(String[] args) {
    String[] votes = {"Alice", "Bob", "Alice", "Bob", "Charlie", "Charlie", "Charlie", "Alice", "Bob", "Bob"};

    // Step 1: Count votes
    Map<String, Candidate> candidates = new HashMap<>();
    for (int i = 0; i < votes.length; i++) {
        String name = votes[i];
        candidates.putIfAbsent(name, new Candidate(name));
        candidates.get(name).addVote(i);
    }

    // Step 2: Sort candidates based on votes and indices
    List<Candidate> candidateList = new ArrayList<>(candidates.values());
    Collections.sort(candidateList, Comparator.comparingInt(Candidate::compareTo));

    // Step 3: Determine the winner
    Candidate winner = candidateList.get(0);
    System.out.println("Winner: " + winner.name + " with " + winner.totalVotes + " votes.");
}
}
Comments (4)