4
\$\begingroup\$

I completed an algorithm problem just as a personal study, and I can't help but feel like my solution is a bit needlessly complicated, although I can't figure out a better way to do it. Here's the problem :

Given a number N, and a list of users currently on a stage, find out the failure rate of each stage up to N, and list the stages in descending order of failure rate. The failure rate is the percentage of users currently stuck on a stage, out of all the users who are currently playing the current stage or higher.

Example : stages = [2, 1, 2, 6, 2, 4, 3, 3], N = 5

  • There is 1 user currently playing stage 1, therefore out of the list of 8 users playing stage 1 or higher the failure rate of stage 1 is 1/8.
  • There are 3 users currently playing stage 2, therefore out of 7 users playing stage 2 or higher the failure rate is 3/7.
  • There are 2 users currently playing stage 3, therefore out of 4 users playing stage 3 or higher the failure rate is 2/4.
  • There is 1 user currently playing stage 4, therefore out of 2 users playing stage 4 or higher the failure rate is 1/2.
  • There are 0 users currently playing stage 5, therefore out of 1 users playing stage 5 or higher the failure rate is 0/1.

Therefore the result is : [3, 4, 2, 1, 5]

My solution :

public class StageFailureRate {
    private ArrayList<Integer> result;

    public StageFailureRate(int N, Integer[] stages) {
        result = new ArrayList<>();
        Map<Integer, Integer> usersOnStage = new HashMap<>();

        //count how many users are on each stage
        for (int stage : stages) {
            if (!usersOnStage.containsKey(stage)) {
                usersOnStage.put(stage, 1);
            } else {
                usersOnStage.put(stage, usersOnStage.get(stage) + 1);
            }
        }

        //compute the failure rate for each stage, up to N stages
        int total = stages.length;
        Map<Integer, Float> failureRates = new HashMap<Integer, Float>();
        float failureRate = 0;
        for (int i = 1; i <= N; ++i) {
            if (usersOnStage.containsKey(i)) {
                failureRate = (float) usersOnStage.get(i) / (float) total;
                total = total - usersOnStage.get(i);
            } else {
                failureRate = 0 / total;
            }
            failureRates.put(i, failureRate);
        }

        //Sort into descending order and get the result.
        Map<Integer, Float> sortedMap = sortByValue(failureRates);

        for (Map.Entry<Integer, Float> entry : sortedMap.entrySet()) {
            result.add(entry.getKey());
        }
    }

    public ArrayList<Integer> getResult() {
        return result;
    }

    private static Map<Integer, Float> sortByValue(Map<Integer, Float> unsortedMap) {
        List<Map.Entry<Integer, Float>> list =
                new LinkedList<Map.Entry<Integer, Float>>(unsortedMap.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<Integer, Float>>() {
            public int compare(Map.Entry<Integer, Float> o1,
                               Map.Entry<Integer, Float> o2) {
                return (o2.getValue()).compareTo(o1.getValue());
            }
        });

        Map<Integer, Float> sortedMap = new LinkedHashMap<Integer, Float>();
        for (Map.Entry<Integer, Float> entry : list) {
            sortedMap.put(entry.getKey(), entry.getValue());
       }
        return sortedMap;
    }
}

This solution is correct. Do you think it's the most optimal solution or could this be optimized to be much faster?

\$\endgroup\$
  • \$\begingroup\$ Did you try to sort stages and see what happen? \$\endgroup\$ – vnp Aug 26 at 6:08
2
\$\begingroup\$
  1. you should define float failureRate = 0; inside the for (int i = 1; i <= N; ++i) loop, because you are not using it outside the loop. See this for more info.

  2. When you calculate failureRate, just cast one of usersOnStage.get(i) or total to float. You don't need to cast both.

  3. else {failureRate = 0 / total;} is redundant because you'll always set failureRate to 0, which is its default value.

As for optimization to make it faster, since this piece of code is likely to be used in a video game, stages should be a small list, where efficiency of the algorithm doesn't matter much. You'd probably want to use simpler data structures, for a smaller overhead.

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

I made some modifies to your code focusing on simplify the code you posted starting from the signature of the constructor public StageFailureRate(int N, Integer[] stages), better to use public StageFailureRate(int N, int[] stages) because in the body of the constructor you never use the ArrayList methods. Instead of

for (int stage : stages) {
    if (!usersOnStage.containsKey(stage)) {
        usersOnStage.put(stage, 1);
    } else {
        usersOnStage.put(stage, usersOnStage.get(stage) + 1);
           }
}

You can omit the if else and write:

for (int stage : stages) {
   int count = usersOnStage.containsKey(stage) ? usersOnStage.get(stage) : 0;
   usersOnStage.put(stage, count + 1);
}

You can convert total = stages.length to float and rewrite the calculus cycle in this way:

float total = stages.length;
Map<Integer, Float> failureRates = new HashMap<Integer, Float>();

for (int i = 1; i <= N; ++i) {
    float failureRate = 0;
    if (usersOnStage.containsKey(i)) {
        failureRate = usersOnStage.get(i) / total;
        total -= usersOnStage.get(i);
    } 
    failureRates.put(i, failureRate);
}

The method sortByValues can be simplified using java streams and you can write it in this way:

private Map<Integer, Float> sortByValue(Map<Integer, Float> map) {
        Map<Integer, Float> reverseSortedMap = new LinkedHashMap<>();
        map 
        .entrySet()
        .stream()
        .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())) 
        .forEachOrdered(x -> reverseSortedMap.put(x.getKey(), x.getValue()));
        return reverseSortedMap;
}

Now you can rewrite the end of your constructor:

Map<Integer, Float> sortedMap = sortByValue(failureRates);
Set<Integer> keys = sortedMap.keySet();
for (Integer key : keys) {
    result.add(key);
}

Above the code of the class modified:

StageFailureRate.java

package stackoverflow;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class StageFailureRate {
    private List<Integer> result;

    public StageFailureRate(int N, int[] stages) {
        result = new ArrayList<>();
        Map<Integer, Integer> usersOnStage = new HashMap<>();

        //count how many users are on each stage
        for (int stage : stages) {
            int count = usersOnStage.containsKey(stage) ? usersOnStage.get(stage) : 0;
            usersOnStage.put(stage, count + 1);
        }


        //compute the failure rate for each stage, up to N stages
        float total = stages.length;
        Map<Integer, Float> failureRates = new HashMap<Integer, Float>();

        for (int i = 1; i <= N; ++i) {
            float failureRate = 0;
            if (usersOnStage.containsKey(i)) {
                failureRate = usersOnStage.get(i) / total;
                total -= usersOnStage.get(i);
            } 
            failureRates.put(i, failureRate);
        }

        //Sort into descending order and get the result.
        Map<Integer, Float> sortedMap = sortByValue(failureRates);

        Set<Integer> keys = sortedMap.keySet();
        for (Integer key : keys) {
            result.add(key);
        }

    }

    private Map<Integer, Float> sortByValue(Map<Integer, Float> map) {
        Map<Integer, Float> reverseSortedMap = new LinkedHashMap<>();
        map 
        .entrySet()
        .stream()
        .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())) 
        .forEachOrdered(x -> reverseSortedMap.put(x.getKey(), x.getValue()));
        return reverseSortedMap;
    }

    public List<Integer> getResult() {
        return result;
    }


    public static void main(String[] args) {
        int[] stages = {2, 1, 2, 6, 2, 4, 3, 3};
        int N = 5;
        StageFailureRate rate = new StageFailureRate(N, stages);
        System.out.println(rate.getResult());
    }
}

I preferred not modify all the methods of your class , normally in the constructor is always preferred just to initialize fields of the class, computations like result are encapsulated in static methods or at least outside constructor.

\$\endgroup\$

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.