Description: The following has been taken from Scaler and goes something like this: problem/description You go to a party of people, and you have to find out the celebrity over there. N According to the problem, the definition of celebrity is -- celebrity is a person who is known to everyone in a party, but he does not know anyone over there. You will be given a square matrix with dimensions . The matrix represents the people in the party. If an element of row ii and column is set to , then the person knows the person. Please note that, here the will always be zero. M[][] N X N M[][] j true i^th j^th M[i][i] Rule: A celebrity is known to everyone, but he does not know anyone at the party. Input Format: You will be given a matrix , where the elements in the matrix represent whether a person is known to another person or not. If the person is known to another person then, , else it is equal to . M M[i][j] = true false Task: Your task is to find out about the celebrity at the party. Print the id of the celebrity, if present. If there is no celebrity at the party, then print -1. Example Example 1: Input:
N = 3 
M[][] = {{false true false}, 
         {false false false}, 
         {false true false}
        } 
Output: 1 Explanation: The person with id = 1 does not know anyone, hence there are all 0's marked in its row, whereas, all the other people know the person '1'. Please note, there is '1' marked at M[0][1] = M[2][1], M[0][1]=M[2][1]. Example 2: Input:
N = 2
M[][] ={{false true},
        {true false}
       }
Output:: -1 Explanation: Both of the person know each other in the party, so there is no celebrity in the party. Solution: Ok ok, honestly I got this problem on the interview. And I solved it only with a brute-force solution. Let’s discuss it. My main idea is to iterate over the array, and check does this person know anybody and does this person knows by other persons. And obviously if so it is a celebrity. For it we need iterate over array for (int i = 0; i < n; i++) and add 2 variables boolean knowsAnyone = false;
 boolean everyoneKnows = true; then we iterate over a row and check that this person knows anyone for (int j = 0; j < n; j++) {
   if (matrix[i][j]) {
      knowsAnyone = true;
      break;
   }
} In the next step, we should check that this person is known by anyone else for (int j = 0; j < n; j++) {
   if (i != j && !matrix[j][i]) {
      everyoneKnows = false;
      break;
   }
} And finally, if a person doesn’t know anyone and is known by others that is mean that we found a celebrity. for this solution is O(N*N), where N is the number of people at the party. Time Complexity for this solution is constant because we are not using any additional data structures. Space Complexity And interviewer wanted another solution without adding some hits. I was disappointed and didn’t improve my idea. Unfortunately, I didn’t pass the interview. But I found an elegant idea. This idea calls Elimination Technique. The main idea is to eliminate elements step by step. In the first step, we should put all people into a Stack. Stack<Integer> stack = new Stack<>();

for (int i = 0; i < n; i++) {
   stack.push(i);
} Then we should iterate over the stack and get pairs while (stack.size() > 1) {
   int first = stack.pop();
   int second = stack.pop();
} When we have a pair we can check does the first person knows the second one if (matrix[first][second]) {} And if the first knows the second, that means that the first cannot be the celebrity. Because the celebrity doesn’t know anybody. But the second one still can be a celebrity if (matrix[first][second]) {
   stack.push(second);
} else{
   stack.push(first);
} When we have zero elements in the stack → it means we do not have a celebrity. if (stack.empty()){
   return -1;
} Also if we have 1 element in the stack we should additionally check that everybody knows it and celebrity doesn’t know anyone for (int i = 0; i < n; i++) {
   if (i != celeb && (matrix[celeb][i] || !matrix[i][celeb])){
      return -1;
   }
} And and, that is it. It is so wise. I was shocked.  Hope you enjoyed this idea. Link to resource: https://www.scaler.com/topics/celebrity-problem/

The code in this story is for educational purposes. The readers are solely responsible for whatever they build with it.

Solving the Single Number and Climbing Stairs Coding Challenge

2021 - HackerNoon Contributor of the Year - INNOVATION

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

Find the Celebrity

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

2022 Noonies Nominee Sergei on Programming, Technology, and More

10 Ways To Effectively Sell Yourself During A Job Interview

10 Tips for Using Diagrams to Ace The System Design Interview

10 Technical Interview Tips

10 Questions for Aswin Ganesh, Noonie Nominee for Functional Programming

10 Proven Techniques to Improve Candidate Experience

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps