Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
public class ArrayUtil {
public static Set<Integer> getOddTimesRepeatedNumbers(int arr[]) {
Set<Integer> result = new HashSet<>();
if (Objects.isNull(arr))
return result;
for (int data : arr) {
if (result.contains(data)) {
result.remove(data);
continue;
}
result.add(data);
}
return result;
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Random;
public class CalculateOddFRequency {
static ArrayList<Integer> arrList = new ArrayList<>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Random random = new Random();
int[] array = new int[200];
for (int i = 0; i < 200; i++) {
array[i] = random.nextInt(10);
}
ReturnOddTimesAppearingNumber(array);
if (arrList.size() > 0) {
for (int a : arrList) {
System.out.print(a + " ");
}
}
}
public static void ReturnOddTimesAppearingNumber(int[] array) {
HashMap<Integer, Integer> hm = new HashMap<>();
for (int num : array) {
if (hm.containsKey(num)) {
hm.put(num, hm.get(num) + 1);
}
else {
hm.put(num, 1);
}
}
for (Entry<Integer, Integer> entryset : hm.entrySet()) {
if (entryset.getValue() % 2 != 0) {
arrList.add(entryset.getKey());
}
}
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Random;
public class CalculateOddFRequency {
static ArrayList<Integer> arrList = new ArrayList<>();
public static void main(String[] args) {
// TODO Auto-generated method stub
Random random = new Random();
int[] array = new int[200];
for (int i = 0; i < 200; i++) {
array[i] = random.nextInt(10);
}
ReturnOddTimesAppearingNumber(array);
if (arrList.size() > 0) {
for (int a : arrList) {
System.out.print(a + " ");}}}
public static void ReturnOddTimesAppearingNumber(int[] array) {
HashMap<Integer, Integer> hm = new HashMap<>();
for (int num : array) {
if (hm.containsKey(num)) {
hm.put(num, hm.get(num) + 1);
}
else {
hm.put(num, 1);}}
for (Entry<Integer, Integer> entryset : hm.entrySet()) {
if (entryset.getValue() % 2 != 0) {
arrList.add(entryset.getKey());
}}}}
Here's a solution with Time Complexity: O(n) and Space Complexity: O(1)
1. Left shift 1 by each number in the array and maintain XOR result of these numbers.
(XOR eliminates all the even occurring numbers as A^A=0)
2. Again left shift 1 by each number and logically AND it with the XOR result. If the same number is returned then that number is occurring odd times.
Result for the above example: 1 2 10000 7 4 8
{code}
public static void printOddOccurringNumbers(int[] a) {
int xor = 0;
for (int i = 0; i < a.length; i++) {
int shifted = 1 << a[i];
xor ^= shifted;
}
for (int i = 0; i < a.length; i++) {
int shifted = 1 << a[i];
if ((shifted & xor) == shifted) {
System.out.print(a[i] + " ");
xor ^= shifted; //remove the odd times occurring number
}
}
}
{code}
//Amazon Question: You have given an array of integers. The appearance of integers vary (ie some integers appears twice or once or more than once) How would you determine which integers appeared odd number of times ?
//Using Dict C# (Hashmap alternate of Java)
//Time Complexity: O(N)
namespace Noofoccurenceofint
{
class Program
{
static void Main(string[] args)
{
int[] a = new int[] { 1, 1, 1, 2, 2, 5, 8, 9, 5, 9, 10 };
List<int> oddocc = OddTimes(a);
foreach(int n in oddocc)
{
Console.WriteLine(n);
}
}
public static List<int> OddTimes(int[] a)
{
Dictionary<int, int> D = new Dictionary<int, int>();
List<int> oddocc = new List<int>();
for (int i = 0; i < a.Length; i++)
{
if (D.ContainsKey(a[i]))
D[a[i]]++;
else
D[a[i]] = 1;
}
foreach(KeyValuePair<int,int> kvp in D)
{
if (kvp.Value % 2 != 0)
oddocc.Add(kvp.Key);
}
return oddocc;
}
}
sort the array - O(n logn)
additional space O(2)
traverse array O(n)
public static void printOddOccurNum(int[] nums) {
Arrays.sort(nums);
int prev=nums[0];
int c=1;
for (int i = 1; i < nums.length; i++) {
if(nums[i]==prev) {
c++;
}else {
if(c%2!=0) {
System.out.println(prev+":"+c);
}
prev = nums[i];
c=1;
}
}
}
#include <stdio.h>
int main(void) {
int a[]={1,1,1,2,5,1000,5,7,4,8};
int n,i,j,count=0,temp=0;
n=sizeof(a)/sizeof(int);
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("The numbers which appeared odd number of times and their count is\n{\n");
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(a[i]==a[j])
{
count++;
}
}
if(count%2!=0)
printf("%d\t %d\n",a[i],count);
i=i+(count-1);
}
printf("}") ;
return 0;
}
output:
The numbers which appeared odd number of times and their count is
{
1 3
2 1
4 1
7 1
8 1
1000 1
}
#include <stdio.h>
int main(void) {
int a[]={1,1,1,2,5,1000,5,7,4,8};
int n,i,j,count=0,temp=0;
n=sizeof(a)/sizeof(int);
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("The numbers which appeared odd number of times and their count is\n{\n");
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(a[i]==a[j])
{
count++;
}
}
if(count%2!=0)
printf("%d\t %d\n",a[i],count);
i=i+(count-1);
}
printf("}") ;
return 0;
}
output:
The numbers which appeared odd number of times and their count is
{
1 3
2 1
4 1
7 1
8 1
1000 1
}
#include <stdio.h>
int main(void) {
int a[]={1,1,1,2,5,1000,5,7,4,8};
int n,i,j,count=0,temp=0;
n=sizeof(a)/sizeof(int);
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("The numbers which appeared odd number of times and their count is\n{\n");
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(a[i]==a[j])
{
count++;
}
}
if(count%2!=0)
printf("%d\t %d\n",a[i],count);
i=i+(count-1);
}
printf("}") ;
return 0;
}
output:
The numbers which appeared odd number of times and their count is
{
1 3
2 1
4 1
7 1
8 1
1000 1
}
#include <stdio.h>
int main(void) {
int a[]={1,1,1,2,5,1000,5,7,4,8};
int n,i,j,count=0,temp=0;
n=sizeof(a)/sizeof(int);
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("The numbers which appeared odd number of times and their count is\n{\n");
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(a[i]==a[j])
{
count++;
}
}
if(count%2!=0)
printf("%d\t %d\n",a[i],count);
i=i+(count-1);
}
printf("}") ;
return 0;
}
output:
The numbers which appeared odd number of times and their count is
{
1 3
2 1
4 1
7 1
8 1
1000 1
}
#include <stdio.h>
int main(void) {
int a[]={1,1,1,2,5,1000,5,7,4,8};
int n,i,j,count=0,temp=0;
n=sizeof(a)/sizeof(int);
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[i]<a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("The numbers which appeared odd number of times and their count is\n{\n");
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<n;j++)
{
if(a[i]==a[j])
{
count++;
}
}
if(count%2!=0)
printf("%d\t %d\n",a[i],count);
i=i+(count-1);
}
printf("}") ;
return 0;
}
output:
The numbers which appeared odd number of times and their count is
{
1 3
2 1
4 1
7 1
8 1
1000 1
}
public static void findOddlyRepeatedNumbers(int a[]) {
if (a == null || a.length == 0) {
return;
}
HashMap<Integer, Integer> map = new HashMap<>(a.length);
int count = 0;
for (int i = 0; i < a.length; i++) {
if (!map.containsKey(a[i])) {
map.put(a[i], 1);
} else {
count = map.get(a[i]);
map.put(a[i], ++count);
}
}
Iterator<Entry<Integer, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Entry<Integer, Integer> entry = (Entry<Integer, Integer>) iterator.next();
int key = entry.getKey();
int value = entry.getValue();
if (value % 2 != 0) {
System.out.println(key + " repeated for " + value + " times");
}
}
}
Here's a solution with Time Complexity: O(n) Space Complexity: O(1)
Maintain an XOR result of all the numbers.
XOR can be used to eliminate the numbers occurring even number of times.
Use logical AND with each number and this XOR result, if the same number comes back it is occurring odd number of times.
The following code gives the result: 1, 2, 10000, 7, 4, 8
public static void printOddOccurringNumbers(int[] a) {
int xor = 0;
for (int i = 0; i < a.length; i++) {
int shifted = 1 << a[i];
xor ^= shifted;
}
for (int i = 0; i < a.length; i++) {
int shifted = 1 << a[i];
if ((shifted & xor) == shifted) {
System.out.print(a[i] + " ");
xor ^= shifted; //remove the odd times occurring number
}
}
}
guilhebl's answer is good, but you don't need to keep track of a count. This works without storing that extra data:
- yawgnimmeh May 07, 20161. Create a HashSet.
2. Traverse array and for each element check to see if it is in the hashset. If it is in the set, remove it and continue. Otherwise, add it to the set.
3. Return the set.