Microsoft Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
of 1 vote

Binary search tree: allows various operations on a set of
elements (create, find, find_min, find_max, insert,
If tree is “balanced” (expected depth of any node is O(logn)) the
average running time of all of the above operations is O(logn).
Worst case complexity is O(n).

Hash tables: support only a subset of the operations allowed by a search tree.
Operations that require ordering info among the elements, such as
find_min, and find_max, are not supported
Insertion, delete, and find: supported in constant
time on average.

More detailed:
* Hash tables have faster average lookup and insertion time (O(1)), while some kinds of binary search tree have faster worst-case lookup and insertion time (O(log n) instead of O(n)). Hash tables have seen extensive use in real time systems, but trees can be useful in high-security real time systems where untrusted users may deliberately supply information that triggers worst-case performance in a hash table, although careful design can remove that issue. Hash tables shine in very large arrays, where O(1) performance is important. Skip lists have worst-case operation time of O(n), but average-case of O(log n), with much less insertion and deletion overhead than balanced binary trees.

* Hash tables can have more compact storage for small value types, especially when the values are bits.

* There are simple persistent versions of balanced binary trees, which are especially prominent in functional languages.

* Building a hash table requires a reasonable hash function for the key type, which can be difficult to write well, while balanced binary trees and skip lists only require a total ordering on the keys. On the other hand, with hash tables the data may be cyclically or partially ordered without any problems.

* Balanced binary trees and skip lists preserve ordering — allowing one to efficiently iterate over the keys in order or to efficiently locate an association whose key is nearest to a given value. Hash tables do not preserve ordering and therefore cannot perform these operations as efficiently.

* Balanced binary trees can be easily adapted to efficiently assign a single value to a large ordered range of keys, or to count the number of keys in an ordered range.

This link might be useful for more insight

- algooz April 27, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

A BST may be used when the search needs to be done for a range of values. Since we know that the nodes of the left subtree hold values less than the root and that of the right hold values greater than the root, we can find the nodes containing a range of values easily.

Using a hash when looking for a range of values will need us to search for every value within that range. If most of the values dont exist then we are doing a lot of unnecessary searches. This doesnt happen for a BST.

- SS April 03, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

In case one wants to sort the elements , in case of binary tree it would be of O(n) where as in case of a Hash it would be of O(n^2)

- Anonymous May 03, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

If list has such numbers whose hash function evaluates to same hash key then inserting/retrieving such numbers is time consuming as compared to BST.

- Anonymous May 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 votes

question says perfect hashing,am assuming this means no collisions

- Anonymous October 26, 2008 | Flag
Comment hidden because of low score. Click to expand.
of 0 vote

BST is preferred :
- When there are as many Insert/Delete operations as Finds. i.e. if Finds are the dominating operations compared to insert/delete then hash will work else BST is better.
- When we want a sorted list or a bunch of elements in a range

- Anonymous January 03, 2010 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More


CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More