在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2136|回复: 14
收起左侧

yelp 店面

[复制链接] |试试Instant~ |关注本帖
say543 发表于 2016-1-30 11:24:59 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类General 硕士 全职@Yelp - 内推 - 技术电面  | Other | fresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
我猜因该是跪了....这题最佳解 我没做出来 给一个array 已知element ranges 是1 to N 然后array size is n+1
可知至少有一个number 重复 请找出这个number 因为array很大 不能sort, array只能read 不能修改content

并不是1个value in range  只能出现2次也可以出现多次 只要找到某一个重复的就行. From 1point 3acres bbs

要求o(1) space 的solution 瓒人品 球pass... 求好的solution....

评分

1

查看全部评分

googlerr 发表于 2016-1-30 11:34:51 | 显示全部楼层
有两点不完全明白:还可能有多个数字重复出现?比如[1,1,2,2]?另外,可能出现2次以上?如[1,1,1,2,2]。如果这两个都成立,还能有O(1) space且不改array的方法吗?
回复 支持 反对

使用道具 举报

 楼主| say543 发表于 2016-1-30 12:58:38 | 显示全部楼层
googlerr 发表于 2016-1-30 11:34
有两点不完全明白:还可能有多个数字重复出现?比如[1,1,2,2]?另外,可能出现2次以上?如[1,1,1,2,2]。如 ...

[1,1,2,2]
输出1 or 2都可
[1,1,1,2,2]. 1point3acres
输出1 or 2都可. 1point 3acres 论坛

两个case都符合题意
要求真的是要o(1) space 且不能改array...
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-1-30 15:17:23 | 显示全部楼层
o(n) time?怎么感觉不太可能。。。
回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2016-1-30 15:43:02 | 显示全部楼层
https://leetcode.com/problems/find-the-duplicate-number/
回复 支持 反对

使用道具 举报

kido099 发表于 2016-1-30 22:23:40 | 显示全部楼层
楼主是怎么拿到的面试?网申还是内推的?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-1-31 02:44:29 | 显示全部楼层
tltzhsajsdr 发表于 2016-1-30 15:43
https://leetcode.com/problems/find-the-duplicate-number/

. visit 1point3acres for more.好像不完全一样。这里可能有多个duplicate,LC上只有一个
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-1-31 10:19:28 | 显示全部楼层
觉得理论上不可行啊,不改content觉得不能符合要求,很明确说了不能修改这个array么?
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-1-31 10:52:14 | 显示全部楼层
Xochitl 发表于 2016-1-31 10:19
觉得理论上不可行啊,不改content觉得不能符合要求,很明确说了不能修改这个array么?

O(n^2) 可以,不过如果是为了追求空间小而无视时间,那这题也太没意义了
回复 支持 反对

使用道具 举报

 楼主| say543 发表于 2016-1-31 12:12:40 | 显示全部楼层
googlerr 发表于 2016-1-31 10:52
O(n^2) 可以,不过如果是为了追求空间小而无视时间,那这题也太没意义了


有先考trade off的solution 最后这个没解出来的 是希望在constraint 的情况下达成 先不用考虑time complexity 能分享怎么做吗 ?
回复 支持 反对

使用道具 举报

syftalent 发表于 2016-1-31 13:31:09 | 显示全部楼层
https://leetcode.com/problems/find-the-duplicate-number/
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-1-31 13:38:14 | 显示全部楼层
say543 发表于 2016-1-31 12:12
有先考trade off的solution 最后这个没解出来的 是希望在constraint 的情况下达成 先不用考虑time comp ...

O(n^2)的方法吗?两个for循环就行了吧
for i=0:N-2
  for j=i+1:N-1
    if(arr==arr[j]) return arr

正在看楼下那个题目别人的解答,或许可行:https://leetcode.com/discuss/615 ... difying-explanation
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-1 03:13:20 | 显示全部楼层
这两个方法确实都可行:O(n log n): https://leetcode.com/discuss/615 ... difying-explanation. from: 1point3acres

O(n): https://leetcode.com/discuss/608 ... hanging-input-array. 1point 3acres 论坛



.本文原创自1point3acres论坛
补充内容 (2016-2-1 03:14):
时间复杂度写反了,上面的是O(n),下面的是O(n log n)
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-2-1 04:29:29 | 显示全部楼层
googlerr 发表于 2016-2-1 03:13. more info on 1point3acres
这两个方法确实都可行:O(n log n): https://leetcode.com/discuss/61514/understood-solution-space-witho ...
.留学论坛-一亩-三分地
啊对,这个slow,fast我还做过,我忘了。。。我还以为我当时用的根据index replace呢
回复 支持 反对

使用道具 举报

haoxuango 发表于 2016-2-1 04:35:33 | 显示全部楼层
googlerr 发表于 2016-2-1 03:13. 牛人云集,一亩三分地
这两个方法确实都可行:O(n log n): https://leetcode.com/discuss/61514/understood-solution-space-witho ...
. 一亩-三分-地,独家发布
是的, 就是一样的思路 。 楼主内推多久有的面试?
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 09:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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