Discussions

General J2EE: Implementing a Set

  1. Implementing a Set (5 messages)

    Hi All,
      Recently in an interview I was asked how to implement a Set. The question was -" How will you extract and prinout unique elements from an array?" I was not allowed to use any libraries like Hashtables etc. Only simple native programming was allowed to solve this problem.
      What you guys think is the best approach??


    Thanks
    G

    Threaded Messages (5)

  2. Implementing a Set[ Go to top ]

    The fastest asymptotic time I know for this is O(n logn). Simply sort the array using quicksort or mergesort and then run over it and print it as you go, ommiting duplicates, as in:

    for (int i=0; i<array.length; i++)
      if (i == 0 || array[i-1] != array[i]) print(array[i]);

    Gal
  3. Implementing a Set[ Go to top ]

    Thanks Gal. BUt wont sorting change the order of the array?

    George
  4. Implementing a Set[ Go to top ]

    A set generally doesn't have an order. The question said "unique printout", it didn't say anything about order preserving. Generally the semantics of "order preserving" in this context aren't clear. If you have several items of the same value, which one do you print?

    Gal
  5. Implementing a Set[ Go to top ]

    Hey Gal
     By order i mean suppose the initial array was :

    10,7,2,7,1,4,8,10,1
     
      Now if we have to print out the unique elements keeping order , the o/p will be :

    10,7,2,1,4,8
     
      But if we sort it, the order would change and the printout wud be :
      1,2,4,7,8,10

      I hope you got the point!

    Thanks
    G
  6. Implementing a Set[ Go to top ]

    Okay. So your specific requirement is to print the elements of the old array in the same order, eliminating all appearences of a specific item after the first appearence. You can do this (without any higher-order data structures) in a way similar to the algorithm I described above.
    Make an array of pairs consisting of the item and it's position in the original array. Now sort this array according to the items, and build a new array of pairs with no duplicate items. Now sort this array again according to position.
    The sort you use must be stable so that you don't eliminate the first item and keep a different one. You can use mergesort for instance. If you want to circuvement this problem, you can refine the ordering relationship on the pairs to use the position to decide the order between two pairs with the same item. That way the pair you keep will allways be the pair with the smallest position.

    Gal