-2

An interveiewer asked me below question:

Search out unique integer values(approx. 1000) from a sorted array of billion records(like 1,1,1,1,3,3,3,4,5,5,6,6,6,6,6,7,7,7,7,7,7,8,8,8,8...........) with complexity less than O(n).
NOTE: NOt to use SET.

One solution that i tried to implement:

Divide that array into two set of arrays,then iterate both subarrays and search in hashmap if element doesnot exit,then add it into hashmap otherwise move to next iteration.

public static void main(String[] args) {
    int arr[] = {1,2,4,9,-3,5,6,3,6,12,5,6,2,-1,-3,6,87,9,2,3,5,7,9,1,0,1,3,5,7,6,3,8,6,3,21,45,6};
    int size1 =0, size2 = 0;
    HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
    System.out.println("length of Array:"+arr.length);

    if((arr.length)%2 == 0){
        size1 = size2 = arr.length/2;
    }else{
        size1 = (arr.length + 1)/2;
        size2 = (arr.length)/2;
    }

    for(int i=0;((size1-i-1)>= 0)||((size2+i)<(arr.length - 1));i++){
        if(map.containsKey(arr[size1 -i-1])== false){
            map.put(arr[size1 -i-1],arr[size1 -i-1]);
        }
        if(map.containsKey(arr[size2 + i]) == false){
            map.put(arr[size2 + i], arr[size2 + i]);
        }
    }

    System.out.println(map.keySet());

}

And its working as expected, then he asked what if we divide the array into n sets?

then the complexity would be O(1) or O(n/n)? Is it possible?

Please suggest if there is another way to implement the same without using hashmap?

Harsh
  • 39
  • 4
  • 5
    Do you want all unique values in the array? That would mean you would have to visit each element at least once, meaning it cannot ever be quicker than O(n), no matter what you do. – David ten Hove Nov 18 '14 at 13:34
  • 2
    Also, O(n/n) doesn't make any sense. That would just be O(1). – David ten Hove Nov 18 '14 at 13:36
  • 1
    Where were you interviewed? Someone asked the same question a few days ago: http://stackoverflow.com/q/26958118/209629 – vz0 Nov 18 '14 at 13:38
  • 1
    Of course it's still O(n) - like David said, it has to be. You're looping over n/k iterations, but do two k comparisons per iteration. That's just loop unrolling. And I would hope that the Interviewer's question about n subdivisions was meant to guide you to the realization that this doesn't work. – OhleC Nov 18 '14 at 13:39
  • @vz0: That should be made an answer, or this should be closed as a duplicate. Probably the latter. – keshlam Nov 18 '14 at 13:51
  • Relevant to Leeors answer, do you need to be quicker than O(n) in the worst, best or average case? – David ten Hove Nov 18 '14 at 14:00

2 Answers2

0

I'd try a binary search based approach, start from the middle element - if it's identical to one of the edges, then you can use the fact the array is sorted and eliminate that half. If it's different from each of the ones on the edges - divide the array into halves and proceed on each of them recursively.

This is still O(n) in the worst case, but on average it may be better then passing over the entire array (especially if there are many repetitions)

example -

1 1 1 1 1 2 2 2 2

could be done in two steps

Leeor
  • 19,260
  • 5
  • 56
  • 87
0

why don't you use a Set instead of Map. Anyways, Set does not allow duplicate elements.

public static void main(String[] args) {
    int arr[] = { 1, 2, 4, 9, -3, 5, 6, 3, 6, 12, 5, 6, 2, -1, -3, 6, 87,
            9, 2, 3, 5, 7, 9, 1, 0, 1, 3, 5, 7, 6, 3, 8, 6, 3, 21, 45, 6 };

    Set<Integer> aset = new HashSet<Integer>();

    System.out.println("length of Array:" + arr.length);

    for (int i : arr) {
        aset.add(i);
    }
    System.out.println(aset);
}
Naren Pamsa
  • 45
  • 5