Get Average Standing - rFronteddu/general_wiki GitHub Wiki

As an aspiring developer, you are required to develop a result analysis service for a car game.

There are n even records of d players who participated in different events in form of [race id, player's id, player's time]. For some race id, a player's ranking id decided based on the increasing order of their finish time. If two players have the same finish time, the one with a lower id is ranked lower.

The average standing of any player is the average of their various positions in all the races they competed in, expressed in the form of a fraction p/q. If there are multiple possible such fractions, reduce them such that p is the minimum possible.

Return a 2-dimensional array where each element i contains the ith player's p and q as described above. If the player did not compete in any races, the player's p and q values are both -1.

Complete the function getAverageStanding which has the following parameters:

  • int d: the number of players
  • int records[n][3]: each record[i] contains [race id, player id, player time]

Strategy

  1. Group records by race id in a map races, where the key is the raceID and the value is a list of [playerID, result]
  2. Process races to determine player ranks storing ranking in a map playersRanks
    • sort participant list in order of time and id (tie-breaker
    • assign rank based on order, add this rank to list of player ranks in playersRanks
  3. Calculate resultsint[d][2], each row is a player, for each, check if there is a result,
    • if there is sum all ranks, do gcd (rankSum, racesCount), p = rankSum / gcd, q = racesCount / mcd
    • else p = -1, q = -1

To get the gcd, if b == 0 return a, otherwise return gcd(b, a%b)

import java.util.*;

public class RaceAnalysis {
    // Helper method to calculate the GCD (Greatest Common Divisor)
    private static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static int[][] getAverageStanding(int d, int[][] records) {
        // Step 1: Organize records by race id
        Map<Integer, List<int[]>> races = new HashMap<>();
        for (int[] record : records) {
            races.computeIfAbsent(record[0], k -> new ArrayList<>())
                .add(new int[]{record[1], record[2]});
        }
       
        // Step 2: Process races to determine player ranks storing ranking in a map
        Map<Integer, List<Integer>> playerRanks = new HashMap<>();
        for (List<int[]> participants : races.values()) {
            // Sort participants first by time, then by player id (to break ties)
            participants.sort((a, b) -> {
                if (a[1] != b[1]) {
                    // Sort by time
                    return Integer.compare(a[1], b[1]); 
                } else {
                    // Sort by player id (tie-breaker)
                    return Integer.compare(a[0], b[0]);
                }
            });
            
            // Assign ranks based on the sorted order
            for (int rank = 1; rank <= participants.size(); rank++) {
                int playerId = participants.get(rank - 1)[0];
                playerRanks.computeIfAbsent(playerId, 
                    k -> new ArrayList<>()).add(rank);
            }
        }
        
        // Step 3: Calculate the average standing for each player
        int[][] result = new int[d][2];
        for (int playerId = 0; playerId < d; playerId++) {
            if (playerRanks.containsKey(playerId)) {
                List<Integer> ranks = playerRanks.get(playerId);
                int totalRaces = ranks.size();
                int totalRank = 0;
                
                // Sum up all the ranks for the player
                for (int rank : ranks) {
                    totalRank += rank;
                }
                
                // Get the average rank as a fraction
                int p = totalRank;
                int q = totalRaces;
                
                // Reduce the fraction p/q
                int commonGcd = gcd(p, q);
                p /= commonGcd;
                q /= commonGcd;
                
                result[playerId][0] = p;
                result[playerId][1] = q;
            } else {
                // Player didn't participate in any races
                result[playerId][0] = -1;
                result[playerId][1] = -1;
            }
        }
        
        return result;
    }
}
⚠️ **GitHub.com Fallback** ⚠️