Other 2005 FR Questions FR other years Be Prepared Home
Part (a)

The running times of the getCitiesForCode and addCityCodePair methods
are both O(1), because they call only HashMap's get and put
methods and HashSet's add method, which all run in O(1) time.

Part (b)

We need to add a map where each key is a city and its
associated value is a set of postal codes. If we make it a TreeMap,
traversing all cities in order (e.g., for printing) will be straightforward,
because this is the default sequence for any iterator over the TreeMap's keySet().

  // additional instance variable(s)

  private Map cityToCodeMap; // each key is a city, its
                             // associated value is a set of postal codes

  // constructs an empty database
  public PostalCodeDB()
    // initialization of additional instance variable(s)

    cityToCodeMap = new TreeMap();
The following statements should be added to the addCityCodePair method
(these statements are identical to the initial statements, but "code" and "city"
are swapped everywhere):

    Set codeSet = getCodesForCity(city);
    if (codeSet == null)
      codeSet = new HashSet();
      cityToCodeMap.put(city, codeSet);

Part (c)

The running time of the getCodesForCity method can be not worse than O(log N), because this method can rely on the TreeMap's get method, which runs in O(log n) time, where n is the number of keys, and there are no more than N keys (cities).

Part (d)
  // prints an alphabetical list of all cities in this database
  // postcondition: the state of the data structure is not changed
  public void printAllCities()
    Iterator it = cityToCodeMap.keySet().iterator();
  } 1
  1. Simply
      public void printAllCities()
    probably would be sufficient for the full credit, too.

Other 2005 FR Questions | Back to Contents

Copyright © 2005 by Skylight Publishing