一亩三分地论坛

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

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

Bloomberg onsite

[复制链接] |试试Instant~ |关注本帖
pro 发表于 2014-10-29 03:35:46 | 显示全部楼层 |阅读模式

2014(10-12月) 码农类 硕士 全职@Bloomberg - 校园招聘会 - Onsite |Fail

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

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

x
面了两轮就被淘汰了……不过我碰到的面试官都是美国人. 鍥磋鎴戜滑@1point 3 acres

第一轮:
1:算fibonacci数列。给项数,返回那一项的数字。
我一开始直接写了个无脑递归的,准备写完再优化,但是被拦住了。先问无脑递归版本会有什么问题。我说时间和空间都有问题。然后问你觉得是时间的问题比较严重还是空间的问题比较严重?给了个例子比如求第100k项。我说时间上的问题严重。空间上可能会stack overflow吧。然后跟我逐步确认了一下空间上的开销,具体到每次调用要往栈上压多少内容,栈最高会有多高,我才发现空间问题没那么严重_(:з」∠)_
2:Best time to buy and sell stock I。

第二轮:
有一些behavior,问why bloomberg之类的。另外针对简历还问了职业规划,有没有open source project的contribution。我说木有
1:有一堆上古时期的legacy code(written in C),发现在生产环境下经常会crash。让我来fix。要怎么做?
我:看看log啊看看document啊根据log定位一下出问题的地方。
他:嗯。但是document非常多,你没时间看这么多document。log一切正常,就是打印了某一行正常的log之后就crash了。. 鍥磋鎴戜滑@1point 3 acres
我:那我看看core dump。
他:好的。那我看了core dump,发现是个segment fault。怎么办?
我:可以用一些static/dynamic analysis tools看看哪里有illegal memory access(比如valgrind)。
另外一个面试官:你用过valgrind吗?我说曾经有个project用过。
他:那我现在找到有一段代码,大概长这样:
int i = 0;
int a[10];
/** some other code, including some function calls **/
a = 0;. From 1point 3acres bbs
crash在a这一行。你怎么看?
我:检查中间的其他代码有没有修改a或者i为非法的值。
他:都没有。
我:再看看中间那些function,如果有参数为a或者i的,看那些function有没有非法修改a或者i。
他:都没有。哦我刚才忘记说了。我在a之前检查了一下i,发现是个0xabcdef什么的值。
我:(卡壳)
他:我给你个提示。我发现如果我把第一行改成 static int i = 0; 程序就不crash了。
我:嗯……那说明有其他线程污染了i……
他:你想想static和没有static的区别是什么?
我:有static,i在单独的data segment里。没有的话i就在stack上。
他:然后呢?
我:调用其他函数的时候stack被污染了!. Waral 鍗氬鏈夋洿澶氭枃绔,
他:(点头)
这应该不是他想要的答案吧……求问各位怎么看
2:给两个函数,DB* openDB(const char* name); int closeDB(DB* db); 针对成功的操作和失败的操作都有不同的返回值。写一个c++类把这俩封装起来,让我在这个程序里可以随便调用。
我写了个singleton。大概就是 http://stackoverflow.com/questio ... eton-design-pattern 这样的,另外加了一个destory()来close资源。
他问了我里面的几个static的意义。然后说我这里DB返回的是指针,你要返回的却是引用。这都不能编译啊怎么破?
我说把返回的指针dereference,然后存起来。调用getInstance的时候返回引用。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
他说这样可以编译。但我跑的时候发现这里会crash,为什么?It's all right if you don't know that。
我这个assignment可能是一个shallow copy,里面有pointer的话就可能会有指针管理上的问题。
他表示这不是他想要的答案……
. From 1point 3acres bbs
然后就被带到另外一个会议室等结果。结果就是收拾东西回家

.1point3acres缃
补充内容 (2014-10-29 03:46):. 1point 3acres 璁哄潧
第二轮少写了一题……第三题是给一个矩阵,从中间开始旋转着一圈一圈把值打印出来。代码写完之后还追问了一下如果要允许用户自定义螺旋的方向要怎么改。
. 1point 3acres 璁哄潧
补充内容 (2014-10-29 04:18):. visit 1point3acres.com for more.
代码找错那题a = 0应该是a「i」=0……方括号i被当成ubb吞掉了_(:з」∠)_

评分

5

查看全部评分

qiaokan 发表于 2014-10-29 10:53:28 | 显示全部楼层
最后一题可能是 threading的问题。
其他的thread可能已经删除了这个object
所以应该实现一个类似OpenPinned
回复 支持 1 反对 0

使用道具 举报

ohmystill 发表于 2014-10-29 03:45:04 | 显示全部楼层
BB是 真心很难
回复 支持 反对

使用道具 举报

ohmystill 发表于 2014-10-29 03:45:14 | 显示全部楼层
BB是 真心很难
回复 支持 反对

使用道具 举报

22691482 发表于 2014-10-29 05:38:03 | 显示全部楼层
"你要返回的却是引用。这都不能编译啊怎么破?"

我当时也被问到了这一句。 请问楼主面试官是不是一个国人?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-29 10:34:18 | 显示全部楼层
是a[i]=0吗?最后一行?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-29 10:51:42 | 显示全部楼层
每个线程有自己独立的栈啊
不会互相影响吧。我觉得不太可能是这个原因。
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-10-29 11:48:00 | 显示全部楼层
qiaokan 发表于 2014-10-29 10:51. Waral 鍗氬鏈夋洿澶氭枃绔,
每个线程有自己独立的栈啊
不会互相影响吧。我觉得不太可能是这个原因。

我想的是可能其他函数里面通过buffer overflow的形式把栈污染掉了……
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-10-29 11:48:12 | 显示全部楼层
22691482 发表于 2014-10-29 05:38. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
"你要返回的却是引用。这都不能编译啊怎么破?"

我当时也被问到了这一句。 请问楼主面试官是不是一个国 ...

不是。一个大胡子美国人。
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-10-29 11:49:18 | 显示全部楼层
qiaokan 发表于 2014-10-29 10:53. visit 1point3acres.com for more.
最后一题可能是 threading的问题。
其他的thread可能已经删除了这个object
所以应该实现一个类似OpenPinn ...

我的destroy倒是会先判断一下是不是NULL才执行close……不过你这么一说的话似乎从判断null到close之间加个锁就好了?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-29 23:21:18 | 显示全部楼层
pro 发表于 2014-10-29 11:48
我想的是可能其他函数里面通过buffer overflow的形式把栈污染掉了……
. 1point 3acres 璁哄潧
不会的。如果访问出了别的函数自己的栈的空间,在当时那个位置就segment fault了。
所以只可能是自己函数里有overflow。
自己函数overflow了那个i的值。

static的话,就不可能被别人改了。因为如果有人去访问static的那块内存,在那句话就会seg fault
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-29 23:22:48 | 显示全部楼层
pro 发表于 2014-10-29 11:49
我的destroy倒是会先判断一下是不是NULL才执行close……不过你这么一说的话似乎从判断null到close之间加 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
恩。可能还需要shared pointer。这个问题扩展的点很多的。
内存管理估计是他想考察的点。
这个问题跟设计一个LRU是一样的。

补充内容 (2014-10-29 23:23):
准确的说是,如何设计一个cache API , 使得用户使用最方便?有很多设计的点可以讨论。
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-10-30 02:11:12 | 显示全部楼层
qiaokan 发表于 2014-10-29 23:21
不会的。如果访问出了别的函数自己的栈的空间,在当时那个位置就segment fault了。
所以只可能是自己函 ...

segfault只有访问了整个进程的内存空间以外的地址的时候才会触发吧……overflow只要没有写到整个进程的stack外面去应该是不会触发segfault的。static的情况我认为应该只是data segment比较远,现有的overflow问题没有盖到ds上。如果真的把ds盖掉了,那也应该就是盖掉了,不会有segfault的提醒的。
回复 支持 反对

使用道具 举报

hebanny 发表于 2014-10-30 02:33:47 | 显示全部楼层
lz难道是我昨天遇到的c大的ece的
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-10-30 09:56:26 | 显示全部楼层
hebanny 发表于 2014-10-30 02:33
lz难道是我昨天遇到的c大的ece的

应该……是的……你是昨天一早的飞机去nyc的那位?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-30 11:02:01 | 显示全部楼层
pro 发表于 2014-10-30 02:11.鏈枃鍘熷垱鑷1point3acres璁哄潧
segfault只有访问了整个进程的内存空间以外的地址的时候才会触发吧……overflow只要没有写到整个进程的st ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
你是说线程吧?
.鐣欏璁哄潧-涓浜-涓夊垎鍦进程更不可能的。
每个 线程都有自己的独立的栈。只要出了这个栈,都是segfault
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2014-10-30 11:05):
static没事,是因为如果是 触碰到static,肯定出了自己的stack,在当时那句就会segfault,不会在最后一句才segfault
回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-10-30 11:08:03 | 显示全部楼层
qiaokan 发表于 2014-10-30 11:02
你是说线程吧?
进程更不可能的。
每个 线程都有自己的独立的栈。只要出了这个栈,都是segfault

呃我现在就暂时只考虑单线程的情况。
你说的出了栈是指,1)某函数操作的内存地址超出了栈上从它的return address、parameter那里开始的界限,还是2)某函数操作的内存地址超出了这个程序的内存空间的stack段,还是3)操作的内存地址超出了这个程序的内存空间?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-30 11:15:53 | 显示全部楼层
pro 发表于 2014-10-30 11:08
呃我现在就暂时只考虑单线程的情况。
你说的出了栈是指,1)某函数操作的内存地址超出了栈上从它的retur ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我的意思是,这个问题没你想那么复杂。
原因就是在 这个函数里。某个地方
比如 你定义其他的一个int B[10]
然后你修改了B[10]
然后B[10]恰好是i的地址。

这个不可能是中间调用别的函数修改的,除非那个函数直接或者间接传入了i的地址。
别的函数无法直接overflow到i的地址的,如果那个发生的话,程序会那个函数调用里就会segfault。因为你说的(2)这个原因。而题目的假设是,segfault发生在最后一行。

如果是static,也是一样的道理。

回复 支持 反对

使用道具 举报

 楼主| pro 发表于 2014-10-30 11:41:17 | 显示全部楼层
qiaokan 发表于 2014-10-30 11:15
我的意思是,这个问题没你想那么复杂。
原因就是在 这个函数里。某个地方
比如 你定义其他的一个int B[ ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
原来如此……我之前都一直在想比如用gets()实现的buffer overflow这种。因为我记得以前在自己的机器上实验的时候gets()里放很长的内容就可以把stack上的很多东西都盖掉……远不止这个函数自己的那一段stack。
我对segfault的理解是1)访问了mmu压根就没map过来的地址空间,2)权限不对,比如往text段写内容。

你说的不能超出函数自己这一段栈的这个特性,是现在的OS已经默认提供的保护措施,还是通过静态/动态分析得到的结果?
回复 支持 反对

使用道具 举报

qiaokan 发表于 2014-10-30 12:14:03 | 显示全部楼层
pro 发表于 2014-10-30 11:41
原来如此……我之前都一直在想比如用gets()实现的buffer overflow这种。因为我记得以前在自己的机器上实 ...

比方你在函数里定义一个大数组,肯定会segfault的,因为你超过的栈的空间。
segfault是os保护的,就是告诉程序,这个位置不属于你。. From 1point 3acres bbs

我倒是觉得下面一题更有意思,有很多可以问和扩展的点。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 15:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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