Who Won the Election? Solving a TCS Coding Interview Question with Simple and Optimized Solutions

Imagine a close election where two candidates, A and B, are vying for votes. The catch? The outcome hinges on neutral voters who are undecided and can tip the balance. This is more than just an election scenario; it's a coding challenge that tests your understanding of algorithms and influence.

In this post, we’ll explore how to solve the "Who Won the Election?" problem. The solution involves determining which candidate wins by calculating the influence of their supporters on neutral voters. Along the way, we’ll break down two solutions: the brute force method for beginners and an optimized approach for advanced developers.

The Election Queue: A Simple Scenario

Picture a queue where each person represents a voter. Some support candidate A, others support candidate B, and there are some neutral voters who haven’t yet decided. The goal is to figure out who the neutral voters will support based on the proximity of supporters.

• 'A' represents a supporter of candidate A.
• 'B' represents a supporter of candidate B.
• '-' represents a neutral voter.

The key rule is:

• A supporters move to the left to influence neutral voters.
• B supporters move to the right.

If a supporter of A reaches a neutral voter before a supporter of B, that voter supports A, and vice versa. If both reach a voter at the same time, the voter remains neutral.

Brute Force Solution: For Beginners

The brute force approach involves checking each neutral voter individually to see which candidate's supporter reaches them first.

Here’s how it works:

1. Count Initial Votes: We start by counting the votes for A and B.
2. Determine Influence: For each neutral voter, check the nearest supporter of A or B.
3. Update Votes: Based on who reaches the voter first, adjust the vote count.

Here's the code in C# for this brute force approach:

using System;

public class Election
{
    public static string DetermineWinner(string queue)
    {
        int aVotes = 0, bVotes = 0;

        foreach (char c in queue)
        {
            if (c == 'A') aVotes++;
            else if (c == 'B') bVotes++;
        }

        // Check influence on neutral voters
        for (int i = 0; i < queue.Length; i++)
        {
            if (queue[i] == '-')
            {
                int leftA = queue.LastIndexOf('A', i);
                int rightB = queue.IndexOf('B', i);

                if (leftA != -1 && (rightB == -1 || Math.Abs(i - leftA) < Math.Abs(i - rightB)))
                    aVotes++;
                else if (rightB != -1) bVotes++;
            }
        }

        return aVotes > bVotes ? "A wins" : bVotes > aVotes ? "B wins" : "Coalition";
    }

    public static void Main()
    {
        string queue = "14--AB--AB---A--";
        Console.WriteLine(DetermineWinner(queue));
    }
}

Optimized Approach: For Advanced Developers

The brute force solution works but isn't efficient for larger queues. We can optimize the process by precomputing the distances to the nearest supporters of A and B for each neutral voter.

By scanning the queue only twice—once from left to right for A’s supporters and once from right to left for B’s—we can quickly determine the influence on each neutral voter in constant time.

Here’s the optimized C++ code:

#include <iostream>
#include <vector>
#include <string>
#include <climits>

std::string determineWinner(const std::string& queue) {
    int aVotes = 0, bVotes = 0;
    std::vector<int> leftA(queue.size(), INT_MAX);
    std::vector<int> rightB(queue.size(), INT_MAX);

    // Fill distances for A supporters
    int lastA = -1;
    for (int i = 0; i < queue.size(); i++) {
        if (lastA != -1) leftA[i] = i - lastA;
        if (queue[i] == 'A') lastA = i;
    }

    // Fill distances for B supporters
    int lastB = -1;
    for (int i = queue.size() - 1; i >= 0; i--) {
        if (lastB != -1) rightB[i] = lastB - i;
        if (queue[i] == 'B') lastB = i;
    }

    // Count initial votes and influence neutral voters
    for (char c : queue) {
        if (c == 'A') aVotes++;
        else if (c == 'B') bVotes++;
    }

    for (int i = 0; i < queue.size(); i++) {
        if (queue[i] == '-') {
            if (leftA[i] < rightB[i]) aVotes++;
            else if (rightB[i] < leftA[i]) bVotes++;
        }
    }

    if (aVotes > bVotes) return "A wins";
    else if (bVotes > aVotes) return "B wins";
    else return "Coalition";
}

int main() {
    std::string queue = "14--AB--AB---A--";
    std::cout << determineWinner(queue) << std::endl;
    return 0;
}

Key Takeaways

1. Brute Force is easier to understand and works well for smaller queues but is inefficient for larger inputs.
2. Optimized Solution precomputes distances and solves the problem in linear time (O(N)), making it suitable for larger queues.
3. Both approaches are valuable to learn as they help build a strong foundation for problem-solving and algorithm optimization.

Whether you're a beginner or an experienced developer, mastering both solutions will boost your confidence and coding skills. If you want more detailed guides, practice examples, and insights, be sure to visit Interview Preparation.

Happy coding!