Find the Celebrity

public class CelebrityFinder extends Relation {
    
    private int totalPeople;
    private Map<Pair<Integer, Integer>, Boolean> relationshipCache = new HashMap<>(); 
    
    @Override
    public boolean knows(int person1, int person2) {
        Pair<Integer, Integer> pair = new Pair<>(person1, person2);
        if (!relationshipCache.containsKey(pair)) {
            relationshipCache.put(pair, super.knows(person1, person2));
        }
        return relationshipCache.get(pair);
    }
    
    public int findCelebrity(int count) {
        totalPeople = count;
        int possibleCelebrity = 0;
        for (int i = 0; i < count; i++) {
            if (knows(possibleCelebrity, i)) {
                possibleCelebrity = i;
            }
        }
        if (checkCelebrity(possibleCelebrity)) {
            return possibleCelebrity;
        }
        return -1;
    }
    
    private boolean checkCelebrity(int candidate) {
        for (int j = 0; j < totalPeople; j++) {
            if (candidate == j) continue; // Skip self checks.
            if (knows(candidate, j) || !knows(j, candidate)) {
                return false;
            }
        }
        return true;
    }
}

The Java program provided implements a CelebrityFinder class which extends the Relation class to determine if there is a "celebrity" among a group of people. The celebrity is a person known by everyone else but who knows no one else. The implementation uses caching to optimize the check for whether one person knows another.

• Class Explanation:

  • The CelebrityFinder class has a totalPeople attribute to store the number of people in the group.
  • A relationshipCache stores results of previous checks to determine if one person knows another, minimizing redundant operations.

• Method Details:

  • The knows method overrides a method in the Relation class that checks if person1 knows person2. This method implements caching to avoid repetitive checks, thus improving performance.
  • The findCelebrity method iterates through all people using a two-pass algorithm:
    1. Identify a potential celebrity by assuming the first person (index 0) as the celebrity and moving to the next person if the assumed celebrity knows the current person.
    2. Verify the potential celebrity to confirm if everyone knows them and they know no one except themselves.
  • The checkCelebrity method checks if the candidate does not know any other person except themselves and all the other people know the candidate.

• Return Values:

  • If a celebrity is found, findCelebrity returns the index of the celebrity.
  • If there is no celebrity, it returns -1.

The approach ensures efficient determination of the celebrity using cache for known relations and minimizing the number of checks needed by adopting an optimal strategy for celebrity identification. The caching mechanism particularly helps in larger groups where multiple calls might otherwise be made to the knows method for the same pair of individuals.

function memoize(functionToMemoize) {
    const memo = new Map();
    return function(...parameters) {
        const key = parameters.join(', ');
        if (!memo.has(key)) {
            const result = functionToMemoize(...parameters);
            memo.set(key, result);
        }

        return memo.get(key);
    }
}

function solution(knowledge) {
    knowledge = memoize(knowledge);

    function checkCelebrity(index, total) {
        for (let other = 0; other < total; other++) {
            if (index === other) continue;
            if (knowledge(index, other) || !knowledge(other, index)) {
                return false;
            }
        }
        return true;
    }

    return function identifyCelebrity(count) {
        let potentialCeleb = 0;
        for (let idx = 0; idx < count; idx++) {
            if (knowledge(potentialCeleb, idx)) {
                potentialCeleb = idx;
            }
        }
        if (checkCelebrity(potentialCeleb, count)) {
            return potentialCeleb;
        }
        return -1;
    }
}

The "Find the Celebrity" problem entails identifying a celebrity among a group of people based on their knowledge of each other. The solution involves using JavaScript to create an efficient mechanism for determining if a celebrity exists and, if so, identifying who it is. Here is a breakdown of how the solution is structured and implemented:

• Memoize Function:

  • The solution begins by creating a memoize function that caches the results of checks between two individuals to speed up the process. This function is utilized to preserve results of pairwise checks to minimize redundant operations.
  • memoize is a higher-order function that takes another function as its argument (functionToMemoize) and returns a new function. This returned function, when called, checks if the result already exists for the given parameters in a Map. If not, it computes the result, stores it, and then returns the result.

• Solution Function:

  • The solution function takes the knowledge function as an argument. This knowledge function is assumed to return true if the first person knows the second person, and it is memoized.
  • Within solution, a nested function checkCelebrity is defined. It iterates through all individuals to verify whether a supposed celebrity really does not know anyone else, but everyone else knows them.
  • The identifyCelebrity function uses the logic to find if there is any celebrity among the group. It processes each individual, updating the potential celebrity based on their mutual knowledge.
  • If a potential celebrity is identified by the end of the iteration, it is validated using the checkCelebrity function.

• Celebrity Identification Process:

  • Start by assuming the first person as a potential celebrity.
  • Sequentially check with every other individual; if the assumed celebrity knows another person, update the potential celebrity to that person.
  • After processing, ensure the final candidate is validated. If they qualify based on the checks, return their index; if no celebrity is found, return -1.

This solution effectively minimizes the number of checks required by utilizing memoization and logical elimination of non-candidates. It efficiently identifies the celebrity with minimized complexity and increased speed, particularly useful for large groups.