Bloomberg LP Interview Question
Financial Software DevelopersCountry: United States
Interview Type: In-Person
Hash tables are an extension to STL and are NOT using trees internally.
Inside hash map, the buckets are organized into vectors of lists and rehashed once the load factor is exceeded.
I might not have understood the question. The typical STL maps don't use hash tables, which is why I said what I did.
Perhaps the interviewer was asking about how I would implement a hash table.
Unless they were referring to the unordered maps introduced in the C++11 standard, the STL maps (std::map and std::multimap) maintain the elements in sorted order. This is required by the C++ standard. The standard does not require a specific implementation (just runtime complexity requirements), but having said that, most implementations that I am aware of use red-black trees. Since hash tables don't maintain sorted order, they don't meet the criteria for an STL map. Hash tables and buckets would make more sense in the context of std::unordered_map and std::unordered_multimap.
@kakavka : I'm sorry that's not accurate. STL maps use red-black balanced trees. For a pure hash table you should use unordered_map.
As for buckets I guess they refer to bucket sort which makes use of a hashing function, but all in all it's nothing but exploiting collisions at own advantage rather than minimizing them as you would do in a hash map.
Either the interviewer doesn't know their stuff or it's a trick question. STL maps use trees internally, I imagine balanced ones.
- eugene.yarovoi October 24, 2011