Interview Question for Software Development Engineering Intern at Amazon.com:

Jun 23, 2012

public static int notRepeated(int[] given) {
  Map<Integer> m = new HashMap<Integer>();
  for(i=0; i < given.length; i++) {
    if(m.get(given[i])) {
      m.put(given[i], 2);
    }
    else
      m.put(given[i], 1);
    for(x:m) {
      if(x == 1)
        return x;
    }
  }
}

If you have an array of positive integers with only ONE non repeated integer, the easiest thing is just xor them all. Whatever you return will be the answer. Perl answer below

sub findNotRepeated{
        my ($arr) = @_;
        if(@$arr==0) {
                return - 1;
        }
        my $val = 0;
        foreach(@$arr) {
                $val ^= $_;
        }
        return($val);
}

sub findMissingElement{
        my ($arr,$arr2) = @_;
        if(@$arr==0 || @$arr2 == 0 ) {
                print " arr2=" .@$arr2 . "X\n";;
                return - 1;
        }
        my $val = 0;
        foreach((@$arr , @$arr2)) {
                $val ^= $_;
        }
        return($val);
}

first sort the array.n then
1)for i=1 to n
     {
      if ( element [i] !=element [i+1] )
           { cout<<element[i]
               break
            }
             else
                    { i=i+2
                     }
}

I dnt have any idea about its time complexity...

This answer is in-place with O(n) complexity. A slight improvement over the space complexity of the Hash Map answer.

public int returnNonRepeat(int[] input)
{
    if(input.length < 3) return -1;
    else
    {
        int repeat = null;
        if(input[0] == input[1]) repeat = input[0];
else if(input[0] == input[2]) return input[1];
else return input[0];
        for(int i = 2; i<input.length; i++)
        {
            if(input[i] != repeat) return input[i];
        }
    }
    return -1;
}

Cant use XOR as it fails when any element repeats odd number of times.....

Can use hash map with O(n) time and O(n) space