Google Interview Question
SDE1sCountry: India
Interview Type: In-Person
Thsi is wrong. The problem statement only said "number", not "32 bit integer". What if you're using python where the numbers have no size limits?
I was thinking along the same lines, to use a bitmap and for each integer found if its set, unset it, else, set it. The value set in the end will be the value with even frequency, but i disregarded it because thats a lot of memory
My solution is to use 2 Hash maps so that when count turns to even - you delete from "odd map" and add to "even map". Algorithm complexity is O(n) - due to every operation on hash map is O(1).
public class SS {
static class EvenCount {
public Set<Integer> evenTimes(int[] input) {
HashMap<Integer, Integer> odd = new HashMap<Integer, Integer>();
HashMap<Integer, Integer> even = new HashMap<Integer, Integer>();
for (int i = 0; i < input.length; ++i) {
int current = input[i];
Integer oddCurrent = odd.get(current); // 1
Integer evenCurrent = even.get(current); // 1
if (notOdd(oddCurrent) && notEven(evenCurrent)) {
odd.put(current, 1); // 1
} else if (notOdd(oddCurrent)) {
odd.put(current, evenCurrent + 1); // 1
even.remove(current); // 1
} else if (notEven(evenCurrent)) {
even.put(current, oddCurrent + 1); // 1
odd.remove(current); // 1
}
}
return even.keySet();
}
private boolean notOdd(Integer integer) {
return integer == null;
}
private boolean notEven(Integer integer) {
return integer == null;
}
}
public static void main(String[] args) {
System.out.println(new EvenCount().evenTimes(new int[]{1, 2, 2, 3, 3}));
}
}
Can you use one hashmap instead? The complexity will be O(n) as well. For each number in the array, count the occurrences. Assign number as key, and the count of occurrences as value in the hashmap. In the end, if the value is even, show the key.
public static void countEvenNumbers(int [] array)
{
HashMap<Integer, Integer> countNumber = new HashMap<Integer, Integer>();
for (int i=0; i<array.length; i++)
{
countNumber.put(array[i], countNumber.containsKey(array[i]) ? countNumber.get(array[i]) + 1 :1);
}
for (Entry<Integer, Integer> entry : countNumber.entrySet())
{
if (entry.getValue() % 2 == 0)
{
System.out.println(entry.getKey());
}
}
}
Java solution, returns the number which occurs even number of times.
public Integer findItemWEvenOcc(int[] in)
{
Map<Integer, Integer> myMap=new HashMap<Integer,Integer>();
for(int i : in)
{
if(!myMap.containsKey(i))
{
myMap.put(i, 1);
}
else
{
int numberOfOccurance=myMap.get(i);
numberOfOccurance++;
myMap.put(i, numberOfOccurance);
}
}
for(Map.Entry<Integer, Integer> kv : myMap.entrySet())
{
if(kv.getValue()%2==0)
{
return kv.getKey();
}
}
return null;
}
{{
package com.algo;
public class EvenCount {
public int eventCount(int[] a) {
int output = 0;
for (int i = 0; i < a.length; i++) {
output = output ^ a[i];
}
return output;
}
public static void main(String[] args) {
int[] a = { 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3 };
EvenCount count = new EvenCount();
System.out.println(count.eventCount(a));
}
}
}}
Not Correct.
The logic which you are trying is for array having numbers that occurs even number of times except one that occurs odd number of times. In this case, doing a XOR of all the numbers will give you the correct result. However not true for this case though.
1st Approach: Using sorting and then iterating over the array to see which element has an even count.
Time: O(n lg n)
Space: O(1)
2nd Approach: Use a hashmap to keep a count of the number of times a number occurs. Then iterate over the hashmap to find which number has occured even number of times.
Time: O(n)
Space: O(n) (Worst case: could be if all the elements appear once except one that occurs twice which leads to a space requirement of O(n))
However an approach which could give the correct result in O(n) time and O(1) space is the one i guess is required in this case.
I spent an hour, still haven't find a better solution (O(n) time and O(1) space).
I can only optimize your 2nd approach by storing a boolean instead of count for smaller storage.
Actually, this is O(n) time and O(1) space.
The space needed is the range of Integer which is a constant. Max range is Integer.MAX_VALUE - Integer.MIN_VALUE + 1.
You need O(n+k) time and O(k) space.
If n is large, then it's O(n) time and O(1) space.
(function() {
'use strict';
var checkOddAry = function(inputAry) {
var numObj = {};
var i = 0;
var length = inputAry.length;
for (i = 0; i < length; i++) {
numObj[inputAry[i]] = !numObj[inputAry[i]];
}
for (i in numObj) {
if (numObj.hasOwnProperty(i)) {
if (numObj[i] === false) {
return i;
}
}
}
return false;
};
var inputAry = [1, 1, 2, 2, 3, 4, 5, 5, 4, 1, 2, 3, 4, 5];
console.log(checkOddAry(inputAry));
inputAry = [];
console.log(checkOddAry(inputAry));
inputAry = [1, 2, 1];
console.log(checkOddAry(inputAry));
})();
My Solution in python. Time complexity is O(n)
testArr = [1,1,1,4,4,4,9,5,9,6,9,10,8,10]
def returnEven(arr):
lenofArr = len(arr)
"""
initilize data
"""
storeCount = {}
seen = set()
current = arr[0]
storeCount[current] = 1
seen.add(current)
for i in range(1, lenofArr):
if arr[i] == current:
storeCount[current] += 1
else:
current = arr[i]
if current in seen:
storeCount[current] +=1
else:
seen.add(current)
storeCount[current] = 1
for k,v in storeCount.items():
if v % 2 == 0:
return k
return None
print(returnEven(testArr))
10
import java.util.*;
public class HelloWorld{
public static void main(String []args){
int[] a={2,2,2,3,3,3,4,4,5,5,5,6,6,6};
ArrayList<Integer> Num=new ArrayList<Integer>();
ArrayList<Integer> Count=new ArrayList<Integer>();
Num.add(a[0]);
int count=1;
for(int i=1;i<a.length;i++)
{
if(a[i]==a[0])
count++;
}
Count.add(count);
for(int i=0;i<a.length;i++)
{
if(Num.contains(a[i]))
{
continue;
}else // if not contain. add new node for a[i], count counts from i~length-1
{
Num.add(a[i]);
count=1;
for(int j=i+1;j<a.length;j++)
{
if(a[j]==a[i])
count++;
}
Count.add(count);
}
}
for(int i=0;i<Count.size();i++)
{
if(Count.get(i)%2==0)
{
System.out.print(Num.get(i));
break;
}
}
}
}
If we use a Set, we can do this at O(n).
If str is not existed -> add
if str is existed -> delete
That is, odd number occurrence will lead "existence". However, even number occurrence will lead "not existence" in a set.
public static Optional<String> findEvenNumberExistedWord(String[] arr) {
Set<String> cache = new HashSet<>();
for (String str : arr) {
if (!cache.add(str)) {
cache.remove(str);
}
}
for (String str : arr) {
if (!cache.contains(str)) {
return Optional.of(str);
}
}
return Optional.absent();
}
public static void main(String[] args) {
String[] input = {"abc","def","klm", "lod", "lod", "abc","def","klm" , "abc","def","klm"};
Optional<String> result = findEvenNumberExistedWord(input);
print(result.get());
}
How about an O(n) complexity with O(1) memory? Simple count the number of binary 1's in each number. For every count that has an even number of 1s and is greater than 0, output a 1.
public int evenInt(int[] a){
int[] bitCount = new int[32];
for(int numb : a){
indexCount(numb, bitCount);
}
return computeEvenBits(bitCount);
}
private void indexCount(int numb, int[] bitCount){
int pos = 0;
while(numb != 0){
bitCount[pos] += (numb & 1);
numb = numb >> 1;
pos++;
}
}
private int computeEvenBits(int[] bitCount){
int retVal = 0;
for(int i = 31; i >= 0; i--){
if(bitCount[i] > 0 && bitCount[i] % 2 == 0){
retVal++;
}
retVal = retVal << 1;
}
return retVal;
}
I have two solutions for this:
Time O(nlogn) Space O(1) : Sort the number, traverse and keep track that a number appearing is appearing even or odd number of times. Sorting takes O(nlogn) while traversing is O(n).
Time O(N) Space O(#UniqueElementInArray)
Traverse the array XORing each element and inserting it in a hash table at the same time.
When we are done with the first traverse we will have XOR of all element in the array.
Now since XORing a number with itself is 0 we would be left with XOR of all the numbers that appeared odd number of times.
Now XOR this variable with all the keys present in the hash table, since hash table stored all the unique values it will nullify all the integers in XOR variable and would also insert XOR of any integer which is not present in initial XOR(Even integers).
After all this we would be left will XOR of all the integers having even occurrence, and since we only have one number with even occurrence we would have that number in XOR.
Example: int[] a = { 1, 1, 1, 2, 4, 4 };
xorVariable = 1^1^1^2^4^4 = (1^2);
xorVariable = xorVariable^1^2^4 ( from the hash table)
= 1^2^1^2^4 = 4.
A O( n ) Time and O ( 1 ) space solution. Uses xor. Assumption +ve numbers only. Not tested for negative numbers.
int findEven(int* a, int n)
{
if (!a) return -1;
int xor = a[0];
for (int i = 1; i < n; i++)
{
xor ^= a[i];
}
for (int i = 0; i < n; i++)
{
if (a[i] & xor)
continue;
else
return i;
}
return -1;
}
Algo :
Iterate through the array, finding the xor. This xor will be the combined xor of all the values that occur odd number of times. suppose values a and b occur odd number of times. xoring through the array will be xor of a and b. so this xor will hold some bits that are set in a, and some that are set in b. This is assuming a != b
Iterating again, xor added with the current element, would always be true ( non-zero ) for the elements repeating odd times. Thus, if the anding gives you a 0 based value, its the value you were searching for. If there are multiple elements that repeat even times, use a vector, and instead of return i, just add i to the vector.
Test cases it worked for:
{ 1, 1, -2, 2, 1, 1}
{ 1, -1, -1, 1, 1 }
{ INT_MIN }
{ INT_MAX, INT_MAX }
{ INT_MIN, INT_MIN, INT_MIN, INT_MAX }
Tested for -ve numbers, and it WORKS!
Make all of the odd occurrences even and all of the even occurrences odd by ignoring the first occurrence of each unique number. XOR all of the remaining numbers together. The remaining XOR value is the even number. O(n) time O(n) space.
Like this:
private static int findEven(final int[] array) {
final HashSet<Integer> set = new HashSet<>();
int output = 0;
for(final int value: array) {
if (set.contains(value)) {
output ^= value;
} else {
set.add(value);
}
}
return output;
}
This would work if you could additionally have the XOR of all the unique numbers in a list. Lemma. A way to XOR all unique numbers, not doing any of them twice in O(n) time, O(n) space. Then XOR the result from above with the result of XORing all the unique numbers that exist in the array will give the even value.
If you can solve that unique numbers lemma, then you can just avoid XORing the first occurrence and then the result would work.
Here is a O(n) time and O(1) space solution. It requires 256 MB of constant memory on my machine though :)). What it does is to represent all possible numbers (expressible with an int) in two arrays (bit arrays to be exact). Where one is to keep if a number does exist and one is to keep if the number is even or odd. After passing through the list and setting these arrays accordingly, it analyzes these two arrays to find out numbers that exists and even.
The reason to keep an array to determine whether a number exists is simply because every number that doesn't exist in the list occurs 0 times which is even. I don't think who asks this question wants us to print millions of numbers therefore to rule out that condition we should utilise it.
While it may seem like cheating since we are using a huge array and say “that is constant size and i can do whatever i want as long as it is constant”, i don’t think this is an invalid answer. In fact i think it is perfectly feasible and maybe your only option if you have TBs, PBs of data to process. Isn’t that why we do asymptotic analysis in the first place. What you have to do is to feed data as 4GB chunks to process function (since it takes an unsigned int as size parameter).
- Ugur Zongur August 27, 2014