CodingGyan

Poll Voting System

medium Real-World Mini Projects

Problem

Build a small poll. Commands: option NAME (print added, or exists if it is already there), vote VOTER NAME (print counted, no such option if the option is unknown, or already voted if the voter has voted before; the check for the option comes first), results (print one line NAME: COUNT for every option, the highest count first, and for equal counts the names in alphabetical order).

Constraints

  • 1 <= commands <= 100
  • names have no spaces

Examples

Input

option tea
option coffee
vote amit tea
results

Output

added
added
counted
tea: 1
coffee: 0

Solutions

Best approachTime O(n log n)Space O(n)

The Poll class owns the counts and the voter set, so the rules (option first, one vote per voter) cannot be skipped by the caller. The sort for the results is a small comparison: count descending, name ascending.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Run the poll.
 * Input   : Command lines.
 * Output  : Answer lines.
 * Approach: Poll class
 * Time    : O(n log n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: The Poll keeps the rules in one place: options with counts, and the set of voters who have voted.
        static class Poll {
            private final java.util.Map<String, Integer> counts = new java.util.HashMap<>();
            private final java.util.Set<String> voters = new java.util.HashSet<>();

            String addOption(String name) {
                if (counts.containsKey(name)) {
                    return "exists";
                }
                counts.put(name, 0);
                return "added";
            }

            // Step 2: The option is checked first, then the voter. A voter is stored only after a counted vote.
            String vote(String voter, String name) {
                if (!counts.containsKey(name)) {
                    return "no such option";
                }
                if (!voters.add(voter)) {
                    return "already voted";
                }
                counts.put(name, counts.get(name) + 1);
                return "counted";
            }

            // Step 3: Sort by count (high first), then by name.
            java.util.List<String> results() {
                java.util.List<String> names = new java.util.ArrayList<>(counts.keySet());
                names.sort((x, y) -> counts.get(y) != counts.get(x).intValue() ? counts.get(y) - counts.get(x) : x.compareTo(y));
                java.util.List<String> out = new java.util.ArrayList<>();
                for (String name : names) {
                    out.add(name + ": " + counts.get(name));
                }
                return out;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        Poll poll = new Poll();
        java.util.List<String> out = new java.util.ArrayList<String>();
        for (String line : lines) {
            String[] part = line.split(" ");
            if (part[0].equals("option")) {
                out.add(poll.addOption(part[1]));
            } else if (part[0].equals("vote")) {
                out.add(poll.vote(part[1], part[2]));
            } else {
                out.addAll(poll.results());
            }
        }
        return out.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. Which check comes first?
  2. When is a voter stored?

Try these next