CareerCup

Well said.
+1

I don't know if that finds all the celebrities.

@bunnybare: Amazing. You managed to skip right past the very first sentence.

If his answer is only for doing one celebrity, then the well said comment is unworthy.

If his answer is saying only one celebrity look up is possible given the linear time restriction, then I'll accept it.

@bunnybare: Only one celebrity is possible. Period. Irrespective of the algorithm time complexity required.

@bunnyabare, According to the rules, there can be at most one celebrity. Proof: Suppose A and B are both celebrities. A knows B by virtue of B's celebrity and the rule that a celebrity is known by everybody. But then A can't be a celebrity, by virtue of the rule that celebrities can't know anyone. Since any pair of celebrities leads to a contradiction of the rules, there can be at most one celebrity.

implement showell30's algorithm with c++

//a[i][j] =1 denotes person i know person j
int Celebrity(vector<vector<int> >& a)
{
	int candidate=0;
	int i=1;
	while(i < a.size())
	{
		if(!a[i][candidate] || a[candidate][i])
			candidate=i;
		i++;
	}
	//check
	for(int i=0;i<a.size();i++)
	{
		if(i!=candidate && (!a[i][candidate] || a[candidate][i]))
		return -1;//no celebrity exist
	}
	return candidate;
}

@duckling That's a nice refinement of my solution. As your code illustrates, there's no need to actually perform a swap; just change the value of candidate to be the new i.

@duckling : Nice efficient implementation.. but could you please explain why are you using 'or' instead of 'and' in the if-condition ? because if a[i][candidate]=1, then i can be no way in which i can be the next possible candidate.. plz verify.

@ss,i think showell30 explained it very clearly," see if either 2 doesn't know 1 or 1 knows 2". if person i doesn't know the candidate or the candidate knows person i,then the candidate is not a celebrity

@duckling One possible optimization here is that we try to eliminate candidates more aggressively. When you have i and candidate, call both KNOW(i, candidate) and KNOW(candidate, i). If both know each other or both don't know each other, then you've eliminated both, and you can advance candidate to be i+1 and i to be i+2. I haven't thought this all the way through, and it might not be worth the trouble, but if you can get all the bookkeeping right, it might eliminate the final linear pass and possibly speed up the first linear pass, especially if the KNOW() function call is expensive for some reason.

Here is a full JavaScript solutions, including structure, which represents the relations among people:

The relations:
We have people A, B, C, D, E. In the example below "A" knows B, C and E.

var relations = {
    A: {
        'B': 1,
        'C': 1,
        'E': 1
    },
    B: {
        'A': 1,
        'C': 1,
        'D': 1
    },
    C: {},
    D: {
        'B': 1,
        'C': 1,
        'E': 1
    },
    E: {
        'A': 1,
        'C': 1
    }
};

Here is the code:

find: function(array, relations) {
    for (var i = 0, j = array.length - 1; array.length > 1;) {
        if (this.isRelated(array[i], array[j], relations)) {
            array.splice(i, 1);

            --j;
        }
        else if (this.isRelated(array[j], array[i], relations)) {
            array.splice(j--, 1);
        }
        else {
            array.splice(j, 1);
            array.splice(i, 1);

            j -= 2;
        }
    }

    if (array.length === 1) {
        return array[0];
    }
}

The answer is C. The time is O(n)

And here is isRelated function, forgot to paste it:

isRelated: function(source, dest, relations) {
    var sourceRelations = relations[source];

    return sourceRelations[dest];
}

@duckling - okk.. got it.. actually I was thinking the other way round..

showell30@yahoo.com We can eliminate both A and B at the same time if they don't know each other. Since they cannot both be celebs, and neither is known, they must both be non-celebs. I'm not sure if you considered this but it isn't in your original description.

This reduces the runtime but not the complexity.

(Sweet solution BTW)

@Barry, thanks. If you scroll up in the comments, I respond to duckling about the optimization where you can eliminate A and B at the same time. As you point out, it doesn't reduce the overall complexity, which is why I'd be somewhat shy about trying to handle this case, unless I were really trying to squeeze out extra performance.

we can eliminate A and B if both knows or both doesnot know each other

@goutham467, Instead of thinking of this as a sorting problem, think of it as a min-item-in-list problem. You can easily find the minimum element of an unsorted list in linear time, as long as the list has some sort of transitive ordering. The twist here is that you don't have a truly transitive ordering, since A can know B can know C can A. From the celebrity's standpoint, though, it doesn't really matter, because he or she is not allowed to be in any strange friendship cycles.

When you solve the traditional min-item-in-a-list problem, you have a provisional min and you keep trying to dethrone the provisional min as you iterate through the list. For the celebrity problem, it's the same algorithm with a slightly different mechanism to dethrone the provisional celebrity.

@showell
Thanks for a such a clear explanation."min-item-in-list" problem, how can I forgot a basic thing.
I am struggling with a question though, could you please comment on it, id=15489912

@goutham467 BTW here is a way to solve this that explicitly uses a comparison function with a generic algorithm:

def max_by(lst, cmp):
    candidate = 0
    for i in range(1, len(lst)):
        if cmp(lst[candidate], lst[i]) > 0:
            candidate = i
    return lst[candidate]

def find_celebrity(lst):
    # Simplifying assumption: assume the most famous
    # person is indeed a celebrity.
    return max_by(lst, famous_cmp)

def famous_cmp(i, j):
    if know(i, j):
        return 1
    else:
        return -1

def know(i, j):
    # 40 is our celebrity
    if i == 40:
        return False
    if j == 40:
        return True
    # For others, return something
    # predictable
    return  i == j + 10 or i == j - 10

print find_celebrity([10, 20, 30, 40, 50])

I omitted the extra step to fully verify celebrity status.

#include <stdio.h>
#include <stdlib.h>


int people;
extern int knows(int a, int b);

int celebrity() {
int celebrity, left = 1, right = people;
while (left < right) {
if (knows(left, right)) {
left++;
} else {
right--;
}
}
celebrity = left;
return celebrity;
}

int main(int argc, char *argv[]) {
printf("Number of people: ");
scanf("%d", &people);
printf("The celebrity is number %d\n", celebrity());
return 0;
}

Time complexity is N to 3N. Final check takes up to 2N calling of KNOWS method.

Your check doesn't work.

Better:

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.

Although it's overkill for this problem, you can model this like an NCAA March Madness single-elimination, which runs in linear time. For each "game," see if A knows B. If A knows B, then B wins, else A wins. After 63 games, you will have a winner that is least as "famous" as all other contenders. To verify that they're actually a celebrity, you'd still need to check the winner's relationship to the 63 losers in another linear pass.

I like the NCAA solution better. Here's the semi-solution with modification to Integer.

public static Integer getMax(List<Integer> list)
    {
	Queue<Integer> queue = new LinkedList<Integer>(list);
	Queue<Integer> que = new LinkedList<Integer>();

	while (queue.size() > 1)
	{
	    while (!queue.isEmpty())
	    {
		Integer first = queue.poll();
		Integer second = queue.poll();

		if (second != null)
		{
		    que.add(first > second ? first : second);
		}
		else
		{
		    que.add(first);
		}
	    }
	    queue.addAll(que);
	    que.clear();
	}
	
	return queue.poll();
    }