Given there are N people, .....

[vikrantt]

Given there are N people, one of them is such as he is known by everybody but doesn't anybody.

How to identify him?
Also, how to identify whether such a person exist in the given set.

[JosAH]

@vikrantt
Draw the set of people as a graph: each person is a vertex in the graph and if person A 'knows' person B a directed edge is drawn from vertex A to vertex B.

A person who doesn't know anybody but is known by everybody has no outgoing edges but N-1 incoming edges where N is the number of vertexes in the graph.

kind regards,

Jos

[vikrantt]

Hey Jos,
Thanks for replying,

But how do you code it with linear time complexity?

[vikrantt]

for simplicity sake we can also assume that the input is given as an adjacency matrix.

[JosAH]

@vikrantt
A column j should contain all zeros (node j doesn't know anyone) while a row j (except possibly on the main diagonal) should contain all ones (everybody knows person j). If the diagonal element A[j][j] is one as well then, by definition person j knows itself).

kind regards,

Jos

[vikrantt]

yeah,

I got that much. But I do not think this is implementable O(N)...this would result in O(N^2)

Thanks a lot.

[JosAH]

@vikrantt
It depends on the meaning of N; if N is the number of vertexes in the graph the computing time is O(N^2), if N is the number of edges in the graph then the computing time is O(N).

kind regards,

Jos

[donbock]

This may be a silly question, but ... when you say "linear time complexity" do you mean linear compared to the number of people or linear compared to the number of relationships?

The second interpretation provides a loophole that justifies an O(N^2) algorithm.

Whoops! I don't know why I didn't realize at the time that all I did was restate Jos' cogent post.

[JosAH]

@donbock
*ahem* great minds think alike ...

kind regards,

Jos ;-)