一亩三分地论坛

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

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

bloomberg的On Campus面经

[复制链接] |试试Instant~ |关注本帖
starwve 发表于 2015-2-25 01:11:10 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Bloomberg - 网上海投 - 校园招聘会 |Other

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

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

x
校面
两位白人男士,其中一位是物理PHD学历。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

3题:. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
1. 谈话闲聊题:说说Git和SVN的区别。

2. Two Sum, 但不是要找和为Target的数组中的两数,而是要找和最接近Target的数组中的两数。

3. Anagram,要找英语词语中的所有Anagram,比如我有Cat和Act, 那么我要找这类Anagram的时候,我就要一下得到所有的。
要用HashMap. 考点:如何写Hash Function。-google 1point3acres

题3没复习好,如何写Hash Function,短路了。
Anyway,继续刷题,转战下一家公司啦。

希望上述题对同仁有点帮助。. visit 1point3acres.com for more.
 楼主| starwve 发表于 2015-2-25 05:22:39 | 显示全部楼层
今日的第三题是LeetCode上第49题Anagram,但他们希望得到的解法是用Prime Number来构造的Hash Function. http://blog.csdn.net/lanxu_yy/article/details/17374967有解法。
回复 支持 反对

使用道具 举报

angle22 发表于 2015-2-25 05:33:56 | 显示全部楼层
多谢面经,不过还是不太明白,你说的hash function是说怎么用hashmap吗,还是要写hash function产生hash code。。

多谢指点。
第一道题请问怎么做的,还是用hashmap做吗?
回复 支持 反对

使用道具 举报

angle22 发表于 2015-2-25 05:40:47 | 显示全部楼层
哦,看到第二题的解法了,是很巧妙,谢谢楼主!
第一道题楼主怎么做的?
回复 支持 反对

使用道具 举报

 楼主| starwve 发表于 2015-2-25 05:53:00 | 显示全部楼层
回答楼上:
#1 写hash function产生hash code。 For the following, correct me if I am wrong.
具体来讲, ABC 和 CBA 是一对 Anagram,他们的 HashCode 应当相同。假若我们把26个字母中的每个字母都用一个特定的质数来对应,然后每个单词的Hashcode都可写为他的每个字母对应的质数的乘积。如此, ABC= 2x3x5=30, CBA = 5x3x2=30, 推出 ABC和CBA为Anagram。 我的败笔在于以为找Hashcode一定要用到%运算,实则不必。

面完后,面试官建议我回去看看 http://en.wikipedia.org/wiki/Prime_number_theorem

#2 跟Leetcode的TwoSum很像,只是你可以加个临时变量找最接近Target的两数与Target的差;这个差最小的那个两数的下标索引即为所求。
回复 支持 反对

使用道具 举报

lubor 发表于 2015-2-25 06:42:13 | 显示全部楼层
starwve 发表于 2015-2-25 05:53. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
回答楼上:
#1 写hash function产生hash code。 For the following, correct me if I am wrong.
具体来 ...

Two sum 这个lz能再给个更详细的思路么,我catch 不到point啊。。谢谢~
回复 支持 反对

使用道具 举报

lubor 发表于 2015-2-25 08:36:17 | 显示全部楼层
starwve 发表于 2015-2-25 05:22. more info on 1point3acres.com
今日的第三题是LeetCode上第49题Anagram,但他们希望得到的解法是用Prime Number来构造的Hash Function. ht ...
. From 1point 3acres bbs
链接里的这个解法会很容易出现integer overflow吧?
回复 支持 反对

使用道具 举报

 楼主| starwve 发表于 2015-2-25 09:51:20 | 显示全部楼层
lubor 发表于 2015-2-25 08:36
链接里的这个解法会很容易出现integer overflow吧?

对,比如英语单词 zyzzyva, 这个方法将是灾难。但今天考官的考点在于 如何构造 那些单词的Key,要用到质数,答案就是简单的 质数连乘造Key,然后Hash Function也是简单的 H(Key) = Key  直接地址法。
回复 支持 反对

使用道具 举报

 楼主| starwve 发表于 2015-2-25 11:36:21 | 显示全部楼层
lubor 发表于 2015-2-25 06:42
Two sum 这个lz能再给个更详细的思路么,我catch 不到point啊。。谢谢~
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
直接给你答案吧,刚写好,你可再用别的Test Case测测:https://github.com/starwavelin/A ... losestToTarget.java
回复 支持 反对

使用道具 举报

lubor 发表于 2015-2-25 12:11:53 | 显示全部楼层
starwve 发表于 2015-2-25 11:36
直接给你答案吧,刚写好,你可再用别的Test Case测测:https://github.com/starwavelin/AlgorithmPractic ...

lz好人,好人必拿好OFFER!

刚看了你的code,我之前没理解你的思路因为以为给的不是sorted的数组,还在想有其他的思路做呢~
回复 支持 反对

使用道具 举报

猴子0523 发表于 2015-3-4 04:49:13 | 显示全部楼层
starwve 发表于 2015-2-25 11:36
直接给你答案吧,刚写好,你可再用别的Test Case测测:https://github.com/starwavelin/AlgorithmPractic ...

楼主代码风格好清晰,一看就训练有素。。不过我用下面这个test case试好像过不去。 {2,7,8,10} 14
. 1point 3acres 璁哄潧返回的index 是 0,3。 但是最接近的应该是1,2
回复 支持 反对

使用道具 举报

 楼主| starwve 发表于 2015-3-4 09:22:09 | 显示全部楼层
猴子0523 发表于 2015-3-4 04:49
楼主代码风格好清晰,一看就训练有素。。不过我用下面这个test case试好像过不去。 {2,7,8,10} 14
返 ...
. 鍥磋鎴戜滑@1point 3 acres
您是对的。多谢您指出问题,我先记录下来了,有空改改。
回复 支持 反对

使用道具 举报

 楼主| starwve 发表于 2015-3-4 11:11:56 | 显示全部楼层
猴子0523 发表于 2015-3-4 04:49
楼主代码风格好清晰,一看就训练有素。。不过我用下面这个test case试好像过不去。 {2,7,8,10} 14
返 ...

我之前的算法是这样的。当数组中的两数之和与 Target Number 的差值大于了原有的差值时,回退移动了的指针并Return。举你的例子来说, 初始指针指向头 (数字2) 和尾 (数字10),它们与Target Number 14的差值的绝对值为2。 利用有序数组的特性,夹逼准则,由于 2 + 10 本身小于目标值 14, 向右移动start指针,到了数字7。OK,7 + 10 - 14 = 3, 大于了原有的差值2, 回退start指针,并输出,所以就得到 0 和 3 了。 您也许会问,假如当start指针到了数字7时,我们不回退start, 而是让end--, 会如何? 假如target  Number 为14, 这么做就对了。但是,如果把Target Number换成13, 这么做得到的结果仍旧是index 1 和2, 就不对了,这时的正确结果反倒是index 0 和 3了。   .鏈枃鍘熷垱鑷1point3acres璁哄潧
对于Given a sorted integer, TwoSum求 最接近 Target的两数,我还没有想到O(nlogn)的解法,Stuck在最接近而非等于Target这个问题上了(这问题有O(nlogn)的解法吗?欢迎同仁赐教)。 我就把自己的代码改成了O(n^2)的,先保证正确性了。  各位同仁面试时,先保住正确性,然后再求更好方法哦。
回复 支持 反对

使用道具 举报

猴子0523 发表于 2015-3-4 11:49:11 | 显示全部楼层
starwve 发表于 2015-3-4 11:11
我之前的算法是这样的。当数组中的两数之和与 Target Number 的差值大于了原有的差值时,回退移动了的指 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可不可以这样。依旧先排序。然后用头尾两个指针夹逼,不过务必走到两个指针相遇为止,过程中遇到的所有差值及其组合都记录在hashmap里面,最后找到hashmap里储存的最小差值对应的组合就是要找的组合。
. 1point 3acres 璁哄潧
排序是nlgn,夹逼是n,搜索hashmap也是n。

补充内容 (2015-3-4 12:13):
或者夹逼的时候维护一个最小差值和一个int[2]记录此差值对应两个指针位置
回复 支持 反对

使用道具 举报

 楼主| starwve 发表于 2015-3-12 04:02:30 | 显示全部楼层
猴子0523 发表于 2015-3-4 11:49
可不可以这样。依旧先排序。然后用头尾两个指针夹逼,不过务必走到两个指针相遇为止,过程中遇到的所有差 ...

. from: 1point3acres.com/bbs 对的,夹逼的时候维护差值最小值及其相应的两指针位置即可。代码已更新(https://github.com/starwavelin/A ... sestToTargetII.java
,相信正确了。
非常谢谢你的反馈!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 18:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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