Puzzle

From: Siddharth Taneja (siddharth.taneja_at_gmail.com)
Date: 11/06/04 

Date: 5 Nov 2004 18:33:58 -0800

Heres one I heard-

For an array of integers in sorted order, which can have multiple
occurences of any integer, form an array which lists the integers just
once first, and then their duplicates in sorted order.

Thus for

1 1 1 2 2 3 9 9 9 10

the o/p should be

1 2 3 9 10 1 1 2 9 9

The algorithm should be O(n) in running time...and should use only
O(1) extra space.

Siddharth Taneja

Relevant Pages

  • Re: How many bytes per Italian character?
    ... 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. ... If with list we mean array, I could do a kind of binary search to find the place of insertion, and then insert. ... If Dr. Newcomer's caching succeeds then he doesn't have to visit all previous K-1 elements. ...
    (microsoft.public.vc.mfc)
  • 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: garbage collection problem in large linked lists
    ... Instead all buckets are allocated at once in an array. ... VG.net, which must be very scalable, but only for lists which would normally ... Linked lists require pointer dereferencing in order to traverse. ... When you run out of space, you allocate a new smaller array. ...
    (microsoft.public.dotnet.framework.performance)
  • Re: Dict sharing vs. duplication
    ... array to enforce unique keys and I use lists to enforce order. ... API in a page or two of Tcl code, it isn't so much a missing feature ... OpenACS database API which creates a new specialized data structure, ...
    (comp.lang.tcl)
  • Re: Translating python to scheme
    ... Scheme has mutation, and there are reasons to use it. ... confusing when considering a 2d array. ... in other languages: Lisp Lists and Vectors. ...
    (comp.lang.scheme)