Loading...
Loading...
Loading...
Your hostel keeps a phone book of students. The warden gives you q commands, one per line:
put name number saves the number for that name. If the name is already there, the new number replaces the old one.get name asks for the number saved for that name.remove name deletes that name. If the name is not there, nothing happens.For every get, print the saved number, or -1 if the name is not in the book.
Build the phone book as your own hash map: an array of buckets, where each bucket is a chain (a linked list) of the names that land in it. Do not use java.util.HashMap, HashSet or any other ready-made map or set from java.util.
put name number, get name or remove name.get command, in order: the saved number, or -1.get.Example 1
Input
7 put ravi 98765 put asha 91234 get ravi put ravi 90000 get ravi remove asha get asha
Output
98765 90000 -1
The second put ravi replaces 98765 with 90000. After remove asha, the name is gone, so the last line is -1.
Example 2
Input
5 get kiran put kiran 99887 remove meena get kiran get meena
Output
-1 99887 -1
Removing a name that was never saved does nothing.
Try the problem first. Open one hint at a time.
An array of buckets plus a linked list in each bucket is all you need. Each list node keeps a name, a number and a link to the next node.
Turn a name into a bucket index with its hashCode(). That value can be negative, so use Math.floorMod(hash, buckets.length).
For put, walk the chain first. If the name is there, change its number; only otherwise add a new node.
For remove, keep a pointer to the node before the current one, so you can unlink a node from the middle of a chain. Double the array when the number of names passes three quarters of its length.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor