Re: How many bytes per Italian character?

"MrAsm" <mrasm@xxxxxxx> wrote in message news:03uf13p5v1grlv20e11119bbj38c6blbcg@xxxxxxxxxx
On Sat, 07 Apr 2007 13:32:45 -0400, Joseph M. Newcomer
<newcomer@xxxxxxxxxxxx> wrote:
But someone at MS told me that her standard interview question is "here is a list in sorted order. Write the code to insert a new element in sorted order" and of 27 interviewees, 26 failed to do it, and the only one who got it right was a PhD candidate, and she struggled to get it. I can do it with both LRU optimization for lookup and sublinear insert performance for large lists without thinking too hard about it.

With "list", do you mean "linked list"?
If with list we mean array, I could do a kind of binary search to find the place of insertion, and then insert. This would be a O(log(n)) algorithm, am I correct?

With a sorted array, it would be O(log(n)) to find the place where you're going to do an O(n) operation. Even if you do some caching, you'll still have to do an average of n/2 moves (i.e. O(n)) to keep it an array.

But if I have a linked list, accessing a list node with an integer key with O(1) performance is not possible, so I think that, to visit K-th element, I should be forced to visit all the previous (K-1) elements, am I correct?

If Dr. Newcomer's caching succeeds then he doesn't have to visit all previous K-1 elements. But I still don't quite see how it works. If the input is coming in randomly then on average you'll have to still have to examine K/4 elements (i.e. O(n)) past the place that was cached.

Of course in real life situations and with enough funding, you can figure out what non-randomness occurs in the input and then you can cache stuff to get the cost down.

.

Relevant Pages

  • Re: Puzzle
    ... > For an array of integers in sorted order, ... > occurences of any integer, form an array which lists the integers ... and then their duplicates in sorted order. ...
    (comp.lang.c)
  • Re: Suggestions for benchmarks for work on TList.Sorting.
    ... > I suggest that the benchmarks for sorts that are intended for ... > having the start data already the reverse of sorted order. ... > The TList.Sort programmer should be aware that some lists ... TList.Sort shouldn't be dereferencing the pointers anyway as they may ...
    (borland.public.delphi.language.basm)
  • Re: parsing directory
    ... the fully qualified names of all .png files in sorted order,ie in ... files declares functions to browse a directory and lists its content and is, if I recall correctly, also mentioned in the K&R book. ... If you have the list of file, you only need to do a string comparison on the file extension. ...
    (comp.lang.c)
  • Puzzle
    ... For an array of integers in sorted order, ... occurences of any integer, form an array which lists the integers just ...
    (comp.lang.c)
  • Suggestions for benchmarks for work on TList.Sorting.
    ... Please excuse me if the topics have already ... having the start data already the reverse of sorted order. ... The TList.Sort programmer should be aware that some lists ...
    (borland.public.delphi.language.basm)
Loading