## Amazon Interview Question for Software Engineer / Developers

Team: Amazon Music
Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
12
of 12 vote

Xor all the numbers. The result will be the number appearing odd number of times. It is because when we XOR the same number with itself, the result is zero. Complexity O(n)

Comment hidden because of low score. Click to expand.
0

this is the most efficient way that I believe

Comment hidden because of low score. Click to expand.
0

And a fact that your answer uses (for clarity of others) is that when a number is XOR'd with 0, it yields itself.

Comment hidden because of low score. Click to expand.
0

But then you will still have to store an array or HashMap for each number's count is this true?

Comment hidden because of low score. Click to expand.
2

No. When you XOR a number with itself, you get 0. When you XOR 0 with something else, it becomes that something else. XORs are also commutative, which makes it work in any order you like.

2 ^ 2 ^ 3 = 2 ^ 3 ^ 2 = 3 ^ 0 = 3

Comment hidden because of low score. Click to expand.
0

This is not working for
int arr[] = { 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 };

output is 2 by xor approach

Comment hidden because of low score. Click to expand.
0

XOR approach works only when there is a single number that is repeated odd number of times. In your example, 5 and 7 both occur three times. So the final result is displayed as XOR of 5 and 7.
5 ^ 7 = 2.

Comment hidden because of low score. Click to expand.
0

what if an integer value exceed the size of an int, xor wouldn't work in that case?

int arr[] = { 99999, 99999 };

Comment hidden because of low score. Click to expand.
2
of 2 vote

Do xor operation on each array element and the final result would be answer
like
while( i < size(array) )
res = res ^ a[i];

print res

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````static void findoddrepeatedNo() {

int a[] = { 4, 5, 6, 4, 7, 8, 9, 5, 7, 6, 9, 8, 9 };
List<Integer> list = new ArrayList<Integer>();

for (int temp : a) {
if (list.contains(temp)) {

list.remove((Integer) temp);

}

else {
}

}

if (list.size() == 0) {
System.out
.println("array does not hav num repeated odd no of times ");
return;
}

for (int temp : list) {

System.out.println(temp);
}``````

}

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````static void findoddrepeatedNo() {

int a[] = { 4, 5, 6, 4, 7, 8, 9, 5, 7, 6, 9, 8, 9 };
List<Integer> list = new ArrayList<Integer>();

for (int temp : a) {
if (list.contains(temp)) {

list.remove((Integer) temp);

}

else {
}

}

if (list.size() == 0) {
System.out
.println("array does not hav num repeated odd no of times ");
return;
}

for (int temp : list) {

System.out.println(temp);
}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

#include <iostream>

using namespace std;

int main()
{
int a[9] = {2,2,3,3,4,4,5,5,6};
int xor2 = a[0];
for(int i =1;i<9;i++){
xor2 = xor2^a[i];
}
cout<<"The odd element is "<<xor2<<endl;

return 0;
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````int a[] = {2,2,7,5,7,5,1,2,1};
int m = 0;

int n = sizeof(a)/sizeof(a[0]);

for(int i = 0; i < n; i++){
m = m^a[i];
}
cout<<m;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a hashmap. Iterate through the input array and insert the elements one by one. If you find a number that has already been added to hashmap, delete entry from hashmap. The numbers occurring even number of times will cancel out. The only entry left in the hashmap at end is the number occurring odd number of times.

Comment hidden because of low score. Click to expand.
0
of 0 vote

*In your example you actually have 2 odd count numbers: 5 and 7

solution using a hashmap to store counts:

``````public class CountOddNumberOfTimesElement {

public static void main(String[] args) {

int a[] = {4,7,2,2,5,3,5,7,7,3,4,5,7};
System.out.println(findNumCountOddTimes(a));
}

public static int findNumCountOddTimes(int a[]) {
Map<Integer, Integer> mapCount = new HashMap<>();

for (int i = 0; i < a.length; i++) {
if (!mapCount.containsKey(a[i])) {
mapCount.put(a[i], 1);
} else {
Integer count = mapCount.get(a[i]);
count = count + 1;
mapCount.put(a[i], count);
}
}

for(Map.Entry<Integer, Integer> countEntry : mapCount.entrySet()) {
if (countEntry.getValue() % 2 != 0) {
return countEntry.getKey();
}
}
return -1;
}
}

// output: 5``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int[] testArray = {1,1,2,2,3,3,4,4,5,5};
int y=0;
for(int i:testArray)
y^=i;
System.out.println(y);``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public void getOddOccurance(int[] numbers){
int res = 0;
if(numbers.length >=2){
res = numbers[0] ^ numbers[1];
}else{
res = numbers[0];
}
for(int i=2;i<numbers.length;i++){
res = res ^ numbers[i];
}
System.out.println("Odd Occurance : "+ res);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Solution: 1. Create a HashSet "set" of Integers.
* 2. Loop through the array of integers
* 3. If set contains the integer then remove it. This means even occurance of the number
* 4. If set does not contain the integer add the integer to the set. This means odd occurance of the number
* 5. Loop through the set and return the first element.
*
* */

public static void problem4()
{
int[] a = {4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5, 7};

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

for(int number : a)
{
if(set.contains(number))
{
set.remove(number);
}
else
{
}
}

for(int number : set)
{
System.out.println(number);
break;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

package amazon;

public class FindOddNoOfTimesRepeatedNo {

/**
* @param args
*/
public static void main(String[] args) {
int arr[] = {1,1,7,22,22,3,3,3,3};

int sum =0;

for (int a : arr) {
sum ^= a;
}

System.out.println(sum);

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Java O(N) solution in time and space with hash table.

``````int find(int[] A){
HashSet<Integer> S = new HashSet<>();

for (int i = 0; i < A.length; i++){
if (S.contains(A[i])){
S.remove(A[i]);
}
else {
}
}

return S.iterator().next();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a stack , alternatievely push and pop when same number occurs. The remaining in the stack will be the answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class OddNumberOfTimes {
public static void main(String[] args) {
int[] arr = new int[] { 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 };
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
int counter = 1;
for (int j = 0; j < arr.length; j++) {
if (i == j) {
continue;
} else if (arr[i] == arr[j]) {
counter++;
}
}
if ((counter & 1) != 0) {
}
}
System.out.println("Odd Time Repeated Numbers : " + set);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class OddNumberOfTimes {
public static void main(String[] args) {
int[] arr = new int[] { 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 };
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
int counter = 1;
for (int j = 0; j < arr.length; j++) {
if (i == j) {
continue;
} else if (arr[i] == arr[j]) {
counter++;
}
}
if ((counter & 1) != 0) {
}
}
System.out.println("Odd Time Repeated Numbers : " + set);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``int[] arr = new int[] { 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 };Set<Integer> set = new HashSet<>();for (int i = 0; i < arr.length; i++) {int counter = 1;for (int j = 0; j < arr.length; j++) {if (i == j) {continue;} else if (arr[i] == arr[j]) {counter++;}}if ((counter & 1) != 0) {set.add(arr[i]);}}System.out.println("Odd Time Repeated Numbers : " + set);``

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class OddNumberOfTimes {
public static void main(String[] args) {
int[] arr = new int[] { 4, 7, 2, 2, 5, 3, 5, 7, 7, 3, 4, 5 };
Set<Integer> set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
int counter = 1;
for (int j = 0; j < arr.length; j++) {
if (i == j) {
continue;
} else if (arr[i] == arr[j]) {
counter++;
}
}
if ((counter & 1) != 0) {
}
}
System.out.println("Odd Time Repeated Numbers : " + set);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I assume the integers could be very large, ie > 64 so th so didn't think bitwise would work.

``````#!/usr/bin/perl -w
use strict;

my @int = (4,7,2,2,5,3,5,7,7,3,4,5);
my %seen = ();

print "array is ", join(",", @int),"\n";
for (my \$i = 0; \$i <= \$#int; \$i++) {
if (!defined(\$seen{\$int[\$i]})) {
\$seen{\$int[\$i]} = 1;
} else {
\$seen{\$int[\$i]}++;
}
}

print "odd count is :\n";
foreach my \$key (keys(%seen)) {
if (\$seen{\$key} && (\$seen{\$key} % 2) == 1) {
print \$key, " = ", \$seen{\$key},"\n";
}
}

./oddArray.pl
array is 4,7,2,2,5,3,5,7,7,3,4,5
odd count is :
5 = 3
7 = 3``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int temp = 0;

for(int i=0;i<arr.length;i++)
{
temp = temp^arr[i];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby impl. Running time: O(n). Space:O(1). Basically, it's zero-sum theory.

``````def find_odd_occuring(array)
return nil if array.nil? || array.length==0

sum=0

array.each do |value|
if sum<=0
sum+=value
else
sum-=value
end
end

sum
end

array = [4,7,2,2,5,3,5,7,7,3,4,5]

puts "Odd occuring: #{find_odd_occuring(array)}"``````

Comment hidden because of low score. Click to expand.
0

I take this back. This doesn't work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

XOR approach doesn't seem to work...

``````def find_odd_occuring(array)
return nil if array.nil? || array.length==0

array.reduce(&:^)
end

array = [4,7,2,2,5,3,5,7,7,3,4,5]

puts "Odd occuring: #{find_odd_occuring(array)}"``````

Returns 2, but expected value is 7.

Comment hidden because of low score. Click to expand.
0

Nm. The input is invalid to begin with

Comment hidden because of low score. Click to expand.
0

5 and 7 are present thrice each. So 5^7 = 2

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.