## Google Interview Question for Developer Program Engineers

• -4

Team: Bing
Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 5 vote

Time complexity = O(n)
Space = O(1)

``````void getEvenDuplicates()
{
int number[]={1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9} ;
int len = sizeof(number)/sizeof(number);
int tracker=0;

for(int i=0; i< len; ++i)
{
int shifted = 1<< number[i];
tracker ^= shifted;
}

for(int i=0; i< len; ++i)
{
int shifted = 1<< number[i];
if((shifted & tracker) ==  0)
{
tracker ^=shifted; // to avoid repeated printing of the number
cout<<number[i]<<endl;
}
}
}``````

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

This will work if the numbers are very small. If 10,000 appears, even if you use long long, it still fails.

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

Nice one Khush. I'd consider it 2 * O(n) but appreciable.

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

@Orion arm: Last time I checked, 2*O(n) = O(n)
@Khush:
wang891010 is right, your solution is not O(1), by adjusting your solution to any range of numbers, you are basically using a bit vector of size m, where m is: max-min

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

this wont work! int has only 32 bits. so any number bigger than 31 will fall off. for example if the array is {50,48,40,50,48,40,35}
"shifted" and "tracker" will be 0 the whole run.

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

Hi,
If the question is three of them are odd appear times and others are even times, I can solve.
I want you can make sure, is the question correct or not?

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

@zhang: yes solve ,but please give algo, no code

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

the example he gives is not correct. 5 appears 2 e.g. even amount of times

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

Hi, can you explain the question more detail? what is the "each integer is present an odd huber of time" meaning? Like give us some example.

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

Updated.

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

Hi,
is there any specific range of numbers like 1 to n ?
and also
a XOR a XOR a ---- - -- - - odd times = a
a XOR a ---- -- -- --- - even times = 0
In our case the number that we want to find out will become zero if we perform XOR only.
I am not sure that we can find out the repeated number using XOR only.
Thanks,
srinivas

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

"is there any specific range of numbers like 1 to n ? "
RE: No, no such thing like that.

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

didnt know google had a bing team :) im pretty sure atleast 90% of the questions in this site are not real.

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

how do you know that? and how did you get this "90%" number? by conforming each of these problems?

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

For each bit position from LSD to MSD (for value upto 9 max 4 bit poistions)
Go through the array and move all the values with bit 0 to the left and 1 to the right
have two pointer one from left and right
increment the left pointer until an interger with bit 1 in digit i is encountered
decrement the right pointer until an interger with bit 0 in digit i is encountered
swap these two
proceed above until left < right
This would have split the numbers into two groups
Performing this for all the 4 bits would have grouped the same numbers next to each other
now scan through the array from 0 to n-1
xor i+1..n until the number is different - count the occurence
print if count is even
now the new number to xor was the different one encountered during xor

Total number of scans through the array = no_bits * n + 1 * n = (no_bits+1) * n = O(N)
As the sort / grouping was done inplace no additional space used.
NOTE:Stack space might be used if the split on groups is performed recursively, just the left and right pointers for each recursive call

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

I realized that no_bits is typically 32( or 64) which is bigger than logn. So it's not better than a sort algorithm which is O(n*logn)

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

@xiaoxipan agreed

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

``````public class Fun {

// configured for positive, single digit integers per sample input.
static final int DIGITS = 1;

public static void main(String[] args) {

int[] counters = new int[10 * DIGITS];
int[] data = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };

for (int x = 0; x < data.length; x++) {
int index = data[x];

if (index > counters.length || index < 0) {
throw new RuntimeException("input Integer " + index + " out of range for data structure");
}

if (counters[index] == 0) {
counters[index] = 1;
}
else {
counters[index] ^= -1; // XOR with negative 1 to create one's
// complement per question requirement
// counters[index] = ~counters[index]; // equivalently, use
// uniary complement operator to create one's complement
}

}

// show the counter results
// 0 means not encountered
// +1 means odd
// -2 means even (one's complement of 1 = -2 and vice versa)
//System.out.println(Arrays.toString(counters));

// show the even numbers
for (int x = 0; x < counters.length; x++) {
if (counters[x] == -2) {
System.out.println(x);
}
}
}
}``````

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

[0, -2, 0, 0, 1, -2, -2, 1, -2, 1]
1
5
6
8

Your data has 2 instances of 5, so it should be in the results.

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

Hi,
I think you us a very good method, for this question. But in your method the Integer value always less than 10. If we can not know the limit of these integer, may be we can not use your way, because the Space Complexity: O(1), counters[] may take lots of memory, right?

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

yea i wouldn't agree thats a great solution because ur making a big assumption on the input if it contains 1 number that is 2^32 -1 then thats a lot of space ur requiring

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

why not simply increment counter instead of fancily using xor.

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

``````import Foundation

class Play {

func play() {

let numbers: Int[] = [1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9]

var dataBank: Int = 0

for number in numbers {
var slot = 1 << number
dataBank ^= slot // Toggle the bit everytime we find the same number in the sequence
}

dataBank = ~dataBank // Invert it so now the posistive bits represent the EVEN numbers we are looking for

for number in numbers {
if dataBank & (1 << number) > 0
{
// TODO: The even numbers will appear at multiple times
println("Even number found: \(number)")
}
}
}``````

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

Hi,
in your method you use Integer as a buffer. If the elements in the array is larger than 32... , how to solve this question?

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

This is an example of the so sought XOR solution and it works in case the number of possible different integers is less than a certain threshold like 128 or 64. You can always rely on a mapping (hashtable) solution if the elements are in a wide range of possible values.

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

``````unsigned int input[] = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};
unsigned int oddInputs=0;
for( unsigned int i = 0 ; i < sizeof(input)/sizeof(input) ; ++i){
oddInputs ^= ( 1 << input[i]);
}

std::cout << "OddInteger { ";

for( unsigned int i = 0 ; i < sizeof(input)/sizeof(input) ; ++i){
if(( oddInputs & ( 1 << input[i])) == 0 ){
oddInputs |= ( 1 << input[i] );
std::cout <<  input[i] << " ";
}
}
std::cout << "}";``````

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

I think we're misunderstanding this a bit. O(1) means constant space - that means the space is not varying with the input n. So in that case we can very well assume an extra int arr and then index the values of the original input straight into arr[value]++ ?

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

I think the sample output in the question is incorrect. It should be 1, 6, 8 and 5. From the input, it seems that 5 is repeated twice, which means it should be in the output.

Am I missing something or does the question specify we can arbitrarily pick 3?

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

this is for sure needs more questions to ask before attempting to solve,

1. what is the domain size, according to example [0-10] ( we will assume ),
so you just need a constant array, size 10, in this case and pass through the data
increment per index in second array and second pass print even or odd numbers

so memory O(1) - constant, time: N + 10, O(N)

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

Try to use a Bit version Trie?
Use a bit (namely, "time") to determine if a node represents a number, so you can use XOR ( time^=1 ) to determine if it appears odd times (if time == 1).
Traverse the trie, print those nodes with time == 1 (You also need to reconstruct the value of the node).

The time complexity is O(32*N) for 4-byte Integers = O(N), and the space complexity is bound by the maximum number of nodes in the trie (2^32). Although it seems large, it's O(1) by definition.

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

1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map

Code:

``````public static void findEvenOccurringNumbers(int[] a)
{
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

for (int num : a)
{
if (hash.containsKey(num))
{
hash.put(num, hash.get(num) ^ 1);
}
else
{
hash.put(num, 1);
}
}

for (Entry<Integer, Integer> entry : hash.entrySet())
{
if (entry.getValue() == 0)
{
System.out.println(entry.getKey());
}
}
}``````

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

Space comp. is O(N) ..

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

First sort the Array

public void FindEvenOccurance(int[] arr,int size)
{
int count,j;
for(int i=0;i<size;i++)
{
count = 1;
j=i+1;
while(j<size && arr[j]==arr[i])
{
count++;
j++;
}
if(count %2==0)
Console.WriteLine("Number"+ arr[i]);
i = j - 1;
}
}

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

``````public static void main(String[] args)
{
Integer [] input  = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

findEvenOccur(input);
}

public static void findEvenOccur(Integer [] input){

if(input == null || input.length == 0)
return;

HashMap<Integer, Boolean> countingMap = new HashMap<Integer, Boolean>();

for(Integer i : input)
{
Boolean isOdd = countingMap.get(i);
if(isOdd == null)
isOdd = false;
countingMap.put(i, isOdd ^ true);  //even occurence will have false, odd will have true.
}

for(Integer i : countingMap.keySet())
{
if(!countingMap.get(i))
System.out.println(i);
}
}``````

O(n) time
O(k) for the hashmap where k = the range of the numbers, and it's k <= n -3. Assume large n and small k, then it's constant.

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

import java.util.*;
public class SortNumber{

public static void main(String []args){

Integer[] hari= {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

ArrayList<Integer> newIn = new ArrayList<Integer>(Arrays.asList(hari));

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

for(Integer a: newIn){
int r = Collections.frequency(newIn, a);

if(r%2 == 0){
}
}

System.out.println(finalList);
}
}

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

import java.util.*;
public class SortNumber{

public static void main(String []args){

Integer[] hari= {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

ArrayList<Integer> newIn = new ArrayList<Integer>(Arrays.asList(hari));

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

for(Integer a: newIn){
int r = Collections.frequency(newIn, a);

if(r%2 == 0){
}
}

System.out.println(finalList);
}
}

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

Time COmplexity =O(n)
Space= O(1)

``````void getEvenDuplicates()
{
int number[]={1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9} ;
int len = sizeof(number)/sizeof(number);
int tracker=0;

for(int i=0; i< len; ++i)
{
int shifted = 1<< number[i];
tracker ^= shifted;
}

for(int i=0; i< len; ++i)
{
int shifted = 1<< number[i];
if((shifted & tracker) ==  0)
{
tracker ^=shifted; // to avoid repeated printing of the number
cout<<number[i]<<endl;
}
}
}``````

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

This solution assumes numbers are in the range [0, 31]. For arbitrary integers it would need a lot of bits.
Comments on a similar solutions in this thread explain how it requires O(logN) memory.

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

in ur example I/O 5 has even frequency

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

For this question, I think we can do it in O(n) time.
1. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.

The algorithm looks like this:

List<Integer> result = new ArrayList<Integer>();

int temp = num;
for (int i = 1; i < num.length; i++) ｛
temp ^= num[i];

for (int i = 0; i < 32; i++) {
int t = 0;
if ((1 << i) & temp == (1 << i)) {
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
if (result.size() == 3) {
break;
}
}
}

return result;

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

For this question, I think we can do it in O(n) time.
1. XOR all the numbers, then we will know which bit appears odd times.
2. As we get the result of step 1, we XOR all the numbers which contains 1 at kth bit. Then we can get three numbers after three loops. That's the answer we want.

The algorithm looks like this:

List<Integer> result = new ArrayList<Integer>();

int temp = num;
for (int i = 1; i < num.length; i++) ｛
temp ^= num[i];

for (int i = 0; i < 32; i++) {
int t = 0;
for (int j = 0; j < num.length; j++) {
if ((1 << i) & num[j] == (1 << j)) {
t ^= nump[j];
}
}
if (result.size() == 3) {
break;
}
}

return result;

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

public static void numTimes(int arr[]) {

HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int count = 1;
int tempVar;
// Sort array
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1; j++) {
if (arr[i] < arr[j + 1]) {
tempVar = arr[j + 1];
arr[j + 1] = arr[i];
arr[i] = tempVar;
}
}
}

// add values in hash map
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
count++;
} else {
hm.put(arr[i], count);
count = 1;
}

}

for (Map.Entry<Integer, Integer> e : hm.entrySet()) {
if (e.getValue() % 2 == 0) {
System.out.print(e.getKey() + " ");
}
}

}

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

run quick sort with O(nlogn) average case, then check if even or odd

``````public void getEven(int array[], int max){
Sort(array, 0, max);
int checker = 1;
int val = array;
for(int i = 1; i<=max; i++){
if(array[i] == val){
checker = checker ^1;
}
else{
if(checker == 0)
System.out.println( array[i-1]);
val = array[i];
checker = 1;
}
}
if(checker == 0)
System.out.println( array[max]);
}

private void QuickSort(int array[], int left, int right){
int i = left, j = right;
int tmp;
int pivot = (right-left)/2 + left;
while (i <= j) {
while (array[i] < array[pivot])
i++;
while (array[j] > array[pivot])
j--;
if (i <= j) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
}
if (left < j)
Sort(array, left, j);
if (i < right)
Sort(array, i, right);
}``````

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

run QuickSort O(nlogn) then check for even/odd

``````public void getEven(int array[], int max){
Sort(array, 0, max);
int checker = 1;
int val = array;
for(int i = 1; i<=max; i++){
if(array[i] == val){
checker = checker ^1;
}
else{
if(checker == 0)
System.out.println( array[i-1]);
val = array[i];
checker = 1;
}
}
if(checker == 0)
System.out.println( array[max]);
}

private void QuickSort(int array[], int left, int right){
int i = left, j = right;
int tmp;
int pivot = (right-left)/2 + left;
while (i <= j) {
while (array[i] < array[pivot])
i++;
while (array[j] > array[pivot])
j--;
if (i <= j) {
tmp = array[i];
array[i] = array[j];
array[j] = tmp;
i++;
j--;
}
}
if (left < j)
Sort(array, left, j);
if (i < right)
Sort(array, i, right);``````

}

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

assume x1,..,xn: odd times,
y1,..,ym: even

x1^x2^...^xn ^ y1 ^...^ym = x1^x2^...^xm = t.
--> t ^ x[i] < t.
and t ^ y[j] > t.

complex: O(N)
space: O(1)

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

int p[] = {1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9};

int cnt = 1;
int n = 17;
int pos;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (p[i] == p[j])
{
cnt++;
pos = j;
for (; pos < n - 1; pos++)
p[pos] = p[pos + 1];
j--;
n--;
}
}
if (cnt % 2 == 0)
cout << p[i] << endl;
cnt = 1;
}

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

Im not sure if this would be the solution.
I would create empty array, and start adding the items of the array. each new addition would do a XOR comparation with the items of the new array. in case XOR result is 0, it means we have, at that moment, a pair, so we can proceed to delete the item from the array. at the end of the full array we would end with the result array.

not really sure that the time complexity is o(N) exactly, but should be pretty close.

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

Space Complexity should be O(1)

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

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

The way I would approach this problem is that I would create a bitmask ( assuming that the digits that are being used are 0-9). As I go over the array I would take the bitmask -lets call it x - and take x XOR (1 << num) . When I am done iterating over the array I would go over the bitmask and see which bits have 0.

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

Sort the array, then compare the items, if they are equal using xOR, leave them in there and try with i+1 (compare xor with 3 elements) if they are odd, then try it with the 4th element. this way we know how many comparations of the numbers we are having and when they are not the same number (xOR is not 0). this way we know which numbers are odd and we can remove them from the array. The comparation index will jump to the last compared item. time complexity o(N) space o(1)

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

you didn't include the time to sort the array. If the array is sorted then its simple XOR start to end which O(n) and space O(1), but what if it is unsorted and sorting may take O(nlogn)

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

5 appears an even number of times but is not included in the output. Typo?

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

XOR based only? Stop posting "puzzles". Google would never impose idiotic restrictions like these.

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

It is unlikely Google asked this. And if someone did, the committee SHOULD throw it out (Unless they were busy that day).

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

``````Dictionary<int, int> counts = new Dictionary<int, int>();
int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };

foreach( int i in input)
{
int count;

if (counts.TryGetValue(i, out count))
{
counts[i] = i ^ count;
}
else
{
counts[i] = i;
}
}

foreach( var pair in counts)
{
if ( pair.Value == 0 )
{
Console.WriteLine(pair.Key);
}
}``````

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

``````Dictionary<int, int> counts = new Dictionary<int, int>();
int[] input = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };

foreach( int i in input)
{
int count;

if (counts.TryGetValue(i, out count))
{
counts[i] = i ^ count;
}
else
{
counts[i] = i;
}
}

foreach( var pair in counts)
{
if ( pair.Value == 0 )
{
Console.WriteLine(pair.Key);
}
}``````

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

The space complexity of O(1) is little bit on the harsher side but here are the steps to get required output

Step1: Sort the integer array using LSD Redix sort. LSD Redix sort uses O(k.N) time where k is a constant and depends on the length of the value to be sorted. For example for integer it will be 32 bit. It does not depend on the length of the input.

For LSD redix sort, ideally a new array is used to store the indexes of the input elements. But instead due to O(1) space requirement, we can use a a String variable which will store indexes.
So for input 1 appearing 3 times, 4 appearing 2 time and 15 appearing 3 times, the string can be
countString = "1-3_4-2_15-3_... etc
indexString would then be appropriately created identifying the indices for the elements.

Step2: After sorting the array, the array will have some elements 3 times and some 2 times.

Now start from index 0, i=0
If (i ^ i+1 ^ i+2) == i then ignore this number and move i = i+3;
if (i ^ i+1 ^ i+2) != i then print this number and move i = i+2;

Total time taken:
Step1: For LSD redix sort O(k.N) --> k is constant. Space complexity with string hack = O(1)

Step2: For loop O(N)

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

Redix sort takes O(k+N) space. See wikipedia.

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

- Open a 2^32 sized bit array (512 mb) and initialize it to all 0.
- Scan the given array, for every integer, "toggle" the corresponding bit:
e.g. for integer 12, if 12th bit is 0, set it to 1, if it was 1 (saw 12 before) set it to 0
-- now, you will have bits set to 1 for odd elements, and bits set to 0 for even elements
- Scan the given array once more, check the bit for every element, if you see a bit 0 for any element, emit that

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

if extra memory can be used, a simple hash map/set does the work whose time/space complexity is both O(n)

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

Inspired by Phoenix's solution I found another solution that doesn't need to alter the input array. I put all the code here: 1. My solution; 2 Solution based on Phoenix's 3 test cases:

``````#include <time.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <iostream>
#include <utility>

#include <vector>

int firstBit1( int x ){
//given x, return the index of the first 1 bit of x
for( int i = 0; x ; x >>= 1, ++i ){
if( x&1 )//test whether the i-th bit of x is 1
return i;
}
return -1;
}

bool find2( std::vector<int> &arr, int &a, int &b, int skip ){
//given a, b occur odd times in arr, others occur even times, return a, b
//with the extra condition: skip all elements that equal to "skip"
int x = 0;
for( int v : arr ){
if( v==skip )continue;
x ^= v;
}
int bit = firstBit1( x );
if( bit == -1 )return false;//invalid input

a = b = 0;
for( int v : arr ){
if( v==skip )continue;
else  b^= v;
}
return true;
}

bool found( std::vector<int> &arr, int a ){
//check whether "a" occurs odd times in arr
bool odd = false;
for( int v : arr )if( v==a )odd = !odd;
return odd;
}

bool find3( std::vector<int> &arr, int &a, int &b, int &c ){
a = b = 0;
int bits = sizeof(int)*8;
for( int i = 0;i < bits; ++ i ){
for( int v : arr ){
else b^= v;
}
if( found(arr, a) ){
return find2( arr, b, c, a );
}
else if( found(arr, b) ){
return find2( arr, a, c, b );
}
}
return false;
}

void createTestCase( std::vector<int> &arr, int &a, int &b, int &c ){
//3 different numbers a, b, c
int max = 10, max_occur = 10;
b = rand()%max;
if( b == 0 || b==max-1 )b = max/2;
a = rand()%b;
c = b + 1 + rand()%(max-1-b);
std::vector<int> different_numbers(max, 0);

different_numbers[a] = (2*(rand()%max_occur)+1)%max_occur;
different_numbers[b] = (2*(rand()%max_occur)+1)%max_occur;
different_numbers[c] = (2*(rand()%max_occur)+1)%max_occur;

int n = 0;
for( int i = 0;i < max; ++ i ){
if( different_numbers[i] == 0 ){
different_numbers[i] = (2*(rand()%max_occur))%max_occur;
}
n += different_numbers[i];
}

arr.resize(n);
for( int i = 0, k = 0; i < max; ++ i ){
for( int j = 0;j < different_numbers[i]; ++ j ){
arr[k++] = i;
}
}

std::random_shuffle( arr.begin(), arr.end() );
}

void bitBasedGroup( std::vector<int>::iterator from, std::vector<int>::iterator to, int bit, int max_bits ){
if( bit == max_bits || to <= from )return;

auto bit0_it = from - 1;
for( auto it = from; it != to; it ++ ){
if( 0 == (mask & *it) ){
std::swap( *it, *(++bit0_it) );
}
}
//	for( auto it = from; it != to; it ++ )std::cout << *it << ' ';
//	std::cout << std::endl;

++ bit0_it;
bitBasedGroup( from, bit0_it, bit+1, max_bits );
bitBasedGroup( bit0_it, to, bit+1, max_bits );
}

void printArray( std::vector<int> &arr ){
std::cout << '[';
for( int v : arr ) std::cout << v << ' ';
std::cout << ']' << std::endl;
}

void bitBasedGroup( std::vector<int> &arr ){
int max = *std::max_element( arr.begin(), arr.end() );
int bits = 0;
for( ; max; max >>=1 ) ++ bits;
bitBasedGroup( arr.begin(), arr.end(), 0, bits );
}

bool find3ByGroup( std::vector<int> &arr, int &a, int &b, int &c ){
if( arr.size() < 3 )return false;

bitBasedGroup( arr );

int X, found = 0;
int prev = arr;
bool odd = true;
for( int i = 1;i < arr.size(); ++ i ){
int v = arr[i];
if( v == prev ){
odd = !odd;
}
else{
if( odd && found<3 )X[found++] = prev;
prev = v; odd = true;
}
}
if( odd && found<3 )X[found++] = prev;
if( found != 3 )return false;
a = X; b = X; c = X;
return true;
}

int main(){
srand( time(0) );

for( int i = 0;i < 1000; ++ i ){
int X;
std::vector<int> arr;
createTestCase( arr, X, X, X );
printArray( arr );
std::cout << "a:" << X << ' ' << "b:" << X << ' ' << "c:" << X << std::endl;

int Y;
find3( arr, Y, Y, Y );
std::sort( Y, Y+3 );
assert( std::equal(X,X+3,Y) );

find3ByGroup( arr, Y, Y, Y );
printArray( arr );
std::sort( Y, Y+3 );
assert( std::equal(X,X+3,Y) );
}
}``````

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

the space complexity is O(1) however the time complexity is O(32*n). Even O(32*n) is also O(n), actually since 32 >= logn, this is bigger than O(n*logn), which means actually we can just sort. So still looking for a real O(n) approach.
By the way, I tried to delete my post but always failed.

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

xor it with the entire array and count the number of zeros.
if it is even, display it and delete its occurrences from the array.
repeat until array is empty or end of array is reached
deleting = O(n)

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

1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map

Code:

``````public static void findEvenOccurringNumbers(int[] a)
{
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();

for (int num : a)
{
if (hash.containsKey(num))
{
hash.put(num, hash.get(num) ^ 1);
}
else
{
hash.put(num, 1);
}
}

for (Entry<Integer, Integer> entry : hash.entrySet())
{
if (entry.getValue() == 0)
{
System.out.println(entry.getKey());
}
}
}``````

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

May be this would be better:

``````public static final int[] findDuplicates(final int[] data) {
// take a copy of the data.
int[] sorted = Arrays.copyOf(data, data.length);
// sort it. This is O(n log(n)) which will be the bulk of our time.
Arrays.sort(sorted);

// now scan the sorted data for even-numbered sequences of values.
int len = 0;
boolean even = false;
// sorted is our first sequence, and currently it is not even.
// note that the scan starts at position 1.
for (int i = 1; i < sorted.length; i++) {
if (sorted[i] == sorted[len]) {
// this element is the same as the sequence, so 'count' the even-ness.
even = !even;
} else {
// this element is different to our sequence, it's a new sequence.
if (even) {
// the old sequence had an even count, so we 'preserve' it.
len++;
}
// move the value of the new sequence to the 'beginning'.
sorted[len] = sorted[i];
// and the new sequence is odd.
even = false;
}
}
if (even) {
// the last sequence was even, we preserve it.
len++;
}
// return the first part of the array, which contains the even sequence values.
return Arrays.copyOf(sorted, len);``````

}

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

1) The solution should be XOR based only.
2) Arrays.sort = Time complexity: O(NlogN)
Expected Time complexity: O(N)

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

Space complexity: O(1)
Using Hashtable --> O(N)

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.