# Re: Microsoft Interview Questions

*From*: "Le Chaud Lapin" <jaibuduvin@xxxxxxxxx>*Date*: 21 Jan 2007 20:16:54 -0800

Ben Pfaff wrote:

"Le Chaud Lapin" <jaibuduvin@xxxxxxxxx> writes:

But if this is for a "regular" engineering position instead of

research, I would imagine that the purpose of the question would be to

probe the candidate to test familiarity with standard data structures

for implementing sets [the kind that Ben Pfaff have done so much work

with. :)]. If the candidate mentions binary tree/O(nlogn) without

asking about the order of extraction from source set of the numbers,

that would be not as good an answer as saying "I do not care about the

order of extraction. I choose Red-Black or AVL tree", in which case

O(nlogn).

That's an interesting suggestion, but I would have, personally,

guessed that the stipulation "no sorting" applied to other

methods that are equivalent to sorting. The construction of any

kind of binary search tree falls into that category, seeing as

a sorted array can be derived from the BST in O(n) time.

I did consider this fact before posting, but still felt that the

interviewer was looking for a stock answer. It is true that a BST

gives you a sort automatically, but technically speaking, you will know

the answer to Microsoft question either before the numbers are sorted,

or precisely at the point where the last element is inserted, in which

case, if the interviewer were to claim, "you cheated, you implemented a

sort..", the applicant could retort, "I found the answer to your

question without having to perform a sort...first." :)

But again, I doubt that the interviewer was looking for anything beyond

stock, obvious answers.

-Le Chaud Lapin-

.

**References**:**Microsoft Interview Questions***From:*kool_guy

**Re: Microsoft Interview Questions***From:*Chris Smith

**Re: Microsoft Interview Questions***From:*Le Chaud Lapin

**Re: Microsoft Interview Questions***From:*Ben Pfaff

- Prev by Date:
**Re: Microsoft Interview Questions** - Next by Date:
**Re: Graph Coloring** - Previous by thread:
**Re: Microsoft Interview Questions** - Next by thread:
**Re: Microsoft Interview Questions** - Index(es):