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

 找回密码
 立即注册
  • 《汉尼拔》第四季有回归的可能性了!
  • 略惊悚:Wi-Fi变狗仔 还能全息成像
  • 厉害了!中国动车组获欧盟铁路最高认证
  • 黄种人首进9.9秒!苏炳添百米创个人最好成绩
  • 北斗/GPS导航定位基准服务启用!精度/信号大提升
  • 神秘外星人在哪?科学家发现了这个地方...
  • 黄金竟有这神用途:成抗击癌症的“子弹”
  • 海盗传说:真的有海怪、美人鱼吗?
  • 夏天穿浅色衣服更凉快?被骗好多年……
  • 为什么互联网大佬都开始养猪养鸡了?
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3043|回复: 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

    主题

    92

    帖子

    133

    积分

    注册会员

    Rank: 2

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


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

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



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

    30

    主题

    121

    帖子

    172

    积分

    注册会员

    Rank: 2

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


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

    16

    主题

    71

    帖子

    107

    积分

    注册会员

    Rank: 2

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


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

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



    --

    19

    主题

    90

    帖子

    131

    积分

    注册会员

    Rank: 2

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


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

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

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

    23

    主题

    100

    帖子

    147

    积分

    注册会员

    Rank: 2

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


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


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





    --

    36

    主题

    131

    帖子

    203

    积分

    注册会员

    Rank: 2

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


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

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

    25

    主题

    96

    帖子

    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

    主题

    94

    帖子

    132

    积分

    注册会员

    Rank: 2

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


    follow up有大小说错了吧

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

    37

    主题

    119

    帖子

    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|唐人社区

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

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