Fast way to store employee objects via zip code lookup.
Ok so you have a hash map of employees keyed off a unique key of employee id. But you also want to be able to answer a question which is give me all employees that have the zip code XXXXX, or whatever. What is a fast way to do this? Keep in mind that when you insert/update/delete employees into this hashmap you must also manage any other data structure you have so that the zipcode index is balanced and accurate.
I had proposed to use another hashmap, where the key is the zip and the value is a linkedlist of pointers to the employees in the employee hashmap, but this becomes O(n) for insert/delete and lookup because you have to walk the entire list of elements in the linked list in the zipcode hashmap. Can we do better, any ideas on making this a faster index, lookup and make sure its balanced? Thanks
You could have your employee hashmap also have a pointer back to the correct element in the linked list of the zip code hashmap.
- Anonymous March 26, 2015Alternatively, you could handle this an easier way that requires no modification to the standard hashmap libraries. As each entry comes in, assign it an auto-incremented ID (use a 64-bit integer so you don't run out of IDs). Then take the employee record and insert into a hash map that maps ID to employee record. Then have two auxillary lookups, one for name -> id and another for zip -> list of IDs. You can see that this is nicely extensible in that you can extend this to as many search criteria as you want.