一道linkedin常见题，我的答案对吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道linkedin常见题，我的答案对吗？

一道linkedin常见题，我的答案对吗？# JobHunting - 待字闺中

J*v2016-11-02 07:11

1 楼

Consider an X x Y array of 1's and 0s. The X axis represents "influences"
meaning that X influences Y. So, for example, if $array[3,7] is 1 that means
that 3 influences 7.
An "influencer" is someone who influences every other person, but is not
influenced by any other member.
Given such an array, write a function to determine whether or not an
"influencer" exists in the array.
https://www.glassdoor.com/Interview/Consider-an-X-x-Y-array-of-1-s-and-0s-
The-X-axis-represents-influences-meaning-that-X-influences-Y-So-for-example-
i-QTN_498161.htm

J*v2016-11-02 07:11

2 楼

public boolean checkInfluencer(boolean[][] followingMatrix) {
if (followingMatrix == null || followingMatrix.length == 0 ||
followingMatrix[0].length == 0)
return false;
int len = followingMatrix.length;
int res = 0;
for (int i = 1; i < len; ++i) {
if (!followingMatrix[i][res] || followingMatrix[res][i]) {
res = i;
}
}
// verify it is indeed an influencer
for (int i = 0; i < len; i++) {
if (i == res) {
continue;
}
if (!followingMatrix[i][res] || followingMatrix[res][i]) {
return false;
}
}
return true;
}

J*v2016-11-02 07:11

3 楼

public boolean hasInfluencer(int[][] followingMatrix) {
if (followingMatrix == null || followingMatrix.length == 0 ||
followingMatrix[0].length == 0)
return false;
int len = followingMatrix.length;
int res = 0;
for (int i = 1; i < len; ++i) {
if (followingMatrix[i][res] == 0 || followingMatrix[res][i] == 1
) {
res = i;
}
}
// verify it is indeed an influencer
for (int i = 0; i < len; i++) {
if (i == res) {
continue;
}
if (followingMatrix[i][res] == 0 || followingMatrix[res][i] == 1
) {
return false;
}
}
return true;
}

o*o2016-11-02 07:11

4 楼

这不是lc celebrity 的变种吗？

J*v2016-11-02 07:11

5 楼

是变种，但leetcode上说最多有一个名人，linkedin这道题有0个或多个influencers都
有可能。

【在 o****o 的大作中提到】

: 这不是lc celebrity 的变种吗？

k*a2016-11-02 07:11

6 楼

influence应该是有传递关系的吧？否则，x,y轴各扫一遍就行了。
有传递关系的话，那就y轴扫描一次，找到没有被influnced的点，如果有多于1个点，
那么就没有influencer
如果只有1个点，然后从这点开始做bfs，看是否cover所有的点。
复杂度应该是（X*Y)级别

k*a2016-11-02 07:11

7 楼

如果有多个，那就违背了
An "influencer" is someone who influences every other person, but is not
influenced by any other member.

【在 J*****v 的大作中提到】

: 是变种，但leetcode上说最多有一个名人，linkedin这道题有0个或多个influencers都
: 有可能。

J*v2016-11-02 07:11

8 楼

还是你观察仔细，那就是和leetcode用同样的解法

【在 k******a 的大作中提到】

:
: 如果有多个，那就违背了
: An "influencer" is someone who influences every other person, but is not
: influenced by any other member.

j*g2016-11-02 07:11

9 楼

我觉得不用DFS。
你可以记录每一个candidate的 indegree，最后看谁的indegree是0，谁就是“
influencer”。这样的话时间复杂度是O(n^2)，空间复杂度是O(n）。

s*g2016-11-02 07:11

10 楼

celebrity解法是O(n)时间 O(1)空间

【在 j********g 的大作中提到】

: 我觉得不用DFS。
: 你可以记录每一个candidate的 indegree，最后看谁的indegree是0，谁就是“
: influencer”。这样的话时间复杂度是O(n^2)，空间复杂度是O(n）。

c*t2016-11-02 07:11

11 楼

同意，楼主贴的code有多余的check, 试试去掉

【在 s**********g 的大作中提到】

: celebrity解法是O(n)时间 O(1)空间

J*v2016-11-02 07:11

12 楼

我这已经是O(N) time, O(1) space了，要去只能去一个followingMatrix[res][i] ==
1
你确定要去掉吗？

【在 c********t 的大作中提到】

: 同意，楼主贴的code有多余的check, 试试去掉

w*u2016-11-02 07:11

13 楼

code里的followingMatrix含义到底是什么?
如果说下面的statement 是正确的话
if $array[3,7] is 1 that means
that 3 influences 7.
那么条件应该改成.
if (followingMatrix[i][res] == 1 || followingMatrix[res][i] == 0

c*t2016-11-02 07:11

14 楼

同意
LZ Time O(n) Space O(1)没问题。第一个循环只用 if (followingMatrix[i][res] =
= 1) 即可，第二个循环有一部分第一个循环已经check了，不需要再做。

【在 w***u 的大作中提到】

: code里的followingMatrix含义到底是什么?
: 如果说下面的statement 是正确的话
: if $array[3,7] is 1 that means
: that 3 influences 7.
: 那么条件应该改成.
: if (followingMatrix[i][res] == 1 || followingMatrix[res][i] == 0