Problem
I am doing an interview exercise problem from here.
The problem is to find “all numbers that occurred an odd-number of times in an array”.
Here is my high level psuedo code thinking:
- Construct a map that will map integers to their frequencies.
- Iterate through the array, use the map to record the frequency count.
- Iterate through all the keys in the map and add the keys that have an odd value to another collection.
- Convert that collection to an array and return it to the user.
Here is the my implementation of this high level psuedo code in Java:
public static int[] allOdd(int[] array) {
Map<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int c=0;c<array.length;c++) {
if(hm.containsKey(array[c])) {
hm.put(array[c], hm.get(array[c]) + 1);
} else {
hm.put(array[c], 1);
}
}
List<Integer> allOdds = new ArrayList<Integer>();
for(int key: hm.keySet()) {
if(hm.get(key) % 2 == 1) {
allOdds.add(key);
}
}
int[] allOs = new int[allOdds.size()];
for(int c=0;c<allOdds.size();c ++){
allOs[c] = allOdds.get(c);
}
return allOs;
}
I tested this for two of my test cases and in both test cases ( {2,3,2,4,4,4,6,8,8} and {90,91,91,93,93,93,95,98,98,97} ), this function produced the right results([3, 4, 6] and [97, 93, 95, 90] respectively).
Is there anything I can do to improve the time and space complexity of this method. One of the worries I had was that I created too many collections (too much space) But to me each collection had its own purpose. The map was to map values to frequencies. The ArrayList was a dynamic structure to hold the odd occurrences. You needed to initialize the last array because ArrayList is a collection that holds objects so you need to manually iterate through the ArrayList and store those ints (Auto box) in the new array. To Array
Is there anything you can point out that can improve time and space efficiency in this function?
Solution
You don’t really need to keep track of how many times you’ve seen each integer, only whether you’ve seen it an odd number of times. So start with your data structure (map, hash table, dictionary, whatever) being empty, which correctly reflects the state that you have seen no numbers an odd number of times. Now for each number x in the array, if x is in the map then remove it (now you’ve seen it an even number of times) otherwise add it.
@vnp had a good point to sort the array first,
@t.niese to forego the counting and keep flipping a boolean flag instead,
and also @WilfRosenbaum to use the property of the counting data structure that elements are either in or out already mean odd or even, respectively.
In addition, @rolfl showed in an answer to a practically duplicate question a technique to collect the odd numbers in-place.
Combining some of these points, and adding to them a bit, here’s an alternative implementation:
public static int[] allOdd(int[] array) {
if (array.length < 2) {
return array;
}
int[] sorted = array.clone();
Arrays.sort(sorted);
boolean odd = true;
int len = 0;
for (int i = 1; i < sorted.length; ++i) {
if (sorted[i] == sorted[i - 1]) {
odd = !odd;
} else {
if (odd) {
sorted[len++] = sorted[i - 1];
}
odd = true;
}
}
if (odd) {
sorted[len++] = sorted[sorted.length - 1];
}
return Arrays.copyOf(sorted, len);
}
This implementation works on a copy of the original array.
If you don’t mind mutating the input parameter,
then you could save the space of the sorted array.
Unit testing
To verify that your solution works,
especially while tweaking it,
it’s good to have some unit tests,
based on the given examples,
and also carefully covering corner cases too:
private void assertEqualSet(int[] expected, int[] actual) {
assertEquals(arrayToSet(expected), arrayToSet(actual));
}
private Set<Integer> arrayToSet(int[] arr) {
Set<Integer> set = new HashSet<>();
for (int num : arr) {
set.add(num);
}
return set;
}
@Test
public void test_empty() {
assertEqualSet(new int[0], allOdd(new int[0]));
}
@Test
public void test_1() {
assertEqualSet(new int[]{1}, allOdd(new int[]{1}));
}
@Test
public void test_1_2() {
assertEqualSet(new int[]{1, 2}, allOdd(new int[]{1, 2}));
}
@Test
public void test_1_1() {
assertEqualSet(new int[0], allOdd(new int[]{1, 1}));
}
@Test
public void test_1_2_1() {
assertEqualSet(new int[]{2}, allOdd(new int[]{1, 2, 1}));
}
@Test
public void test_2_3_2_4_4_4_6_8_8() {
assertEqualSet(new int[]{3, 4, 6}, allOdd(new int[]{2, 3, 2, 4, 4, 4, 6, 8, 8}));
}
@Test
public void test_90_91_91_93_93_93_95_98_98_97() {
assertEqualSet(new int[]{97, 93, 95, 90}, allOdd(new int[]{90, 91, 91, 93, 93, 93, 95, 98, 98, 97}));
}
Code review
A few other things can be improved about your implementation.
When you don’t need the element indexes when iterating over an array,
use a for-each loop. So instead of:
for(int c=0;c<array.length;c++) {
// ...
}
This is better:
for (int num : array) {
// ...
}
This code performs a hash lookup twice: once in containsKey, and then in get:
if (hm.containsKey(num)) {
hm.put(num, hm.get(num) + 1);
} else {
hm.put(num, 1);
}
You could factor out one lookup by using a get and a null-check.
The code is also shorter this way, with less duplicated elements:
Integer count = hm.get(num);
if (count == null) {
count = 0;
}
hm.put(num, count + 1);
I am not a Java expert. I just know that map may degenerate in a linear list giving a worst case performance of O(n2). Facing question like this I’d first (heap- or merge-) sort the array, and then scan it counting repetitions. O(nlogn) time is pretty much guaranteed, with no space penalty.
import java.util.HashSet;
public class OddOccurence {
public static void main(String[] args) {
int[] a = {1,1,1,2,2,3,3,4,4,4,5,6,6,6,6,7,7,8,8,8,3,8,8};
int i=0;
int j=0;
HashSet<String> result = new HashSet<String>();
System.out.println(a[i] );
for( i = 0 ; i<a.length; i++){
int counter = 0;
for( j = 0; j<a.length; j++){
if(a[i]==a[j])
counter++;
}
if(counter%2 != 0)
result.add(Integer.toString(a[i]));
}
System.out.println(result);
}
}