Interview: on People Matching

Question

I saw this interview question recently for a firm that said:

Group of people, you can call Know(i, j) to ask if ith person knows jth, the return value is true (i knows j) or false (i does not know j). Find the person that everybody else knows him but he knows nobody.

I can think of a O(N^2) implementation such that you just match every person with the method with every other person, eliminating anyone who actually knows someone. I however cannot think of a faster implementation than this.

Can anyone help or give hints?

Answer 1

We can do this in linear time with a simple algorithm. In two lookups, we can eliminate at least one candidate -- pick two persons, and remove person i with Know(i,j) or ~Know(j,i).

Answer 2

All we have to do is -

1. Find out a person who doesn't know anyone else
2. And then check everyone knows that person

Step 1: Find out a person who doesn't know anyone else. Initially every one is our candidate. So let's start with any one i as current node. Iterate over all candidates j. If Knows(i, j) is false. Then j cannot be our candidate. So remove j from candidates. If Knows(i, j) is true for any j, then i cannot be our candidate, so current node will be updated to j, and remove node i. Repeat this until we can't update current node. The last current node is our final candidate. This will be actually O(N) because at each step we are actually removing one node, either i or j.

Step 2: We found a person who doesn't know anyone else. But we've to verify that everyone else knows him. What we can just do is iterate over all the nodes and check, which is O(N). If we found that this is not our node, then there is no such solution. Because there cannot be another node k, which is the solution, as i doesn't know k.

We can use a link list for storing the list of candidates so that removing a candidate will be O(1).