Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Is it really working? Can you explain little bit more about how this program is working?
With the following [ 1, 2, 3, 3, 1, 3 ] input, output shows 1, instead of 3.
Syed: The example only works if there is one odd number 2 and 3 both occur an odd number of times so it wouldn't work in this case.
This works because when a number xor's with it self the result is zero.
1^1 = 0, 2^2=0,...
So if all values occur in pairs except for 1, the result is the odd one out.
public static void occurOddTimes(int[] arr){
Hashtable<Integer,Object> ht = new Hashtable<Integer,Object>();
Object seenOdd = new Object();
Object seenEven = new Object();
Integer intr;
for (int i = 0; i< arr.length ; i++)
{
intr = new Integer(arr[i]);
if(!ht.containsKey(intr)){
ht.put(intr, seenOdd);
}
else{
if(ht.get(intr) == seenOdd){
ht.put(intr, seenEven);
}
else{
ht.put(intr, seenOdd);
}
}
}
Set<Integer> set = ht.keySet();
Iterator iter = set.iterator();
while(iter.hasNext()){
intr = (Integer) iter.next();
if(ht.get(intr) == seenOdd){
System.out.println(intr);
}
}
}
Algorithm:
1) iterate through array.
if key doesn't exist in hashtable put it as seenOdd.
else toggle the values between seenOdd and seenEven
I have printed the values which occur odd number of times. You can add it to arraylist
Best approach to achieve O(N) and O(1) is to do XOR with 0. Even number of XORs will always return the number you are XORing with. For example, 0^6^6 = 0 and 0^6 = 6. So, code is -
public int findOdd(int[] input, int length) {
int toReturn = 0;
for (int i = 0; i < length; i++) {
toReturn ^= input[i];
}
return toReturn;
}
For the case when there is more than one number occurring odd number of times, use the following algorithm
create a hash table
for each x in array
if the x is found in the hash table
remove it from the HT
else
add it to the HT
The resulting hash table will eventually contain all the elements that occur odd number of times.
Best approach to achieve O(N) and O(1) is to do XOR with 0. Even number of XORs will always return the number you are XORing with. For example, 0^6^6 = 0 and 0^6 = 6. So, code is -
public int findOdd(int[] input, int length) {
int toReturn = 0;
for (int i = 0; i < length; i++) {
toReturn ^= input[i];
}
return toReturn;
}
if the array contains multiple elements with odd count, then to display the odd count elements with their no. of occurrences can be coded as:
int arr[] = {1,2,1,3,2,5,51,91,1,1,1};
Map<Integer,Integer> oddCount = new HashMap<Integer,Integer>();
Map<Integer,Integer> evenCount = new HashMap<Integer,Integer>();
for(int i=0;i<arr.length;i++){
if(oddCount.containsKey(arr[i])){
evenCount.put(arr[i],oddCount.get(arr[i])+1);
oddCount.remove(arr[i]);
}else if(evenCount.containsKey(arr[i])){
oddCount.put(arr[i],evenCount.get(arr[i])+1);
evenCount.remove(arr[i]);
}
else{
oddCount.put(arr[i],1);
}
}
Ankita Jain
int arr[] = {1,2,1,3,2,5,51,91,1,1,1};
Map<Integer,Integer> oddCount = new HashMap<Integer,Integer>();
Map<Integer,Integer> evenCount = new HashMap<Integer,Integer>();
for(int i=0;i<arr.length;i++){
if(oddCount.containsKey(arr[i])){
evenCount.put(arr[i],oddCount.get(arr[i])+1);
oddCount.remove(arr[i]);
}else if(evenCount.containsKey(arr[i])){
oddCount.put(arr[i],evenCount.get(arr[i])+1);
evenCount.remove(arr[i]);
}
else{
oddCount.put(arr[i],1);
}
}
public class Example3 {
/**
* @param args
*/
public static void main(String[] args) {
Integer[] input = { 1,1,2, 2, 3, 3,3 ,4};
Map<Integer, Integer> output = new HashMap<Integer, Integer>();
for (int i = 0; i < input.length; i++) {
if(output.get(input[i]) != null) {
continue;
}
int count = checkCount(input, i);
output.put(input[i], count);
if(count%2 != 0) {
System.out.println("The Number:-"+input[i]+"Has Count of"+count);
}
}
}
private static int checkCount(Integer[] input, int i) {
int count = 1;
for (int j = 0; j < input.length; j++) {
if (j != i) {
if (input[i] == input[j]) {
count++;
}
}
}
return count;
}
}
The solution I am posting will return all elements that occur an odd number of times. I am not sure if that is what is entirely desired, but hey, food for thought. Also, there is no need for maps/hashmaps
public static ArrayList<Integer> findOdd(int[] a) {
int max = 0;
for (int i = 0;i<a.length;i++) {
if (a[i] > max) {
max = a[i];
}
}
int[] counts = new int[max+1];
for (int j = 0; j < a.length; j++) {
counts[a[j]]++;
}
ArrayList<Integer> oddCounts = new ArrayList<Integer>();
for (int k = 0;k<counts.length;k++) {
if ((counts[k] % 2) == 1 ) {
oddCounts.add(k);
System.out.println(k);
}
}
return oddCounts;
}
Create a Binary search tree of struecture containing counter of that digit. how many times it occurs. Trace counter for odd 1 and print it . Below is my solution
#include <stdio.h>
#include <stdlib.h>
// structue for node
typedef struct node
{
int data;
int count;
struct node *right;
struct node *left;
} NODE;
/*
This function is for inserting new node in binary tree.
*/
void insert(NODE **root, int data)
{
NODE *temp;
if(*root == NULL)
{
temp=(NODE *)malloc(sizeof(NODE));
if(temp == NULL)
{
printf("Unable to allocate memory");
}
else
{
temp->data=data;
temp->count=1;
temp->left=NULL;
temp->right=NULL;
*root=temp;
}
}
else if(data < (*root)->data)
{
insert(&(*root)->left,data);
}
else if(data > (*root)->data)
{
insert(&(*root)->right,data);
}
else if(data==(*root)->data)
{
(*root)->count=(*root)->count +1;
}
}
void traverse(NODE **root)
{
if((*root)!=NULL)
{
if(((*root)->count)%2!=0)
printf("Value %d comes odd times\n",(*root)->data);
traverse(&(*root)->left);
traverse(&(*root)->right);
}
}
int findOdd(int *input, int length)
{
int i;
NODE *root=NULL;
for(i=0;i<length;i++)
{
insert(&root,input[i]);
}
traverse(&root);
}
int main(void)
{
int a[]={1, 2, 3, 1, 2, 3, 4, 5, 9, 10};
findOdd(a,10);
return 0;
}
My answer was:
int findOdd(int[] input, int length) {
if(input.size() == 1)
{
return input[0];
}
sort(&input);
counter = 1;
for(int i = 1; i < input.size(); i++)
{
if(input[i - 1] < input[i])
{
if(counter % 2 == 1)
return input[i - 1];
else
counter = 0;
}
counter++;
}
return input[input.size() - 1];
}
If we are not allowed to sort:
#include <iostream>
using namespace std;
int findOdd(int input[], int length)
{
int count = 0;
for(int i = 0; i < length; i++)
{
count = 1;
for(int j = 0; j < length; j++)
{
if (i == j) continue;
if (input[j] == input[i])
count++;
}
if (count % 2 == 0)
continue;
else
return input[i];
}
}
int main()
{
int input[] = {1,2,3,2,1,2,3,2,1};
int odd = findOdd(input, 9);
cout << odd;
return 0;
}
If there is only one element that occurs odd number of times...
- Mars.LeeZm November 21, 2012int value = 0;
for (int i =0; i<size;++i)
value = value ^element[i];
print value;