Celebrity is the person to whom everyone know but he do not know any person. This problem one of the programing problem that asked in companies

Problem Statement:

You are going to a party of N people and your task is to find a celebrity in the party. Means Celebrity is know by N-1 person in the party of N people.

Solution:

A Square matrix is used to represent the people in the party → if an element of row i and column j is set to 1 it means i-th person knows j else 0.

Input:
MATRIX = { {0, 0, 1, 0},
           {0, 0, 1, 0},
           {0, 0, 0, 0},
           {0, 0, 1, 0} }
Output: id = 2
Explanation: The person with ID 2 does not know anyone but everyone knows him

Input:
MATRIX = { {0, 0, 1, 0},
           {0, 0, 1, 0},
           {0, 1, 0, 0},
           {0, 0, 1, 0} }
Output: No celebrity 
Explanation: There is no celebrity.

There are two ways to solve this problem

1. Using Stack
2. Using Graph

Using Stack

• If A knows B, then A can’t be a celebrity. Discard A, and B may be celebrity.
• If A doesn’t know B, then B can’t be a celebrity. Discard B, and A may be celebrity.
• Repeat above two steps till there is only one person.
• Ensure the remained person is a celebrity.

Algorithm

1. Create a stack and push all the id’s in the stack.
2. Run a loop while there are more than 1 element in the stack.
3. Pop top two element from the stack (represent them as A and B)
4. If A knows B, then A can’t be a celebrity and push B in stack. Else if A doesn’t know B, then B can’t be a celebrity push A in stack.
5. Assign the remaining element in the stack as the celebrity.
6. Run a loop from 0 to n-1 and find the count of persons who knows the celebrity and the number of people whom the celebrity knows. if the count of persons who knows the celebrity is n-1 and the count of people whom the celebrity knows is 0 then return the id of celebrity else return -1.

Code

MATRIX = [[0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]]

def a_knows_b(a, b):
    return MATRIX[a][b]

def find_celebrity_stack(guestCount):
    # create a empty array which act as stack
    stack = []
    # push all guest in the stack (means all ids i.e 0 to guest count)
    for i in range(guestCount):
        stack.append(i)

    while len(stack) > 1:
        # now pick top two guest from stack
        guestA = stack.pop()
        guestB = stack.pop()
        # check guestA knows guestB
        # if guestA knows guestB then push back guestB into stack else push guestA
        if a_knows_b(guestA, guestB):
            stack.append(guestB)
        else:
            stack.append(guestA)

    if not len(MATRIX):
        return -1
    celebrity = stack.pop()

    # Now verify that last person in the stack is celebrity or not
    for i in range(guestCount):
        if i != celebrity and (a_knows_b(celebrity, i) or not a_knows_b(i, celebrity)):
            return -1

    return celebrity


print(find_celebrity_stack(len(MATRIX)))

Using Graph

Initialize indegree and outdegree of every vertex as 0. If A knows B, draw a directed edge from A to B, increase indegree of B and outdegree of A by 1.  If a celebrity is present in the party, there will be one sink node in the graph with outdegree of zero and indegree of N-1. 

Algorithm

1. Create two arrays indegree and outdegree, to store the indegree and outdegree
2. Run a nested loop, the outer loop from 0 to n and inner loop from 0 to n.
3. For every pair i, j check if i knows j then increase the outdegree of i and indegree of j
4. For every pair i, j check if j knows i then increase the outdegree of j and indegree of i
5. Run a loop from 0 to n and find the id where the indegree is n-1 and outdegree is 0

Code

MATRIX = [[0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]]


def a_knows_b(a, b):
    return MATRIX[a][b]

def find_celebrity_graph(guestCount):
    # create two array for input and outpu of guests with initial value 0
    inputA = [0 for x in range(guestCount)]  # [0] * guestCount
    outputA = [0 for x in range(guestCount)]
    for i in range(guestCount):
        for j in range(guestCount):
            if a_knows_b(i, j):
                # if "a" knows "b" then value for "a" increement by 1 in inputA array
                # if "b" knows "a" then value for "a" increment by 1 in outputB array
                outputA[i] = outputA[i] + 1
                inputA[j] = inputA[j] + 1
    try:
        # if any index of inputA has value "guestCount - 1" then we will get index of that value
        # if at that index in outpuA array value should be "0" to qualify index as celebrity
        if inputA.count(guestCount - 1) == 1:
            # if (guestCount - 1) is more than 1 then there is no celebrity
            celebrity = inputA.index(guestCount - 1)
            if not outputA[celebrity]:
                return celebrity
        else:
            return -1
    except Exception as e:
        return -1


print(find_celebrity_graph(len(MATRIX)))

Final Code

Celebrity Problem Code