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

 找回密码
 立即注册
  • NASA神秘发现:超越太阳系!
  • 欧洲惊现致命放射性粒子 科学家都蒙了
  • 澳洲一轻型飞机撞上商场坠毁 5人全部死亡
  • 科学家破译蝙蝠聊天内容:对飙垃圾话
  • 范冰冰穿花衣旧照曝光 网友调侃:还以为是谢大脚
  • 杨幂揪心想念女儿 硬起来保护家庭:别说我家人
  • 高晓松晒收藏的《金瓶梅》 书都被读烂了
  • 宇宙神秘难解之题:中国科学家搞定了
  • 历史首次!杨振宁弃美国国籍 转为中科院院士
  • 淘宝违反“广告法”?被起诉索赔20万
  • 道琼斯、标准普尔、Nasdaq和罗素创纪录新高,上涨超过10%
  • AMD股票预期将回升
  • 推动美国股市走高的动力与阻力
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3025|回复: 13

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

[复制链接]

9

主题

26

帖子

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

主题

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

主题

111

帖子

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

主题

85

帖子

124

积分

注册会员

Rank: 2

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


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

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

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

20

主题

94

帖子

137

积分

注册会员

Rank: 2

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


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


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





--

32

主题

122

帖子

187

积分

注册会员

Rank: 2

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


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

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

24

主题

94

帖子

139

积分

注册会员

Rank: 2

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

主题

90

帖子

132

积分

注册会员

Rank: 2

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


follow up有大小说错了吧

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

37

主题

112

帖子

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

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

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