一亩三分地论坛

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

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

Bloomberg 10/18 onsite面经

[复制链接] |试试Instant~ |关注本帖
abcd1992719g 发表于 2016-10-20 02:50:29 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@Bloomberg - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
总共面了4轮, 每轮都在不同的楼层. 几乎走遍了20-29的每一层......

第一轮, 是两个人. 先问了two linked list相加, 一道比较经典的题. 撸主就用最普通的方法, reverse, 相加, 再reverse; 然后问了max points in a line, 也是leetcode原题. https://github.com/gzc/leetcode/ ... 20on%20a%20Line.cpp        两题都在纸上写了代码. 写了好多好多页, 然后居然没有橡皮......

第二轮, 是一个伯克利的math专业的小哥. 问的第一个问题类似 https://leetcode.com/problems/find-the-duplicate-number/     不过duplicate number 可能不止一个, 比如可能 [1,1,2,2,2]. 他问了好多好多关于这个题目. 首先分了两大类, 数组immuted和muted. 然后针对每一类,都给出O(n^2, nlogn, n)的, 空间也要慢慢优化. 最后muted他要我给出O(n) time, O(0) space, immuted给出O(n), O(1) space. 关于muted的O(0) space, 我告诉他swap可以用O(0) 不需要临时变量. CMU的同学肯定都知道, 在CSAPP这本书里, 给出了bit manipulation swap不需要temporary variable. 我告诉他我大一就学了那本书, 哗啦啦把那三行代码写了出来, 他很满意. 关于immuted的最优解, 就是类似 circle list, 快指针慢指针跑来跑去,很经典的. 他让我证明为什么这种方法最后得到的就是intersection, 我也用数学给了他证明.
然后第二题是一个2d-grid, 每一个都是 >=0的int, 表示有多少苹果. 起点在左上角, 终点在右下角. 起点到终点只能向右或者下, 终点到起点只能向左或者上. 问 : 从起点到终点再回来, 最多能拿多少苹果. 一个格子内的苹果被拿掉就没了. 我没有给出最优解, 时间很少了 - - 问了他他的想法. 他也告诉我了. 听起来很有道理. 但撸主我这时候在想其他事情没听进去 = =

第三轮, 是一个HR, 就问很多乱七八糟的问题 = =

第四轮, 是一个senior印度人,在bb 呆了 12年. 问了我分布式设计题. 有一个distributed dispatch server. 还有很多sub-server, such as chat server/add server/store server. 然后要怎么设计. 我就扯淡了... message queue/lock/rpc/load balancing/......乱讲一通。他也蛮满意的感觉 = =. 1point 3acres 璁哄潧

共勉!求star球follow  https://github.com/gzc




补充内容 (2016-10-20 06:07):
muted就是可以改变数组元素,immuted相当是加了const, 不能改变

评分

3

查看全部评分

zzgzzm 发表于 2016-10-20 03:09:21 | 显示全部楼层
Lz 可以具体说一下第二题的内容吗?是说定一个数组找重复元素?感觉这一题问很多基础知识,若是非cs 背景的就很吃力啊
回复 支持 反对

使用道具 举报

洋葱a 发表于 2016-10-20 04:02:25 | 显示全部楼层
请问immuted 和 muted 指的是给一个数列然后实时改变里面的数字,然后o(1)时间给出重复的数字?没看懂muted的变的是哪里啊。。
求问找苹果的那个咋做。。我只能想到brute force
回复 支持 反对

使用道具 举报

fangwei007 发表于 2016-10-20 05:12:48 | 显示全部楼层
数组immuted和muted ,是什么意思呢题主?谢谢
回复 支持 反对

使用道具 举报

小飞侠我去 发表于 2016-10-20 08:52:23 | 显示全部楼层
求问楼主苹果那题,小哥什么想法?
回复 支持 反对

使用道具 举报

382851453 发表于 2016-10-20 09:54:14 | 显示全部楼层
请问楼主onsite大家都是穿西服去吗
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-20 10:38:10 | 显示全部楼层
关于“第二题是拿苹果”:我的想法是用dp(i,j) = grid(i,j) + max(dp(i-1,j), dp(i,j-1))来计算在坐标(i,j)可以拿的最多苹果总数,同时记录previous坐标prev(i,j)。到达右下时back track走过的路径将拿掉的苹果减去,然后再走回来(走回来就不用track路径了)。
PS:我觉得可以先证明最优往返路径在除了起点和右下转折点外不可能有交点的。因为若有的话那么交点将路径就分成了几个段,而在交点处将其中一条L型detour一下就可以拿更多的苹果
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-21 06:07:43 | 显示全部楼层
382851453 发表于 2016-10-20 09:54
请问楼主onsite大家都是穿西服去吗

撸主我就是T恤男
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-21 06:13:08 | 显示全部楼层
382851453 发表于 2016-10-20 09:54
请问楼主onsite大家都是穿西服去吗

我是唯一一个T恤...
回复 支持 反对

使用道具 举报

fangwei007 发表于 2016-10-22 05:01:28 | 显示全部楼层
题主发的find duplicate这个题真的很棒,能不能给讲讲具体思路,多个解究竟该怎么处理?多谢了,题主大神 ^^
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-23 03:09:57 | 显示全部楼层
楼主有消息了吗~
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-23 03:10:28 | 显示全部楼层
abcd1992719g 发表于 2016-10-21 06:13
我是唯一一个T恤...

我也是T恤啊。。哈哈 楼主我是加你微信的那个男生! 你有消息了吗
回复 支持 反对

使用道具 举报

 楼主| abcd1992719g 发表于 2016-10-23 07:34:46 | 显示全部楼层
小A要当码农 发表于 2016-10-23 03:10
我也是T恤啊。。哈哈 楼主我是加你微信的那个男生! 你有消息了吗

跪的不明不白
回复 支持 反对

使用道具 举报

小A要当码农 发表于 2016-10-23 10:00:11 | 显示全部楼层

摸摸。。我还没有任何消息。。。。感觉默剧了
回复 支持 反对

使用道具 举报

Nakanu 发表于 2016-10-24 02:28:05 | 显示全部楼层
zzgzzm 发表于 2016-10-20 10:38
关于“第二题是拿苹果”:我的想法是用dp(i,j) = grid(i,j) + max(dp(i-1,j), dp(i,j-1))来计算在坐标(i,j) ...

这个问题没那么简单,L型detour只是其中一种情况,可以举出反例的。

我觉得有这么几个限制条件:
1. 两条路径不相交。
2. 两条路径必然共享dp求单程解最优路径上的所有点。(可能有一部分两条路靠的很近,然后出现一条路绕行的情况,也可能在什么地方就完全分开了)
3. 两条路径必然一个从起点和终点的一侧出,另一侧进。
有点greedy的思路在里面,理论上也能数学证明。
然后算法的话,我想的是backtracking,一步一步看,因为每一步都要满足以上条件和左上右下的条件,根据constraint修剪树。理论复杂度是exp,但实际运算肯定远小于这个。
回复 支持 反对

使用道具 举报

wcsoswto 发表于 2016-10-24 02:49:31 | 显示全部楼层
求问楼主什么时候投的?等了多长时间?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-24 02:49:59 | 显示全部楼层
Nakanu 发表于 2016-10-24 02:28
这个问题没那么简单,L型detour只是其中一种情况,可以举出反例的。
.鐣欏璁哄潧-涓浜-涓夊垎鍦
我觉得有这么几个限制条件:

感谢分析。其实我就是不确定这个往返的最优解能不能证明就是两个单程的DP最优解(?),也就是说用greedy对不对?能不能具体说一下backtracking?谢谢
回复 支持 反对

使用道具 举报

Nakanu 发表于 2016-10-24 04:41:57 | 显示全部楼层
zzgzzm 发表于 2016-10-24 02:49. visit 1point3acres.com for more.
感谢分析。其实我就是不确定这个往返的最优解能不能证明就是两个单程的DP最优解(?),也就是说用greedy ...
. more info on 1point3acres.com
来回dp求2次最优的反例:
2 2 2 0. 1point3acres.com/bbs
0 6 3 0
0 6 6 2
0 4 4 1
第一次dp会挑选右下角左上的6作为路径点,但其实应该挑选[3,1]的4作为路径点。. From 1point 3acres bbs
backtracking其实就是搜索树,从起点开始一格一格找。利用前面的限制条件修剪搜索树。
我暂时没想到更加好的方法
回复 支持 反对

使用道具 举报

382851453 发表于 2016-10-24 23:31:36 | 显示全部楼层
abcd1992719g 发表于 2016-10-21 06:13
我是唯一一个T恤...

同情楼主
回复 支持 反对

使用道具 举报

BRYCEMENG 发表于 2016-10-25 01:01:24 | 显示全部楼层
小A要当码农 发表于 2016-10-23 10:00
摸摸。。我还没有任何消息。。。。感觉默剧了

哈喽,你也是onsite4轮吗,现在怎么样了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 10:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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