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.

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();
  }

    ...

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

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).

  // 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();
    while(it.hasNext())
      System.out.println(it.next());
  } 1

1. Simply

     public void printAllCities()
     {
       System.out.println(cityToCodeMap.keySet());
     }

   probably would be sufficient for the full credit, too.