Bloomberg LP Interview Question Software Engineer / Developers
I think a hash table with 26 buckets will be very inefficient for large data sets like a phone book, because there will be many collisions. Nowhere it says that list must be ordered. If you really want it ordered, use a binary tree.
Maybe the garbage collector is not working so we are not deleting the entries which go out of scope
When hash table becomes so large as to result into significant number of collisions, we expand the hash table. So maybe it exceeded 15Gb of size and it was doubled to 30Gb
It seems unlikely that such a large table could be stores on a 32 bit system. So it has to be on a distributed network
Maybe the garbage collector is not working so we are not deleting the entries which go out of scope
When hash table becomes so large as to result into significant number of collisions, we expand the hash table. So maybe it exceeded 15Gb of size and it was doubled to 30Gb
It seems unlikely that such a large table could be stores on a 32 bit system. So it has to be on a distributed network
Use 26 buckets corresponding to each alphabet and insert names in sorted order. So, if name starts with A insert in the first bucket, if its starts with B insert in second bucket. To make sure that all the names starting with A are stored in sorted order care must be taken while inserting them in the hash. Obviously there will be several collisions and that be handled by chaining. If the maximum length of the chain is K then the efficiency to insert or search for a particular entry will be O(log(k)). This is the best I know, if anyone knows a better answer please comment.
- gauravk.18 April 04, 2008