美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 没悬念!世界最美的十位空姐一览:中国女孩第一
  • 女子伪造身份注册Facebook 美国社会送其坐牢一年
  • 余额宝回光返照!每日收益大涨10%
  • 银行卡存600万剩690 那600万存款“飞”去哪了?
  • 小猪尾巴被剪掉生无可恋:遇到一群汪后惊人变化
  • 中国诺奖青蒿素新突破!国外证实其有助拯救糖尿病
  • 画面震惊!饥饿松鼠竟捕食大蛇:活生生咬死
  • NASA公布最新照片:太阳竟然笑了
  • 居然这样洗水果农药残留最低:真相了!
  • 怎么分辨配偶:大猩猩看一眼屁股即可
  • 标普上涨7%,特朗普的政策不约束通货膨胀
  • 亿万富翁在黎明醒来的原因
  • 舒尔茨的退出,但继续持有星巴克股票
  • 企业税法变化的赢家和输家
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3006|回复: 15

内推面经 -一道linkedin常见题,我的答案对吗?- 唐人社区|北美华人论坛

[复制链接]
TA在交友中心
0 0 17
  @ME:   

8

主题

26

帖子

42

积分

新手上路

Rank: 1

积分
42
QQ
发表于 2016-11-17 03:17:40 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推HP?mod=forumdisplay&fid=83&fromuid=1" target="_blank" class="relatedlink">面经版-一道linkedin常见题,我的答案对吗?


  JobHunting
标 题: 一道linkedin常见题,我的答案对吗?


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

--

微信公众号】funinusa : 每日微信滚动更新美国市场打折团购折扣Coupon讯息。
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

TA在交友中心
0 0 46
  @ME:   

21

主题

77

帖子

117

积分

注册会员

Rank: 2

积分
117
QQ
发表于 2016-11-17 04:21:55 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


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

【 在 coldknight (冷骑士) 的大作中提到: 】
: 同意, 楼主贴的code有多余的check, 试试去掉



--
TA在交友中心
0 0 43
  @ME:   

19

主题

94

帖子

131

积分

注册会员

Rank: 2

积分
131
QQ
发表于 2016-11-17 04:43:20 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


我觉得不用DFS。
你可以记录每一个candidate的 indegree,最后看谁的indegree是0,谁就是“
influencer”。这样的话时间复杂度是O(n^2),空间复杂度是O(n)。
--
TA在交友中心
0 0 57
  @ME:   

24

主题

90

帖子

144

积分

注册会员

Rank: 2

积分
144
QQ
发表于 2016-11-17 04:48:35 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


influence应该是有传递关系的吧?否则,x,y轴各扫一遍就行了。

有传递关系的话,那就y轴扫描一次,找到没有被influnced的点,如果有多于1个点,
那么就没有influencer

如果只有1个点,然后从这点开始做bfs, 看是否cover所有的点。

复杂度应该是(X*Y)级别


--
TA在交友中心
0 0 23
  @ME:   

11

主题

206

帖子

229

积分

中级会员

Rank: 3Rank: 3

积分
229
QQ
发表于 2016-11-17 05:10:05 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


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


【 在 ooxxoo () 的大作中提到: 】
: 这不是lc celebrity 的变种吗?



--
TA在交友中心
0 0 56
  @ME:   

24

主题

98

帖子

148

积分

注册会员

Rank: 2

积分
148
QQ
发表于 2016-11-17 05:26:55 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


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;
    }
--
TA在交友中心
0 0 44
  @ME:   

20

主题

85

帖子

125

积分

注册会员

Rank: 2

积分
125
QQ
发表于 2016-11-17 05:28:54 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


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;
    }
--
TA在交友中心
0 0 46
  @ME:   

20

主题

79

帖子

122

积分

注册会员

Rank: 2

积分
122
QQ
发表于 2016-11-17 05:49:29 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


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

19

主题

88

帖子

128

积分

注册会员

Rank: 2

积分
128
QQ
发表于 2016-11-17 05:57:44 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


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

【 在 sapphirewing (Audrey的树) 的大作中提到: 】
: celebrity解法是O(n)时间 O(1)空间



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
TA在交友中心
0 0 59
  @ME:   

29

主题

91

帖子

149

积分

注册会员

Rank: 2

积分
149
QQ
发表于 2016-11-17 06:18:10 | 显示全部楼层
JobHunting
标  题: Re: 一道linkedin常见题,我的答案对吗?


同意

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

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



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?
您需要登录后才可以回帖 登录 | 立即注册  

本版积分规则

玩美生活FunInUSA.net 华人娱乐论坛发布的内推面经 -一道linkedin常见题,我的答案对吗?- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -一道linkedin常见题,我的答案对吗?- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

Copyright ©2011 FunInUSA.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA

安全联盟认证 安全联盟认证

快速回复 返回顶部 返回列表