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

 找回密码
 立即注册
  • 男生“换心”后秒变学霸!这才是真相
  • 18万元!日本无印良品推9平单间小屋:海边山脚都能建
  • 大疆发飙!举报干扰成都机场无人机奖100万
  • 把猫头鹰羽毛一撩 网友惊呼:竟是大长腿
  • 夸张!科学家揭开人类大秘密:《魔戒》小矮人成真
  • 捡回一条命!男子深海垂钓巨大鲨鱼上钩:结果意外
  • 胖子有救!利用大脑电磁刺激技术进行减肥:效果不错
  • 男子和机器人手臂玩刀戳手指缝:这结果没想到
  • 催眠是真的吗?其实 你被骗很多年了!
  • 担任戛纳主竞赛评委 范冰冰:深感荣幸 很有压力
  • 特朗普的狂想——不切实际的公司税计划
  • AMD:增长和损失同在,有改变才会有进步
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
  • Tom Lee警示下行风险,揭示市场三大“地雷”
  • 在Buffalo Wild Wings季度财报中出现了“天文误差”
  • 巴菲特该高兴了,IBM加息至每股1.5美元
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3038|回复: 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:如果可以每次都可以选择删除第一个或者最后一个,问最少要删掉几
次。。
--
【COACH美国代购总群】99634155
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

13

主题

90

帖子

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

主题

116

帖子

172

积分

注册会员

Rank: 2

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


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

15

主题

70

帖子

92

积分

注册会员

Rank: 2

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


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

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



--

19

主题

89

帖子

131

积分

注册会员

Rank: 2

积分
131
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有點問題。刪除頭或者尾元素並不能讓最小值更小或最大值
: 更大,所以無論怎麼刪除,都不能完成第一題的條件,對麼?





--

35

主题

128

帖子

197

积分

注册会员

Rank: 2

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

主题

93

帖子

132

积分

注册会员

Rank: 2

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


follow up有大小说错了吧

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

37

主题

115

帖子

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

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

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