@@ -0,0 +1,2791 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0A/**%0A * Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The%0A * definition of a celebrity is that all the other n - 1 people know him/her but he/she does not know any of them.%0A * %3Cp%3E%0A * Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do%0A * is to ask questions like: %22Hi, A. Do you know B?%22 to get information of whether A knows B. You need to find out the%0A * celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).%0A * %3Cp%3E%0A * You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int%0A * findCelebrity(n), your function should minimize the number of calls to knows.%0A * %3Cp%3E%0A * Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a%0A * celebrity in the party. If there is no celebrity, return -1.%0A * %3Cp%3E%0A * Company Tags: LinkedIn, Facebook%0A * Tags: Array%0A */%0Apublic class FindTheCelebrity %7B%0A%0A    /*%0A     * The knows API is defined in the parent class Relation.%0A     * boolean knows(int a, int b);%0A     */%0A    public class Solution extends Relation %7B%0A%0A        /**%0A         * Pick the candidate first.%0A         * If a candidate doesn't know someone, that guy cannot be candidate, candidate remains the same.%0A         * If a candidate knows someone, he cannot be candidate anymore, the one he knows is the next candidate.%0A         * After that we need to validate the candidate, since no guarantee for a celebrity.%0A         * For the people before candidate, they cannot be candidate anymore.%0A         * So check if candidate knows any of them. If yes, return -1.%0A         * For the people after, candidate doesn't know them.%0A         * So check if any of them doesn't know candidate. If not, return -1.%0A         * If the candidate passes this two checks, he is the celebrity everyone knows but doesn't know anyone.%0A         */%0A        public int findCelebrity(int n) %7B%0A            int candidate = 0;%0A            for (int i = 1; i %3C n; i++) %7B%0A                if (knows(candidate, i)) %7B%0A                    candidate = i;%0A                %7D%0A            %7D%0A            for (int i = 0; i %3C candidate; i++) %7B%0A                if (knows(candidate, i)) %7B%0A                    return -1;%0A                %7D%0A            %7D%0A            for (int i = candidate + 1; i %3C n; i++) %7B%0A                if (!knows(i, candidate)) %7B%0A                    return -1;%0A                %7D%0A            %7D%0A            return candidate;%0A        %7D%0A    %7D%0A%0A    /**%0A     * Dummy.%0A     */%0A    private class Relation %7B%0A%0A        boolean knows(int a, int b) %7B%0A            return false;%0A        %7D%0A    %7D%0A%0A%7D%0A

add find the celebrity