Re: Microsoft Interview Questions

kool_guy <yjaplomb@xxxxxxxxx> wrote:
I went to Redmond, WA for Microsoft interview, but got stumbled upon
two interview questions, I hope our experts can answer them for me.

Q1) You are given a set of n numbers, what is an efficient way to
determine whether there is any duplicate in the set? And what is your
run time? (Note: You are not allowed to sort the numbers first.)

No one seems to have addressed this part yet. In general, this is
called the element uniqueness problem. Under the algebraic decision
tree model, it has a worst-case complexity of O(n log n), which suggests
that you may as well do it by sorting and then scanning for duplicates.
Of course, you're forbidden from sorting, so I would have pressed for a
reason for this restrictions. Do they want to preserve the original
data? If so, then copy it elsewhere and then sort. If it truly is an
entirely arbitrary and unmotivated restriction, then I'd just throw up
my hands and give the obvious n^2 solution, assuming that there's no use
doing more work until I understand the requirements better than they are
willing to explain. After all, anything else you come up with may be
arbitrarily forbidden as well; for example, could you do a merge sort
but just abort as soon as you find a duplicate? That would sort lists
without duplicates, but it wouldn't sort a list if it had a duiplicate.
Would that count as sorting? Until you have a reasonably formed
problem, these semantic games are going to come up.

If you're willing to abandon algebraic decision tree and make additional
assumptions about your input, then you could do it in linear time.
You'd need a better assumption than "numbers", though. Are they
integers? Natural numbers? Constrained to fit within some range?

Chris Smith

Relevant Pages

  • Re: processing a large textfile
    ... The below is giving me context errors when i put ... Currently i don't need the regex part and sorting i want to sort the ... To sort and remove duplicates use, ... duplicate entries, from the error i'm getting there are something like ...
  • Re: Inserting a bunch of rows at once.
    ... can be sorted, and that only one entry per sort key would have been ... Microsoft MVP - Excel ... > the duplicate is where you want the blank row) ... > 7) Remove the filter - you should have desired result ...
  • Re: Need help sorting images.
    ... Do you want to sort a lot of images and then copy or move them ... Or are they already in subfolders and you want ... You'd still want a tool such as uniq to handle duplicate ... Because two cameras were used and one camera was left on PDT, ...
  • Re: Need help sorting images.
    ... In Windows Explorer add "Date Picture Taken" to the columns of the ... :>> I have been asked to sort a lot of images into subfolders based ... You'd still want a tool such as uniq to handle duplicate ... Because two cameras were used and one camera was left on PDT, ...
  • Re: large number, store and sort
    ... You can set an index to either accept or reject duplicate values. ... the 7 "sortable" digits. ... >>If you need to sort on just some of the digits it would ... >>Please respond in the newgroup and not by email. ...