Amazon Interview Question: You are given an array with n... | Glassdoor

## Interview Question

Software Development Engineering Intern Interview Seattle, WA

# You are given an array with n positive integers where all

values in the array are repeated except for one. Return the one that is not repeated.
Tags:
data structures, programming, algorithm

1

public static int notRepeated(int[] given) {
Map m = new HashMap();
for(i=0; i &lt; 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;
}
}
}

Interview Candidate on Jun 23, 2012
1

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);
}

XOR it on Jul 16, 2012
1

first sort the array.n then
1)for i=1 to n
{
if ( element [i] !=element [i+1] )
{ cout&lt;

yogesh on Aug 2, 2012
0

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 &lt; 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

Caleb on Jan 4, 2013
0

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

syam on Feb 17, 2013
1

only 2 possible solutions
1.) using sorting
2.) using additional space. which will be less than o(n)

alien on Feb 20, 2013
0

sub find_odd {
my @a = @{\$_[0]};
my (\$i, \$n);

\$n = \$a[0];
for \$i (1 .. \$#a) {
\$n = \$n ^ \$a[\$i];
}
printf("number is %s\n", \$n);
}

Anonymous on Dec 2, 2015