4
\$\begingroup\$

Yes, yet another challenge on CodeEval!

This one has the purpose of finding the major element of a sequence: the element which appears in a sequence of size L more than L/2 times. I have this:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main (String[] args) throws IOException {
        File file = new File(args[0]);
        BufferedReader buffer = new BufferedReader(new FileReader(file));
        String line;
        String[] numbersRaw;
        int[] numbers;
        while ((line = buffer.readLine()) != null) {
            line = line.trim();
            numbersRaw = line.split(",");
            numbers = new int[numbersRaw.length];
            for(int i = 0; i < numbersRaw.length; i++){
                numbers[i] = Integer.valueOf(numbersRaw[i]);
            }
            System.out.println(mostFrequentElement(numbers));
        }
    }

    private static String mostFrequentElement(int[] arr) {
        Arrays.sort(arr);
        int counter = 0, big = -1, bigCounter = -1;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] == arr[i + 1]) {
                counter++;
            } 
            else {
                counter++;
                if (counter > bigCounter) {
                    big = arr[i];
                    bigCounter = counter;
                }                        
                counter = 0;
            }            
        }
        if(bigCounter > arr.length / 2) {
            return big + "";
        }
        return "None";
    }    
}

I have this solution, with appears to solve the challenge - however I think its performance is a bit sluggish (measured running time is about 1300 milliseconds). Is there any way to improve this?

\$\endgroup\$
4
\$\begingroup\$

Bug / unexpected result

Focusing only on mostFrequentElement() method

Assume passing the array {2,2,3,3,3} this will result in "None" but the correct result should be "3".

To get rid of this unwanted result, we need after the loop to increment the counter by 1 and add a check

counter++;
if (counter > bigCounter) {
    big = arr[arr.length - 1];
    bigCounter = counter;
}

Simplification

Because you are incrementing counter wether the if condition is true or false this can be simplified to

for (int i = 0; i < arr.length - 1; i++) {
    counter++;
    if (arr[i] != arr[i + 1]) {
        if (counter > bigCounter) {
            big = arr[i];
            bigCounter = counter;
        }                        
        counter = 0;
    }            
}

General

  • Instead of return big + ""; you should use the return String.valueOf(big); because it is more readable.

  • you should also check if the given array contains any element.

  • declaring multiple variables on one line removes readability.

  • you can initialize bigCounter with 0 because counter is always > 0.

  • big and bigCounter aren't good names. Better name them mostFrequentElement and mostFrequentElementCounter and rename the method to getMostFrequentElement.
    Using verbs or verb phrases for methodnames improves readability.

Refactoring

private static String getMostFrequentElement(int[] arr) {
    if (arr.length == 0) {
        return "None";
    }

    Arrays.sort(arr);

    int counter = 0;
    int mostFrequentElement = -1;
    int mostFrequentElementCounter = 0;

    for (int i = 0; i < arr.length - 1; i++) {
        counter++;
        if (arr[i] != arr[i + 1]) {
            if (counter > mostFrequentElementCounter) {
                mostFrequentElement = arr[i];
                mostFrequentElementCounter = counter;
            }
            counter = 0;
        }
    }

    counter++;
    if (counter > mostFrequentElementCounter) {
        mostFrequentElement = arr[arr.length - 1];
        mostFrequentElementCounter = counter;
    }

    if (mostFrequentElementCounter > arr.length / 2) {
        return String.valueOf(mostFrequentElement);
    }
    return "None";
}
\$\endgroup\$
1
  • \$\begingroup\$ I admit the variables were named as I was experimenting to see if the approach I was thinking on could work, so I never really gave their names much thought. And I had the idea that there were some issues with my code (the first time I tried it I got a "partially" solved state - with the same code, I tried it again and got the challenge "solved"), so thanks :) the performance improved, albeit not much - it's in the 1,2k milliseconds. But seeing the program messes with arrays and string manipulation, I guess its performance will not be great... \$\endgroup\$ Jan 14 '15 at 14:36
2
\$\begingroup\$

I tested locally, and casting array to int + sorting + finding major element took longer than finding major element in string array. Besides you could put check inside loop, than in some cases you don't have to go to the end of array.

public static Object getMostFrequentElementObject(Object[] objects) {
    HashMap<Object, CountNum> map = new HashMap<>();
    int L2 = objects.length / 2;
    for (Object o : objects) {
        CountNum count = map.get(o);
        if (count == null) {
            map.put(o, new CountNum());
        } else {
            ++count.i;
            if (count.i > L2)
                return o;
        }
    }
    return map;
}

...

class CountNum {
    public int i = 1;
}

also this command: line.split(","); takes 80% of all time for me.

\$\endgroup\$
1
\$\begingroup\$

The best way to improve performance is to use a better algorithm. A dominating element could be found in linear time and constant space (surprisingly, sorting an array only slows you down). Check out a classic Boyer-Moore solution.

\$\endgroup\$
2
  • \$\begingroup\$ The thing is: with that algorithm, how do you test if the dominating element occurs more than L/2 times? \$\endgroup\$ Jan 15 '15 at 7:26
  • \$\begingroup\$ Impossible. The existence of a dominating element is a prerequisite. \$\endgroup\$
    – vnp
    Jan 15 '15 at 7:38

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.