美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 李嘉诚会见AlphaGo之父 称投资DeepMind是可贵缘份
  • 中国最大快递圈子诞生!菜鸟与15家快递结盟
  • 0:3输给AlphaGo后柯洁和人下了一盘:结果轻松快乐
  • Windows遭遇史上最大攻击:微软却在疯狂圈粉
  • 跨性别上卫生间遭拒:库克等14位IT大佬怒反对
  • 下一次真正的电池技术突破 我们要等多少年?
  • 世嘉经典街机《疯狂出租车》登陆iOS/Android:免费!
  • 逼格瞬间爆棚:索尼PS4 Slim土豪金版曝光
  • 《守望先锋》发售一年之后:仍神一样存在
  • 《小魔女学园》游戏年内登PS4平台:公布首支预告片
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3024|回复: 16

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

    [复制链接]

    8

    主题

    28

    帖子

    42

    积分

    新手上路

    Rank: 1

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

    唐人社区-北美华人论坛-内推面经版-一道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

    --

    【返利网站】返利额度最高的海外购物返利网站Topcashback:平均返利7~10%,注册就送$10点我注册
    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    27

    主题

    92

    帖子

    150

    积分

    注册会员

    Rank: 2

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


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

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



    --

    20

    主题

    102

    帖子

    140

    积分

    注册会员

    Rank: 2

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


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

    27

    主题

    97

    帖子

    157

    积分

    注册会员

    Rank: 2

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


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

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

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

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


    --

    11

    主题

    217

    帖子

    229

    积分

    中级会员

    Rank: 3Rank: 3

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


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


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



    --

    27

    主题

    109

    帖子

    169

    积分

    注册会员

    Rank: 2

    积分
    169
    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;
        }
    --

    24

    主题

    98

    帖子

    149

    积分

    注册会员

    Rank: 2

    积分
    149
    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;
        }
    --

    23

    主题

    95

    帖子

    142

    积分

    注册会员

    Rank: 2

    积分
    142
    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
    --

    25

    主题

    101

    帖子

    162

    积分

    注册会员

    Rank: 2

    积分
    162
    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?

    32

    主题

    101

    帖子

    166

    积分

    注册会员

    Rank: 2

    积分
    166
    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常见题,我的答案对吗?- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
    Sasa.com

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

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

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

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