The Celebrity Problem | GeeksforGeeks
In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.
We have following observation based on elimination technique (Refer Polya’s How to Solve It book).
http://blog.csdn.net/fightforyourdream/article/details/17410993
public void solve() {
int[][] acquiantance = new int[][] { {0, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0}
};
System.out.println(howIsCelebrity(acquiantance, acquiantance.length));
}
public int howIsCelebrity(int[][] acquiantance, int n) {
Stack<Integer> s = new Stack<Integer>();
int id = 0;
while (id < n) {
s.push(id);
++id;
}
int a = s.pop();
int b = s.pop();
while (s.size() != 1) {
if (haveAcquiantance(acquiantance, a, b)) {
// a knows b and a is not the celebrity. Update a.
a = s.pop();
} else {
// a does not know b so b cannot be the celebrity. Update b
b = s.pop();
}
}
// With one element in stack, check if that is the celebrity.
int candidate = s.pop();
if (haveAcquiantance(acquiantance, candidate, a)) {
candidate = a;
}
if (haveAcquiantance(acquiantance, candidate, b)) {
candidate = b;
}
for (int i = 0; i < n; ++i) {
if (i == candidate) {
continue;
}
if (haveAcquiantance(acquiantance, candidate, i) || !haveAcquiantance(acquiantance, i, candidate)) {
return -1;
}
}
return candidate;
}
public boolean haveAcquiantance(int[][] acquiantance, int a, int b) {
return acquiantance[a][b] == 1;
}
对a做检测，如果a认识b || b不认识a，a就不会是celebrity
第一个循坏对can进行挑选，如果i不认识can，则说明can一定不是celebrity。如果i认识can，能说明i一定不是celebrity
http://www.zrzahid.com/find-influencer-or-celebrity/
https://lina.bitcron.com/post/code/2018-summer-fb-intern-mian-jing
Read full article from The Celebrity Problem | GeeksforGeeks
In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions.
We have following observation based on elimination technique (Refer Polya’s How to Solve It book).
- If A knows B, then A can’t be celebrity. Discard A, and B may be celebrity.
- If A doesn’t know B, then B can’t be celebrity. Discard B, and A may be celebrity.
- Repeat above two steps till we left with only one person.
- Ensure the remained person is celebrity. (Why do we need this step?)
- Push all the celebrities into a stack.
- Pop off top two persons from the stack, discard one person based on return status of HaveAcquaintance(A, B).
- Push the remained person onto stack.
- Repeat step 2 and 3 until only one person remains in the stack.
- Check the remained person in stack doesn’t have acquaintance with anyone else.
http://blog.csdn.net/fightforyourdream/article/details/17410993
我们把人编号，比如从1 到 N。
我们考虑最坏情况：你问每一个人是否认识 X ，如果大家都认识，那么 X 一定是名人，如果其中一个人说不认识，那么那个人一定不是名人。因为 X 的范围是 1 到 N， 所以，在最坏情况下，我们 要问 （N - 1）* N 个问题。
但是，有一种更好的方法。我们从1开始，依次问他是否认识他的下一个，比如 2， 如果 1 说认识，那么 1 一定不是名人，2 有可能是名人； 如果1 说不认识，2 一定不是名人，1 却有可能是名人。这是这个方法巧的地方。所以，不管1 回答是还是不是，我们都可以确定其中一个不是名人，然后，我们继续问 可能是名人那一位 是否认识 3， 然后依次下去，直到第 N 个人。这样我们就可以只要问 （N - 1） 个问题就可以把名人找出来。
https://github.com/monkeylyf/interviewjam/blob/master/graph/facebook_Celebrity_Problem.javapublic void solve() {
int[][] acquiantance = new int[][] { {0, 0, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0}
};
System.out.println(howIsCelebrity(acquiantance, acquiantance.length));
}
public int howIsCelebrity(int[][] acquiantance, int n) {
Stack<Integer> s = new Stack<Integer>();
int id = 0;
while (id < n) {
s.push(id);
++id;
}
int a = s.pop();
int b = s.pop();
while (s.size() != 1) {
if (haveAcquiantance(acquiantance, a, b)) {
// a knows b and a is not the celebrity. Update a.
a = s.pop();
} else {
// a does not know b so b cannot be the celebrity. Update b
b = s.pop();
}
}
// With one element in stack, check if that is the celebrity.
int candidate = s.pop();
if (haveAcquiantance(acquiantance, candidate, a)) {
candidate = a;
}
if (haveAcquiantance(acquiantance, candidate, b)) {
candidate = b;
}
for (int i = 0; i < n; ++i) {
if (i == candidate) {
continue;
}
if (haveAcquiantance(acquiantance, candidate, i) || !haveAcquiantance(acquiantance, i, candidate)) {
return -1;
}
}
return candidate;
}
public boolean haveAcquiantance(int[][] acquiantance, int a, int b) {
return acquiantance[a][b] == 1;
}
int CelebrityUsingStack(int size){ // Handle trivial case of size = 2 list<int> stack; // Careful about naming int i; int C; // Celebrity i = 0; while( i < size ) { stack.push_back(i); i = i + 1; } int A = stack.back(); stack.pop_back(); int B = stack.back(); stack.pop_back(); while( stack.size() != 1 ) { if( HaveAcquiantance(A, B) ) { A = stack.back(); stack.pop_back(); } else { B = stack.back(); stack.pop_back(); } } // Potential candidate? C = stack.back(); stack.pop_back(); // Last candidate was not examined, it leads one excess comparison (optimise) if( HaveAcquiantance(C, B) ) C = B; if( HaveAcquiantance(C, A) ) C = A; // I know these are redundant, // we can simply check i against C i = 0; while( i < size ) { if( C != i ) stack.push_back(i); i = i + 1; } while( !stack.empty() ) { i = stack.back(); stack.pop_back(); // C must not know i if( HaveAcquiantance(C, i) ) return -1; // i must know C if( !HaveAcquiantance(i, C) ) return -1; } return C;}
1. Write code to find celebrity. Don’t use any data structures like graphs, stack, etc… you have access to N and HaveAcquaintance(int, int) only.
2. Implement the algorithm using Queues. What is your observation? Compare your solution withFinding Maximum and Minimum in an array and Tournament Tree. What are minimum number of comparisons do we need (optimal number of calls to HaveAcquaintance())?
http://shibaili.blogspot.com/2015/09/day-129-277-find-celebrity.html对a做检测，如果a认识b || b不认识a，a就不会是celebrity
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| // Forward declaration of the knows API.bool knows(int a, int b);class Solution {public: int findCelebrity(int n) { for (int a = 0; a < n; a++) { int b = 0; for (; b < n; b++) { if (a == b) continue; if (knows(a,b) || !knows(b,a)) { break; } } if (b == n) return a; } return -1; }}; |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| // Forward declaration of the knows API.bool knows(int a, int b);class Solution {public: int findCelebrity(int n) { int can = 0; for (int i = 1; i < n; i++) { if (!knows(i,can)) { can = i; } } for (int i = 0; i < n; i++) { if (i == can) continue; if (!knows(i,can) || knows(can,i)) return -1; } return can; }}; |
A celebrity/influencer is a person who doesn’t know anybody but is known to or followed by everybody. Given N peoples and a matrix for known or following information then find the celebrity or influencer among the group of N peoples.
Formally speaking, Given a matrix of following between N users (with ids from 0 to N-1):
* following[i][j] == true iff user i is following user j
* thus following[i][j] doesn’t imply following[j][i].
* Let’s also agree that followingMatrix[i][i] == false
*
* Influencer is a user who is:
* – followed by everyone else and
* – not following anyone himself
*
* Find an Influencer by a given matrix of following,
* or return -1 if there is no Influencer in this group.
* following[i][j] == true iff user i is following user j
* thus following[i][j] doesn’t imply following[j][i].
* Let’s also agree that followingMatrix[i][i] == false
*
* Influencer is a user who is:
* – followed by everyone else and
* – not following anyone himself
*
* Find an Influencer by a given matrix of following,
* or return -1 if there is no Influencer in this group.
For example, Lets suppose we have N=5 peoples {A,B,C,D,E} and the following matrix is as follows –
following[0][3] = 1;
following[0][1] = 1;
following[1][3] = 1;
following[1][0] = 1;
following[1][4] = 1;
following[4][3] = 1;
following[2][3] = 1;
following[2][4] = 1;
following[0][1] = 1;
following[1][3] = 1;
following[1][0] = 1;
following[1][4] = 1;
following[4][3] = 1;
following[2][3] = 1;
following[2][4] = 1;
then clearly 3 is celebrity.
We can build a directed graph and then find the single vertex that has out degree 0 but in degree = N-1.
Computing in-degree and out-degree of a directed graph will take O(n^2) time. Can we do better? Note that, we can easily proof that there should be only one celebrity c with the two following properties –
1. Everybody knows c 2. c doesn't know anybody
So, we can compute the celebrity in O(n) time by testing each person for the above properties. We can select a person c as a candidate celebrity and then test if c is indeed a celebrity by testing with next person. If the next person doesn’t know (or follow) the current candidate (or influencer) or the candidate knows the next person then the next person may be the celebrity. We can choose such a candidate and then test if all other person knows the candidate c and the candidate c doesn’t know anybody. If any of these properties fail we say there is no such celebrity (or influencer). The overall complexity is O(n).
public static int influencer(int[][] following){ int influencer = 0; //find the candidate influencer by testing each person i //a person i may be a candidate influencer if s/he follows nobody or som for(int i = 1; i < following.length; i++){ if(following[i][influencer] == 0 || following[influencer][i] == 1){ influencer = i; } } //verify that the candidate influencer is indeed an influencer for(int i = 0; i < following.length; i++){ if(i == influencer){ continue; } //to be influencer he/she shouldn't follow anybody and there should be nobody else who doesn't follw him/her if(following[i][influencer] == 0 || following[influencer][i] == 1){ return -1; } } return influencer; }
https://lina.bitcron.com/post/code/2018-summer-fb-intern-mian-jing
collection of objects，只能两两判断大小。只有“大”和“小”, 没有”等“。 然后也没有transitivity，也就是A > B && B > C 不能推出A > C。 类似石头剪刀布。要求找出max， max的定义是比其他所有都大。Find celebrity 变种： max 大于所有数
public Object findMax(List<Object> list){
Object candidate = list.get(0);
for(Object x : list)
{ if(x>candidate){
candidate = x;
}
}
for(Object x : list){
if(x>=candidate&&x!=candidate){
return null;
}
}
return candidate;
}
