当前在线人数8398
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
求问Jane Street一道面试题
[版面:待字闺中][首篇作者:frederickyl] , 2015年09月22日13:35:29 ,1241次阅读,20次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
frederickyl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: frederickyl (frederickyl), 信区: JobHunting
标  题: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 13:35:29 2015, 美东)

有个大小为n+1的数组,数组中的每个元素是[1,n],所以至少有两个是重复的。例如n=
4, 数组为[2,3,4,1,1]或者[2,3,1,1,1],要求找出重复的那个数字。复杂度要求:空
间O(1), 时间复杂度:小于O(n^2)。不能改变原来数组。

请各位看清题目再回复,和LC的题目不一样。

--
※ 修改:·frederickyl 於 Sep 22 18:03:23 2015 修改本文·[FROM: 128.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 67.]

 
deepthroat
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: deepthroat (The wind is rising. We must try to live), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 13:41:27 2015, 美东)

XOR?


【 在 frederickyl (frederickyl) 的大作中提到: 】
: 有个大小为n+1的数组,数组中的每个元素是[1,n],所以至少有两个是重复的。例如
n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1],要求找出重复的那个数字。复杂度要求:空
: 间O(1), 时间复杂度:小于O(n^2)。不能改变原来数组。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 172.]

 
frederickyl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: frederickyl (frederickyl), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 13:42:40 2015, 美东)

能详细说说吗?
【 在 deepthroat (The wind is rising. We must try to live) 的大作中提到: 】
: XOR?
: n=



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 67.]

 
deepthroat
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: deepthroat (The wind is rising. We must try to live), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 14:11:41 2015, 美东)

不能,因为我也没做。


【 在 frederickyl (frederickyl) 的大作中提到: 】
: 能详细说说吗?

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 172.]

 
zyzyis
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: zyzyis (zyzyis), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 14:24:19 2015, 美东)

lc原题
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 143.]

 
frederickyl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: frederickyl (frederickyl), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 15:07:22 2015, 美东)

哪个题目?我觉得不一样,如果有错误,请指正。
【 在 zyzyis (zyzyis) 的大作中提到: 】
: lc原题



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 128.]

 
laohuangniu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: laohuangniu (老黄牛), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 16:02:40 2015, 美东)

"不能改变原来数组",找到以后改回去,可以吗? :)
【 在 frederickyl (frederickyl) 的大作中提到: 】
: 有个大小为n+1的数组,数组中的每个元素是[1,n],所以至少有两个是重复的。例如
n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1],要求找出重复的那个数字。复杂度要求:空
: 间O(1), 时间复杂度:小于O(n^2)。不能改变原来数组。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 147.]

 
btfath
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: btfath (btfd), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 16:07:11 2015, 美东)

sum up, then you will get it


【 在 frederickyl (frederickyl) 的大作中提到: 】
: 有个大小为n+1的数组,数组中的每个元素是[1,n],所以至少有两个是重复的。例如
n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1],要求找出重复的那个数字。复杂度要求:空
: 间O(1), 时间复杂度:小于O(n^2)。不能改变原来数组。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 192.]

 
deepthroat
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: deepthroat (The wind is rising. We must try to live), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 16:15:24 2015, 美东)

靠,考过这么多遍的我竟然都忘了。


【 在 btfath (btfd) 的大作中提到: 】
: sum up, then you will get it
: n=

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 172.]

 
frederickyl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: frederickyl (frederickyl), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 18:00:32 2015, 美东)

不行
【 在 laohuangniu (老黄牛) 的大作中提到: 】
: "不能改变原来数组",找到以后改回去,可以吗? :)
: n=



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 128.]

 
frederickyl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: frederickyl (frederickyl), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 18:01:59 2015, 美东)

看清题目再回答,还有楼下的那位。。。如果数组全是1,1,1,1,1,sum up 有啥用?
【 在 btfath (btfd) 的大作中提到: 】
: sum up, then you will get it
: n=



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 128.]

 
jmty0083
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: jmty0083 (), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 18:05:24 2015, 美东)

压缩了空间,放宽了时间,感觉一定是divide & conquer,最后答案是O(nlogn)这样。
和xor 或者sum 应该没关系,这俩都是遍历出结果,O(n)时间。
有没有点提示?这个当follow up比较常见吧。

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 128.]

 
backstab
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: backstab (沧海月明), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 18:53:45 2015, 美东)

binary search,
int lowbound = 0, uppbound =n;
int mid = (lowbound + uppbound) / 2;
int countLowHalf=0, countUpperHalf = 0;
now go through the list and count how many in lower half, how many in
upperhalf, and update the low/upper bound to the part which has count > n/2.
since each time we reduce the range by 2, so need longn steps to get to the
bottom, and each step need to loop through the whole array, so it's nlogn.
not sure if there is O(n) algorithm.



【 在 frederickyl (frederickyl) 的大作中提到: 】
: 有个大小为n+1的数组,数组中的每个元素是[1,n],所以至少有两个是重复的。例如
n=
: 4, 数组为[2,3,4,1,1]或者[2,3,1,1,1],要求找出重复的那个数字。复杂度要求:空
: 间O(1), 时间复杂度:小于O(n^2)。不能改变原来数组。
: 请各位看清题目再回复,和LC的题目不一样。



--
如果有来生,要做一棵树;
站成永恒,没有悲欢的姿势。
一半在土里安详,一半在风里飞扬,
一半洒落阴凉,一半沐浴阳光。
非常沉默,非常骄傲,    
从不依靠,从不寻找

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 108.]

 
noregrets
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: noregrets (风满袖), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 19:27:21 2015, 美东)

排序, 然后一个一个比较不就完了, 这题考个Bird?


--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
backstab
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: backstab (沧海月明), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 19:29:15 2015, 美东)

cannot change the content of array, and O(1) space.
【 在 noregrets (风满袖) 的大作中提到: 】
: 排序, 然后一个一个比较不就完了, 这题考个Bird?



--
如果有来生,要做一棵树;
站成永恒,没有悲欢的姿势。
一半在土里安详,一半在风里飞扬,
一半洒落阴凉,一半沐浴阳光。
非常沉默,非常骄傲,    
从不依靠,从不寻找

※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 108.]

 
noregrets
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: noregrets (风满袖), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Tue Sep 22 19:41:40 2015, 美东)

那就只能二分把N方降下来, 不过这纯属扯淡, 现在都什么年代还考怎么套牛拉车。

【 在 backstab (沧海月明) 的大作中提到: 】
: cannot change the content of array, and O(1) space.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
btfath
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: btfath (btfd), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Wed Sep 23 00:00:56 2015, 美东)

没看清题,很简单,还是sum up, 先取<=n/2的,如果都出现且一次那么和是定值,那
么重复的一定是在>n/2中。每次遍历数组n, 遍历log n。复杂度nlogn


【 在 frederickyl (frederickyl) 的大作中提到: 】
: 看清题目再回答,还有楼下的那位。。。如果数组全是1,1,1,1,1,sum up 有啥用?

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
xunhuan19
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: xunhuan19 (Xun Huan), 信区: JobHunting
标  题: Re: 求问Jane Street一道面试题
发信站: BBS 未名空间站 (Wed Sep 23 08:12:04 2015, 美东)

radix sort

加和也可以
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 107.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996