Other 2004 FR Questions FR other years Be Prepared Home
AB-2
Part (a)
  // precondition:  each entry in ballotList is a Set representing
  //                one voter's ballot
  // postcondition: voteCount.get(candidate) is the total number of
  //                times candidate appears on ballots in ballotList
  public VoterBallots(List ballotList)
  {
    voteCount = new HashMap(); 1

    Iterator iter = ballotList.iterator();
    while(iter.hasNext())
    {
      Set ballot = (Set)iter.next();
      Iterator ballotIter = ballot.iterator(); 2
      while (ballotIter.hasNext())
      {
        String candidate = (String)ballotIter.next();
        int count = 0;
        Object obj = voteCount.get(candidate);
        if (obj != null)
          count = ((Integer)obj).intValue();
        voteCount.put(candidate, new Integer(count + 1)); 3
      }
    }
  }
Notes:
  1. We could use a TreeMap as well.

  2. The outer loop iterates over all the ballots in ballotList; the inner loop iterates over all the candidates in the ballot.

  3. Integer is immutable, so we need to create a new Integer for the updated count and put it in the map.  If candidate is already in the map, the value associated with it is replaced.

Part (b)
  // postcondition: returns a set containing the candidate(s)
  //                with the most votes
  public Set candidatesWithMost()
  {
    Set bestCandidates = new HashSet(); 1
    Iterator iter = voteCount.keySet().iterator();
    Integer maxCount = maxVotes();

    while(iter.hasNext())
    {
      Object candidate = iter.next();
      Integer count = (Integer)voteCount.get(candidate);
      if (count.equals(maxCount)) 2
        bestCandidates.add(candidate);
    }

    return bestCandidates;
  }
Notes:
  1. You could pick TreeSet, but then Part(c) would become more difficult.

  2. Not
          if (count == maxCount)...
    because you are comparing Integer objects.  You could use
        int maxCount = maxVotes().intValue();
        ...
          int count = ((Integer)voteCount.get(candidate)).intValue();
          if (count == maxCount) ...
    
    but it is more error-prone.

Part (c)

O(C).

The time of the candidatesWithMost method consists of the time needed to call maxVotes, the time needed to iterate over all the candidates (i.e., over all the keys in the voteCount map), and the time for inserting matching candidates into bestCandidates. 1 

Since voteCounts is a HashMap, the time for traversing it in the maxVotes method and in the candidatesWithMost method is O(C). 2  Since bestCandidates is a HashSet, The time for inserting a candidate into it is O(1).  The total time is O(C). 3

Notes:

  1. Note that the votes have been already tallied in the constructor, so the individual voters are no longer represented anywhere and their number V is irrelevant.

  2. If voteCounts were a TreeMap, we'd have to multiply the traversal time by log C, because each get(...) call takes O(log C) time.  (You may argue it doesn't have to in a more efficient implementation of TreeMap traversal by keys, but there is no one to argue with at the AP exam.  It's better to just use a HashMap to be on the safe side.)

  3. The time for inserting a candidate into bestCandidates may potentially get you bogged down in the issue of what portion of C can match the best count, and so on.  To avoid that, make bestCandidates a HashSet, so that adding a value to is always O(1).  For a TreeSet, the total worst-case time (when all the candidates have the same count) would be O(C log C)


Other 2004 FR Questions | Back to Contents

Copyright © 2004 by Skylight Publishing
support@skylit.com