0
\$\begingroup\$

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:

  1. Construct a map that will map integers to their frequencies.
  2. Iterate through the array, use the map to record the frequency count.
  3. Iterate through all the keys in the map and add the keys that have an odd value to another collection.
  4. 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?

\$\endgroup\$
  • \$\begingroup\$ You don't need to count the frequency. One bit would be sufficient. 0 even, 1 odd and flipping that bit for each occurence. \$\endgroup\$ – t.niese Feb 20 '15 at 6:10
  • \$\begingroup\$ Take a look at Find elements occurring even number of times in an integer array. \$\endgroup\$ – 200_success Feb 20 '15 at 7:00
  • \$\begingroup\$ @200_success in your solution, why did you need 2 sets? Why not just have 1 and then remove back and forth? Like if you have 1 1 1. It be a sequence of add 1 remove 1 add 1 and you end up with what you want. \$\endgroup\$ – committedandroider Feb 20 '15 at 7:49
  • \$\begingroup\$ The even-occurrences problem is harder than the odd-occurrences problem. \$\endgroup\$ – 200_success Feb 20 '15 at 8:24
  • \$\begingroup\$ @200_success So all you would need here is that one set? \$\endgroup\$ – committedandroider Feb 20 '15 at 8:26
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ And then you just return the keyset? \$\endgroup\$ – committedandroider Feb 20 '15 at 7:38
  • \$\begingroup\$ Yeah. It always contains exactly the integers you've seen an odd number of times. \$\endgroup\$ – Wilf Rosenbaum Feb 20 '15 at 7:41
  • \$\begingroup\$ Yeah cause the question never states you have to return an int array so why go through the trouble of "autoboxing" the set of Integers into an array of ints? \$\endgroup\$ – committedandroider Feb 20 '15 at 7:42
  • \$\begingroup\$ So all you would need is a set then? \$\endgroup\$ – committedandroider Feb 20 '15 at 7:47
  • \$\begingroup\$ Yeah, you could use a set or any other data structure that supports efficient insertion, deletion and querying. \$\endgroup\$ – Wilf Rosenbaum Feb 20 '15 at 7:52
2
\$\begingroup\$

@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);
\$\endgroup\$
  • \$\begingroup\$ How do you know what the edge cases are? \$\endgroup\$ – committedandroider Feb 20 '15 at 7:51
  • \$\begingroup\$ You think hard, and ask yourself questions like: "what can possibly go wrong", "what input could break the function". Typical edge cases are small inputs, empty input, degenerate inputs (array of all the same values). Stuff like that. For the record, your implementation passes all the tests I could think of. My point was just a general tip about unit testing. \$\endgroup\$ – janos Feb 20 '15 at 7:59
  • \$\begingroup\$ Did you put the test code as part of the class code. In my JUnit test code, I had to always call ClassName.allOdd(...)? \$\endgroup\$ – committedandroider Feb 20 '15 at 8:03
  • \$\begingroup\$ Yes, JUnit tests should go to their own file. For the sake of simplicity I put them in the same class in my local version. It's a minor technical detail and not really relevant for this discussion. You can easily move these tests to a separate file and add a helper method there with the name allOdd that simply calls return ClassName.allOdd. \$\endgroup\$ – janos Feb 20 '15 at 8:09
  • \$\begingroup\$ In general software, is it up to you to decide how to return all the values with odd occurrences in an array? Like you're given an array. Do you usually have flexibility in choosing what kind of data structure to return those values back in - set, array, etc? \$\endgroup\$ – committedandroider Feb 20 '15 at 8:15
1
\$\begingroup\$

I am not a Java expert. I just know that map may degenerate in a linear list giving a worst case performance of \$O(n^2)\$. Facing question like this I'd first (heap- or merge-) sort the array, and then scan it counting repetitions. \$O(n \log{n})\$ time is pretty much guaranteed, with no space penalty.

\$\endgroup\$
  • \$\begingroup\$ What do you mean by degenerate? \$\endgroup\$ – committedandroider Feb 20 '15 at 7:38
  • \$\begingroup\$ Technical term: decline or deteriorate; in a pathological case perform much worse than expected in average. \$\endgroup\$ – vnp Feb 20 '15 at 7:45
  • \$\begingroup\$ MathJax indeed. \$ math \$ \$\endgroup\$ – vnp Feb 20 '15 at 7:57
  • \$\begingroup\$ Would using just one hashset resolve that issue of the worst case of O(\$n^2\$)? \$\endgroup\$ – committedandroider Feb 20 '15 at 8:05
  • \$\begingroup\$ I believe so. Such is a nature of a worst case - being worst. \$\endgroup\$ – vnp Feb 20 '15 at 8:16
-2
\$\begingroup\$

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);

}

}

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. \$\endgroup\$ – Toby Speight Mar 8 '18 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.