F5 Networks Interview Question
Software Engineer / DevelopersAlgorithm :The buckets array may have to be resized dynamically when a certain load factor is reached.the tree need to be balanced.
C++ STL Implementations:std::unordered_map,std::unordered_set for hashes and std::map for trees
Sorting:No in hashes Yes in Tree
Range Search :"
Runtime Complexity :Inserting: O(1) (normal case), O(N) (worst case, only with bad hash algorithm)
Searching: O(1) (normal case), O(N) (worst case, only with bad hash algorithm).
Inserting: O(log(n)) (when balanced)
Searching: O(log(n)) (when balanced)
Hash tables have high insertion complexity but other operations are constant time depending on the hash function. hashmaps or unordered are implemented using this.
- chennavarri November 11, 2010RBTrees is the widely used balanced binary tree which has logn for all operations. and not so easy to implement. Maps are implemented using this structure
So it depends on the application, if you know approx. what the size of your data would be then hashmaps are the best if not you need to choose.
An easier alternative to RBTrees are skip lists which are much easier to implement but same performance.
anyways, please reply your perspective on this problem. Thanks