Re: Puzzle

From: CBFalconer (cbfalconer_at_yahoo.com)
Date: 11/06/04

  • Next message: CBFalconer: "Re: hashlib package" 
    Date: Sat, 06 Nov 2004 06:26:11 GMT

    Siddharth Taneja wrote:
    >
    > 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.

    The answer seems simple, but it doesn't belong here. This would be
    quite welcome on comp.programming. 

    -- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>  USE worldnet address!
  • Next message: CBFalconer: "Re: hashlib package"

    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)
    • Puzzle
      ... For an array of integers in sorted order, ... occurences of any integer, form an array which lists the integers just ...
      (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)