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

 找回密码
 立即注册
  • 李英爱新剧《师任堂》接档《蓝海传说》 26日首播
  • 48岁许晴与友人庆生 素颜出镜似18岁少女
  • 林允牙齿大变样 网友惊呼认不出
  • 姚晨三亚度假摘芒果 偶遇儿时同学趣事多
  • 赵丽颖有新恋情?邓超一不小心提到了她男朋友
  • 林心如谈“幸福”的定义:每天都在笑
  • 外媒称中国正在研发百亿亿次超级计算机
  • 邓超狂晒打篮球帅照 孙俪冷回10字笑翻众人
  • 48亿:北京打造全球最亮“慧眼”
  • 中国基建狂魔:11072米世界第一航道桥合龙
  • 中国建立了146亿美元的互联网投资基金
  • 历届美国总统经历的市场
  • 市场:特朗普就任的第一周
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3017|回复: 13

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

[复制链接]

9

主题

25

帖子

43

积分

新手上路

Rank: 1

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

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


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


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

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

接着follow-up:如果可以每次都可以选择删除第一个或者最后一个,问最少要删掉几
次。。
--
【中国海淘拼单总群】36382164
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

13

主题

86

帖子

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个包子聊表谢意

29

主题

109

帖子

157

积分

注册会员

Rank: 2

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


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

15

主题

67

帖子

92

积分

注册会员

Rank: 2

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


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

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



--

18

主题

84

帖子

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





--

31

主题

119

帖子

169

积分

注册会员

Rank: 2

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


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

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

24

主题

91

帖子

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

主题

89

帖子

132

积分

注册会员

Rank: 2

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


follow up有大小说错了吧

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

36

主题

112

帖子

192

积分

注册会员

Rank: 2

积分
192
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.com All Right Reserved.  Powered by Discuz! X3.0 小黑屋

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

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

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