Amazon Interview Question Software Engineer / Developers
Team: Amazon Music
Country: United States
Interview Type: Phone Interview
And a fact that your answer uses (for clarity of others) is that when a number is XOR'd with 0, it yields itself.
But then you will still have to store an array or HashMap for each number's count is this true?
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
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
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.
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 {
list.add(temp);
}
}
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);
}
}
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 {
list.add(temp);
}
}
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);
}
}
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.
*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
/*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
{
set.add(number);
}
}
for(int number : set)
{
System.out.println(number);
break;
}
}
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) {
set.add(arr[i]);
}
}
System.out.println("Odd Time Repeated Numbers : " + set);
}
}
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) {
set.add(arr[i]);
}
}
System.out.println("Odd Time Repeated Numbers : " + set);
}
}
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);
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) {
set.add(arr[i]);
}
}
System.out.println("Odd Time Repeated Numbers : " + set);
}
}
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
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)}"
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.
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)
- angshu1986 April 17, 2015