I am working on the level 1 of the Google FooBar Minion scheduling challenge :

Write a function called solution(data, n) that takes in a list of less than 100 integers and a number n, and returns that same list but with all of the numbers that occur more than n times removed entirely.

The returned list should retain the same ordering as the original list - you don't want to mix up those carefully-planned shift rotations!

For instance, if data was [5, 10, 15, 10, 7] and n was 1, solution(data, n) would return the list [5, 15, 7] because 10 occurs twice, and thus was removed from the list entirely.

This is my solution, but for some reason only 2 testcases are passing out of 10.

The strange thing is, the open testcase {1, 2, 2, 3, 3, 3, 4, 5, 5}, n = 1 is also failing, while in my local IDE it passes.

public static int[] solution(int[] data, int n) {
    Map<Integer, Integer> map = new LinkedHashMap<>();
    
    if (data.length < 1) {
        return data;
    }
    
    if (n < 1) {
        return new int[0];
    }
    
    for (final int datum : data) {
        map.put(datum, map.getOrDefault(datum, 0)   1);
    }
    
    List<Integer> t = map.entrySet()
        .stream()
        .filter(x -> x.getValue() == 1)
        .map(Map.Entry::getKey)
        .toList();
    
    int[] b = new int[t.size()];
    
    for (int i = 0; i < t.size(); i  ) {
        b[i] = t.get(i);
    }
    
    return b;
}

Please, point out the issue with this code.

CodePudding user response：

The problem in your code lies in the filter operation, since you should keep only the elements lower or equal to n.

The whole logic of your algorithm is fine, apart from the bug in the filter operation, but you could simplify some of the code by employing a stream to create the Map with the occurrences for each number, it would probably look easier to read and more concise.

Then, with a second stream pipeline create a new List with only the numbers whose occurrences are below or equal to n. By the way, I preferred using the given array as the source of the stream instead of the Map because in the requirements of your problem is said that the order of the elements should not be changed, and since the map's keys can be retrieved with no particular order, I preferred to rely on the array rather than the Map.

Finally, return an array of int populated with the list's elements. If the returned type int[] is not a constraint, then you could return directly the List obtained from the stream.

public static int[] removeDuplicatesN(int[] nums, int n) {
    Map<Integer, Integer> mapOccurrences = Arrays.stream(nums)
            .boxed()
            .collect(Collectors.toMap(Function.identity(), i -> 1, (a, b) -> a   b));

    List<Integer> listRes = Arrays.stream(nums)
            .boxed()
            .filter(i -> mapOccurrences.get(i) <= n)
            .collect(Collectors.toList());

    int[] res = new int[listRes.size()];
    for (int i = 0; i < res.length; i  ) {
        res[i] = listRes.get(i);
    }

    return res;
}

Output

[5, 15, 7]

Here is a link to test the code:

https://www.jdoodle.com/iembed/v0/rSS

CodePudding user response：

returns that same list but with all of the numbers that occur more than n times removed entirely.

The returned list should retain the same ordering

According to the original problem statement, you need to discard only elements having the number of occurrences more than n, and nothing else.

There's no requirement that all elements in the resulting array should be distinct. It means you have to preserve all duplicated elements that will be encountered n or less than n times.

The approach of build building a histogram of frequencies (counting the number of occurrences) is correct, but you don't need LinkedHashMap.

This logic can be written like that using Java 8 method merge():

public static Map<Integer, Integer> countFrequencies(int[] arr) {
    Map<Integer, Integer> frequencies = new HashMap<>();
    for (int next: arr) {
        frequencies.merge(next, 1, Integer::sum);
    }
    return frequencies;
}

Or with Stream API:

public static Map<Integer, Long> countFrequencies(int[] arr) {
    
    return Arrays.stream(arr)
        .boxed()
        .collect(Collectors.groupingBy(
            Function.identity(),
            Collectors.counting()));
}

To ensure the order, you just need to iterate over the given array, and filter out the element having frequency less or equal to n.

Also, there's no need to create an intermediate list, you can get the resulting array as a result of execution of the stream pipeline.

public static int[] solution(int[] data, int n) {
    
    Map<Integer, Long> frequencies = countFrequencies(data);
    
    return Arrays.stream(data)
        .filter(num -> frequencies.get(num) <= n)
        .toArray();
}

See the Online Demo

Also make sure that you have all the imports at the top of the file you're submitting (imports for the code given above are listed in the demo).

And don't use import java.util.*, because of that your solution might not pass the tests.