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

 找回密码
 立即注册
  • 章子怡的好后妈人设崩塌? 继女被曝和奶奶生活
  • 好着呢!杨幂刘恺威参加女儿班级活动 一家人同框
  • 美图:我们用户大多是“白富美” 不愁赚钱
  • 网红面包店深夜发声明 承认面粉过期
  • 手机以换壳为本?华为余承东:没有创新才这么干
  • 腾讯二把手悄然交接 一人拿到大笔钱一人掌握更大权
  • 那些恐怖电影中的角色生活中原来长这样
  • 《神奇女侠》女神新手办亮相:脸崩了 但美腿还能玩一年
  • 再进华夏中原 小米之家郑州第二店正式开业
  • 中国人的睡眠:西藏最幸福 海南最可怜
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3031|回复: 13

    内推面经 -这道算法题follow-up让所有人都跪了,你会做吗?- 唐人社区|北美华人论坛

    [复制链接]

    9

    主题

    28

    帖子

    44

    积分

    新手上路

    Rank: 1

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

    唐人社区-北美华人论坛-内推面经版-这道算法题follow-up让所有人都跪了,你会做吗?


      JobHunting
    标 题: 这道算法题follow-up让所有人都跪了,你会做吗?


    给你你个数组,要你返回数组的最小值的平方是否小于最大值。题目很简单,需要注意
    的就是最小值的平方可能越界。

    follow-up:如果这个数组不满足第一题中的条件,然后允许你执行“删除数组的第一
    个元素”的操作,让你返回要执行多少次,也就是删除多少个数组前面的元素后才能满
    足第一题中的条件。如果删完都不满足,返回-1;这一题小哥反复提示才想出来一个O
    (n)的做法,然后今天看还有个小bug,哎。。

    接着follow-up:如果可以每次都可以选择删除第一个或者最后一个,问最少要删掉几
    次。。
    --

    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    13

    主题

    87

    帖子

    125

    积分

    注册会员

    Rank: 2

    积分
    125
    QQ
    发表于 2016-11-22 01:41:18 | 显示全部楼层
    JobHunting
    标  题: Re: Re:这道算法题follow-up让所有人都跪了,你会做吗?


    你仔细想想 删除元素只可能让最小值变大 以及 最大值变小 这样如果原题不成立 那
    么删除后更不会成立
    应该是楼主描述反了

    【 在 JavaDev (码神) 的大作中提到: 】
    : 删除头尾元素可以改变整个数组的最大值和最小值



    ★ 发自iPhone App: ChineseWeb 13
    --
    Scottrade ReferALL code: JHFV5891 用了附赠10个包子聊表谢意

    30

    主题

    112

    帖子

    172

    积分

    注册会员

    Rank: 2

    积分
    172
    QQ
    发表于 2016-11-22 02:17:00 | 显示全部楼层
    JobHunting
    标  题: Re:这道算法题follow-up让所有人都跪了,你会做吗?


    我覺得這個題的follow up有點問題。刪除頭或者尾元素並不能讓最小值更小或最大值
    更大,所以無論怎麼刪除,都不能完成第一題的條件,對麼?
    --

    15

    主题

    68

    帖子

    92

    积分

    注册会员

    Rank: 2

    积分
    92
    QQ
    发表于 2016-11-22 02:35:50 | 显示全部楼层
    JobHunting
    标  题: Re: Re:这道算法题follow-up让所有人都跪了,你会做吗?


    删除头尾元素可以改变整个数组的最大值和最小值

    【 在 zou2016 (middleboy) 的大作中提到: 】
    : 我覺得這個題的follow up有點問題。刪除頭或者尾元素並不能讓最小值更小或最大值
    : 更大,所以無論怎麼刪除,都不能完成第一題的條件,對麼?



    --

    18

    主题

    87

    帖子

    124

    积分

    注册会员

    Rank: 2

    积分
    124
    QQ
    发表于 2016-11-22 03:01:19 | 显示全部楼层
    JobHunting
    标  题: 这道算法题follow-up让所有人都跪了,你会做吗?


    给你你个数组,要你返回数组的最小值的平方是否小于最大值。题目很简单,需要注意
    的就是最小值的平方可能越界。

    follow-up:如果这个数组不满足第一题中的条件,然后允许你执行“删除数组的第一
    个元素”的操作,让你返回要执行多少次,也就是删除多少个数组前面的元素后才能满
    足第一题中的条件。如果删完都不满足,返回-1;这一题小哥反复提示才想出来一个O
    (n)的做法,然后今天看还有个小bug,哎。。

    接着follow-up:如果可以每次都可以选择删除第一个或者最后一个,问最少要删掉几
    次。。
    --

    22

    主题

    97

    帖子

    144

    积分

    注册会员

    Rank: 2

    积分
    144
    QQ
    发表于 2016-11-22 03:50:17 | 显示全部楼层
    JobHunting
    标  题: Re: Re:这道算法题follow-up让所有人都跪了,你会做吗?


    确实有点怪,不过我认为是lz描述反了


    【 在 zou2016 (middleboy) 的大作中提到: 】
    : 我覺得這個題的follow up有點問題。刪除頭或者尾元素並不能讓最小值更小或最大值
    : 更大,所以無論怎麼刪除,都不能完成第一題的條件,對麼?





    --

    34

    主题

    124

    帖子

    194

    积分

    注册会员

    Rank: 2

    积分
    194
    QQ
    发表于 2016-11-22 04:03:19 | 显示全部楼层
    JobHunting
    标  题: Re: 这道算法题follow-up让所有人都跪了,你会做吗?


    第一个follow-up, 从后往前找最长的满足要求的序列不就好了吗,O(n)

    第二个follow-up,O(nlogn)容易,O(n)要再想想
    --

    25

    主题

    95

    帖子

    154

    积分

    注册会员

    Rank: 2

    积分
    154
    QQ
    发表于 2016-11-22 04:38:11 | 显示全部楼层
    JobHunting
    标  题: Re: 这道算法题follow-up让所有人都跪了,你会做吗?


    lz描述应该是正确的。因为最小数可能是负数。

    第一个follow-up,从后往前找,不需要都满足,找到满足的最小index
    第二个 use min to split to subarrays , 再对每个subarray check, recursion 找
    到最长的满足. O(nlogn)


    【 在 wishee (温顺的野猪) 的大作中提到: 】
    : 第一个follow-up, 从后往前找最长的满足要求的序列不就好了吗,O(n)
    : 第二个follow-up,O(nlogn)容易,O(n)要再想想




    --
    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?

    24

    主题

    91

    帖子

    132

    积分

    注册会员

    Rank: 2

    积分
    132
    QQ
    发表于 2016-11-22 04:54:08 | 显示全部楼层
    JobHunting
    标  题: Re: 这道算法题follow-up让所有人都跪了,你会做吗?


    follow up有大小说错了吧

    越删 min^2<max可能性越小
    --

    37

    主题

    113

    帖子

    193

    积分

    注册会员

    Rank: 2

    积分
    193
    QQ
    发表于 2016-11-22 05:02:07 | 显示全部楼层
    JobHunting
    标  题: Re:这道算法题follow-up让所有人都跪了,你会做吗?


    搞一個bst,查lowerKey(min*min), 存在就返回rank,不存在就回-1
    --
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -这道算法题follow-up让所有人都跪了,你会做吗?- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -这道算法题follow-up让所有人都跪了,你会做吗?- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
    Sasa.com

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

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

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

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