Amazon Interview Question
Software Engineer / DevelopersTree Vs Hashes.
1.hashing cannot help in range queries.. while b trees or bst trees can help in range queries.
2.tree is a more compact and flexible when it comes to growing and shrinking in size. Hashing would waste a lot of space.
Hash Vs trees
1.tree does help in sorting but the use of map in c can also help in sorting.
2.Merging of two trees is difficult unless they are leftist trees( O(logn) merging), while merging two hashes is simpler.
3.insertion and deletion in tree logn , while the load factor governs the actual insertion or deletion time.
hashtable is better as it adds/searches elements in O(1) time, provided hashfunction uses a good algorithm to distribute elements in different buckets.
- Vaibhav March 20, 2010In bst, add/search is of order O(logN) and in tree its O(n), whereas in hashtable its O(1), hence hashtable is better here.
In hashtable, we keep elements in array, hence we use extra space and thus in terms of space complexity, tree is better.