Solutions to other chapters:
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26  
Java Methods Home Page Skylight Publishing



Java Methods A & AB:
Object-Oriented Programming and Data Structures

Answers and Solutions to Exercises

Chapter 24

3.   public int busiestHour(List<PhoneCall> dayCalls) { int[] counts = new int[24]; for (PhoneCall call : dayCalls) { if (call.getDuration() >= 30) counts[call.getStartHour()]++; } int maxHour = 0; for (int hour = 1; hour < 24; hour++) if (counts[hour] > counts[maxHour]) maxHour = hour; return maxHour; }
6. (a) F -- it is O(1)
(d) T -- for a reasonably functioning hash table; also, after several removals and additions, a BST may need rebalancing.
7. (b) A hashTable element takes 4 bytes, ListNode takes 8 bytes; Record takes 20 bytes. With 5 nodes per slot (on average) we need
    1000 * 4 + 5000 * (8 + 20) = 144,000 bytes
for the hash table. We need
    12000 * 4 + 5000 * 20 = 148,000 bytes
for the lookup table. The lookup table takes less than 3% extra space.

Finding a record in a hash table takes one hashCode computation plus, on average, three record comparisons. The retrieval operation will run four times faster with the lookup table.


Copyright © 2006 by Skylight Publishing