西媒太他妈牛逼了Tibet crisis might have driven hikers to Ne (转载) - 未名空间MITBBS历史存档

西媒太他妈牛逼了Tibet crisis might have driven hikers to Ne (转载)# Joke - 肚皮舞运动

c*i2012-09-25 07:09

1 楼

刚结束了bb家的面试，攒RP报个面筋。之前邮件里说是2个SDE面我，就一轮，实际去了
发现是有三个
SDE面，都是非CS专业三哥。总共一个小时，寒暄了20分钟的之前做过的project，简单
问了一些基本的coding知识，然后做了2个题，2个题都没做好，估计是肯定杯具了。之
前低估了bb家面试的难度，准备的太欠缺了，在这给大家提个醒一定要准备充分。第一
个题是写个函数输出所有的满足前三位和等于后三位和的六位数，比如156723，我写了
个bruteforce的，被要求优化，想了下说可以利用对称性减一些运算量，但是要考虑有
padding zero的情况，后来时间不多了也就不了了之了，面试官说其实是可以推出个公
式的，晕。第二个题是给一个8*8的board，其中有两个点被block了不能放东西，现在
给定这两个店的坐标，写个程序检测可否用domino pizza来覆盖这个board，其中每个
格子只能被覆盖一次，被block的不能覆盖，domino pizza就是1*2或者2*1的格子，开
始想和能不能往DP上靠，发现走不通，于是有点慌，经提示说把二维board转成一维，
说了一点尝试性的做法，但最终还是时间到了没做出来，这个题总共给了10分钟。最后
问了一个2sum，这个比较简单，讲了一下思路。就这一轮面试，面完了和HR寒暄了几句
，HR问有没有啥要问他的问题，然后说下周给结果，因为最近是holiday所以要等，估
计是杯具了，求RP求momo

c*k2012-09-25 07:09

2 楼

【以下文字转载自 Military 讨论区】
发信人: meiguohuaren (唐骏博士), 信区: Military
标题: 西媒太他妈牛逼了Tibet crisis might have driven hikers to Nepal mountain hit by deadly avalanche
发信站: BBS 未名空间站 (Tue Sep 25 12:02:56 2012, 美东)
http://news.yahoo.com/tibet-crisis-might-driven-hikers-nepal-mo
China rejected climbing permits for mountaineers hoping to scale peaks in
the Tibetan Himalayas, forcing many to crowd onto mountains in Nepal,
according to alpine companies.
Relations between Tibet and the Chinese government have been volatile this
year, as many Tibetans set themselves on fire to bring attention to what
they say is their suffering under China's repressive policies. China claims
Tibet has always been Chinese territory, but most Tibetans say the Himalayan
region was independent for much of its history.

d*x2012-09-25 07:09

3 楼

你的第一直觉是对的，第二道题是典型的dp

【在 c**i 的大作中提到】

: 刚结束了bb家的面试，攒RP报个面筋。之前邮件里说是2个SDE面我，就一轮，实际去了
: 发现是有三个
: SDE面，都是非CS专业三哥。总共一个小时，寒暄了20分钟的之前做过的project，简单
: 问了一些基本的coding知识，然后做了2个题，2个题都没做好，估计是肯定杯具了。之
: 前低估了bb家面试的难度，准备的太欠缺了，在这给大家提个醒一定要准备充分。第一
: 个题是写个函数输出所有的满足前三位和等于后三位和的六位数，比如156723，我写了
: 个bruteforce的，被要求优化，想了下说可以利用对称性减一些运算量，但是要考虑有
: padding zero的情况，后来时间不多了也就不了了之了，面试官说其实是可以推出个公
: 式的，晕。第二个题是给一个8*8的board，其中有两个点被block了不能放东西，现在
: 给定这两个店的坐标，写个程序检测可否用domino pizza来覆盖这个board，其中每个

b*u2012-09-25 07:09

4 楼

要理解，正在造船。

mountain hit by deadly avalanche
claims

【在 c******k 的大作中提到】

: 【以下文字转载自 Military 讨论区】
: 发信人: meiguohuaren (唐骏博士), 信区: Military
: 标题: 西媒太他妈牛逼了Tibet crisis might have driven hikers to Nepal mountain hit by deadly avalanche
: 发信站: BBS 未名空间站 (Tue Sep 25 12:02:56 2012, 美东)
: http://news.yahoo.com/tibet-crisis-might-driven-hikers-nepal-mo
: China rejected climbing permits for mountaineers hoping to scale peaks in
: the Tibetan Himalayas, forcing many to crowd onto mountains in Nepal,
: according to alpine companies.
: Relations between Tibet and the Chinese government have been volatile this
: year, as many Tibetans set themselves on fire to bring attention to what

l*b2012-09-25 07:09

5 楼

第一题前几天有个google的面试也被问过，不过是4位数字，第2题CC150上面有类似的
？BTW，什么是Domino Pizza？

d*x2012-09-25 07:09

6 楼

求贴150上类似题目
没印象了啊

【在 l**b 的大作中提到】

: 第一题前几天有个google的面试也被问过，不过是4位数字，第2题CC150上面有类似的
: ？BTW，什么是Domino Pizza？

d*x2012-09-25 07:09

7 楼

他说了，1*2或者2*1的格子

【在 l**b 的大作中提到】

: 第一题前几天有个google的面试也被问过，不过是4位数字，第2题CC150上面有类似的
: ？BTW，什么是Domino Pizza？

c*i2012-09-25 07:09

8 楼

刚翻了下，应该是brainteaser第2题，不过不太一样，那里是用了黑棋和白棋的数目来
解的，而且被block的两个棋子位置固定。现在这个题是没有黑白棋子之分，而且被
block的棋子位置是参数

【在 d**********x 的大作中提到】

: 求贴150上类似题目
: 没印象了啊

l*b2012-09-25 07:09

9 楼

第二个是dp? 只要一黑一白肯定可以吧

【在 d**********x 的大作中提到】

: 你的第一直觉是对的，第二道题是典型的dp

l*b2012-09-25 07:09

10 楼

可以自己染色呀

【在 c**i 的大作中提到】

:
: 刚翻了下，应该是brainteaser第2题，不过不太一样，那里是用了黑棋和白棋的数目来
: 解的，而且被block的两个棋子位置固定。现在这个题是没有黑白棋子之分，而且被
: block的棋子位置是参数

f*e2012-09-25 07:09

11 楼

第二题好像是黑白染色题,都不用DP。第一题就是用一个vector >，记录
和为m的3位数，然后再排列组合。

【在 d**********x 的大作中提到】

: 你的第一直觉是对的，第二道题是典型的dp

d*x2012-09-25 07:09

12 楼

从上到下，一行一行地填
子状态的描述是：有pizza的最大行数(int a)以及在这一行上的填充状态(bit array b
)，以及到此为止的未填充格子数量(int c)

【在 c**i 的大作中提到】

:
: 刚翻了下，应该是brainteaser第2题，不过不太一样，那里是用了黑棋和白棋的数目来
: 解的，而且被block的两个棋子位置固定。现在这个题是没有黑白棋子之分，而且被
: block的棋子位置是参数

d*x2012-09-25 07:09

13 楼

恩。。开始的时候不知道是1*2...

【在 f*****e 的大作中提到】

: 第二题好像是黑白染色题,都不用DP。第一题就是用一个vector >，记录
: 和为m的3位数，然后再排列组合。

r*62012-09-25 07:09

14 楼

第一题能不能说的详细一点。。

【在 f*****e 的大作中提到】

: 第二题好像是黑白染色题,都不用DP。第一题就是用一个vector >，记录
: 和为m的3位数，然后再排列组合。

d*x2012-09-25 07:09

15 楼

哦，擦，我看错题目了
lz那个题目是要检测能否覆盖
我以为是要求最大覆盖

【在 f*****e 的大作中提到】

: 第二题好像是黑白染色题,都不用DP。第一题就是用一个vector >，记录
: 和为m的3位数，然后再排列组合。

s*l2012-09-25 07:09

16 楼

第一题数字能重复吗？

【在 c**i 的大作中提到】

: 刚结束了bb家的面试，攒RP报个面筋。之前邮件里说是2个SDE面我，就一轮，实际去了
: 发现是有三个
: SDE面，都是非CS专业三哥。总共一个小时，寒暄了20分钟的之前做过的project，简单
: 问了一些基本的coding知识，然后做了2个题，2个题都没做好，估计是肯定杯具了。之
: 前低估了bb家面试的难度，准备的太欠缺了，在这给大家提个醒一定要准备充分。第一
: 个题是写个函数输出所有的满足前三位和等于后三位和的六位数，比如156723，我写了
: 个bruteforce的，被要求优化，想了下说可以利用对称性减一些运算量，但是要考虑有
: padding zero的情况，后来时间不多了也就不了了之了，面试官说其实是可以推出个公
: 式的，晕。第二个题是给一个8*8的board，其中有两个点被block了不能放东西，现在
: 给定这两个店的坐标，写个程序检测可否用domino pizza来覆盖这个board，其中每个

l*a2012-09-25 07:09

17 楼

111111当然满足条件

【在 s********l 的大作中提到】

: 第一题数字能重复吗？

m*s2012-09-25 07:09

18 楼

第二题如果数学不能做的话，用dp可以O(m*n*2^m)搞定，其中m是列数，因为任意一个
格子最多影响到之后的第m个格子

【在 c**i 的大作中提到】

: 刚结束了bb家的面试，攒RP报个面筋。之前邮件里说是2个SDE面我，就一轮，实际去了
: 发现是有三个
: SDE面，都是非CS专业三哥。总共一个小时，寒暄了20分钟的之前做过的project，简单
: 问了一些基本的coding知识，然后做了2个题，2个题都没做好，估计是肯定杯具了。之
: 前低估了bb家面试的难度，准备的太欠缺了，在这给大家提个醒一定要准备充分。第一
: 个题是写个函数输出所有的满足前三位和等于后三位和的六位数，比如156723，我写了
: 个bruteforce的，被要求优化，想了下说可以利用对称性减一些运算量，但是要考虑有
: padding zero的情况，后来时间不多了也就不了了之了，面试官说其实是可以推出个公
: 式的，晕。第二个题是给一个8*8的board，其中有两个点被block了不能放东西，现在
: 给定这两个店的坐标，写个程序检测可否用domino pizza来覆盖这个board，其中每个

s*l2012-09-25 07:09

19 楼

我知道满足条件
所以问问可否重复

【在 l*****a 的大作中提到】

: 111111当然满足条件

c*i2012-09-25 07:09

20 楼

可以的，但是001010这样的是不合法的，不能有leading 0s

【在 s********l 的大作中提到】

: 我知道满足条件
: 所以问问可否重复

c*i2012-09-25 07:09

21 楼

大家能细说下黑白染色解第二题吗？

c*i2012-09-25 07:09

22 楼

我当时说了用个hashtable存sum为某个数的组合个数，但是那样写code很不好写啊，有
更好的办法吗？

【在 f*****e 的大作中提到】

: 第二题好像是黑白染色题,都不用DP。第一题就是用一个vector >，记录
: 和为m的3位数，然后再排列组合。

c*u2012-09-25 07:09

23 楼

bb待遇在NYC很一般吧

s*e2012-09-25 07:09

24 楼

第二题貌似金田一某集中有解……记得是国际象棋染色，如果block的是同色就无法覆
盖，否则可以

l*n2012-09-25 07:09

25 楼

我也去了一日游，同意楼主所说，低估了！考了个bst 第k大，没准备好，挂了

b*n2012-09-25 07:09

26 楼

8x8 board的题就是国际象棋棋盘。如果block的格子是同色的，就无解；如果是一黑一
白，就一定可以覆盖。证明如下：
如果block的是相邻的格子，那是trivial case.
如果不相邻的一黑一白，则可以reduce 成2by3的格子，两个block的黑白cell在对角的
两头，这样用两个dominos也可以轻易覆盖#
bool canCover(int x1,int y1,int x2,int y2) {
return ((x1+y1)&1) ^((x2+y2)&1);
}

【在 c**i 的大作中提到】

: 刚结束了bb家的面试，攒RP报个面筋。之前邮件里说是2个SDE面我，就一轮，实际去了
: 发现是有三个
: SDE面，都是非CS专业三哥。总共一个小时，寒暄了20分钟的之前做过的project，简单
: 问了一些基本的coding知识，然后做了2个题，2个题都没做好，估计是肯定杯具了。之
: 前低估了bb家面试的难度，准备的太欠缺了，在这给大家提个醒一定要准备充分。第一
: 个题是写个函数输出所有的满足前三位和等于后三位和的六位数，比如156723，我写了
: 个bruteforce的，被要求优化，想了下说可以利用对称性减一些运算量，但是要考虑有
: padding zero的情况，后来时间不多了也就不了了之了，面试官说其实是可以推出个公
: 式的，晕。第二个题是给一个8*8的board，其中有两个点被block了不能放东西，现在
: 给定这两个店的坐标，写个程序检测可否用domino pizza来覆盖这个board，其中每个

m*t2012-09-25 07:09

27 楼

bless
and
拍拍
not
momo
哈哈