一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1278|回复: 14
收起左侧

yelp 店面

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

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

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

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

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

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

要求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]-google 1point3acres
输出1 or 2都可

两个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/

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

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

 楼主| say543 发表于 2016-1-31 12:12:40 | 显示全部楼层
googlerr 发表于 2016-1-31 10:52. 鍥磋鎴戜滑@1point 3 acres
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. 鍥磋鎴戜滑@1point 3 acres

O(n): https://leetcode.com/discuss/608 ... hanging-input-array


.鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-2-1 03:14):
时间复杂度写反了,上面的是O(n),下面的是O(n log n)
回复 支持 反对

使用道具 举报

Xochitl 发表于 2016-2-1 04:29:29 | 显示全部楼层
googlerr 发表于 2016-2-1 03:13
这两个方法确实都可行: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 ...
. visit 1point3acres.com for more.
是的, 就是一样的思路 。 楼主内推多久有的面试?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 05:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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