访谈:关于人员匹配

Question

我最近看到一个公司的面试问题说:

一群人,你可以打电话Know(i, j)询问是否i有人知道j,返回值是true(i知道j)或false(i不知道j).找到其他人都认识的人,但他不认识任何人.

我可以想到一个O(N^2)实现,这样你就可以将每个人与每个人的方法相匹配,从而消除任何真正认识某人的人.然而,我想不出比这更快的实现.

任何人都可以提供帮助或提示吗？

Answer 1

我们可以通过简单的算法在线性时间内完成此操作.在两次查询中,我们可以消除至少一个候选人 - 选择两个人,并i用Know(i,j)或删除人~Know(j,i).