Re: Microsoft Interview Questions

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

Of course no one can read the mind of the Microsoft person who posed
the question, but I would think that the "no sorting allowed"
stipulation would be to prevent the candidate from sorting the numbers
in a fixed array, then doing a scan, which would yield O(n).

[...]

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.
--
Ben Pfaff
blp@xxxxxxxxxxxxxxx
http://benpfaff.org
.

Relevant Pages

  • Re: Balancing a Binary Tree
    ... a list personnel records into a BST, and if you had it compare them ... This sounds like sorting to me. ... a binary search tree, because a binary search tree has rules ... ordered set screws up performance in a BST might quantify how ...
    (comp.programming)
  • Re: Balancing a Binary Tree
    ... and the criteria is "files that contain the keywords". ... form of sorting. ... But, a binary search tree isn't a list, so it wouldn't fit my ... partial ordering is defined. ...
    (comp.programming)
  • Re: sorts with binary trees
    ... Sure you can do sorting with a binary search tree. ... and no similar material for fortran. ...
    (comp.programming)