1
$\begingroup$

Problem I am trying to solve is this:

There are n nodes, and for every pair of node $X$ and $Y$, the relation "$X \space knows \space Y$" is either $T$ or $F$. It is possible that "$X \space knows \space Y$" but "$Y \space doesn't \space know \space X$".

We are trying to find if a special node exists: that is known to everyone but doesn't know anyone. How can you find out if such node exists by using only this type of query: For any nodes $X$ and $Y$, ask $X$ "$if \space X \space knows \space Y$". This query can be asked unlimited amount of times, but the total number of queries should be $O(n)$. I can think of $O(n^2)$ case but how to do it with $O(n)$ queries? Thanks!

$\endgroup$
1
$\begingroup$

This can be done with the help of an auxiliary stack and elimination technique. Let us call the node we are looking for the special node. We can make certain conclusions by examining the relation of any two nodes as following :

  1. If node A knows node B, then A is surely not the special node and B may be the special node.

  2. If node A doesn't know node B, then B is surely not special node and A may be the special node.

  3. We repeat above two steps till we are left with only one node.

  4. Examine the last node if it doesn't know anyone and is known to everyone.

Algorithm: (uses auxiliary stack)

  1. Push all the nodes on the stack.

  2. Pop off top two nodes from the stack, discard one node based on the observations made.

  3. Push the remained node onto stack.

  4. Repeat step 2 and 3 until only one node remains in the stack.

  5. Check the remained node is the one we are looking for.

Why do we need the last step?

Because we have examined all the nodes relative to only one node which is adjacent to it on the stack but we don't know its relation with other nodes. So we need to ensure that the potential candidate for the special node is actually the special node.

This will require $3(n-1)$ comparisons in total. So the complexity is $O(n)$.

$\endgroup$
  • $\begingroup$ Thanks this really worked! I accepted your answer. $\endgroup$ – aky Nov 25 '18 at 22:07
  • $\begingroup$ This problem is also known as Celebrity problem and this problem is somewhat similar to Moore's voting algorithm $\endgroup$ – Navjot Singh Nov 26 '18 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.