周末去软店看了SB - 未名空间MITBBS历史存档

x*i2015-11-01 07:11

1 楼

下午刚刚面的，面试官是个国人大哥。上来他先自我介绍了一下，然后我自我介绍，说
了下phd的研究内容。然后就开始coding。
第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
inplace，线性复杂度。这一题做的很顺利。面试官说good enough
第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
我试了一下，果断发现bug，修好。
然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂
。然后lz就删了重新用levelorder traversal写了一遍，写完的时候其实就超时了一分
钟左右。面试官没让lz检查，说已经good enough了，不过还是指出一个小错误，然后
自己主动把那个bug改掉了。然后面试官说这题有空间复杂度O(1)的做法，不过lz当时
估计也想不出来这么做。
然后让我问了问我问题就结束了。感觉面试官挺nice的，但听说fb的要求是bug free，
我这还是有点小bug，不知道能不能到下一轮。顺便求个bless了。。

s*u2015-11-01 07:11

2 楼

先去的果店，与果店的人头攒动相比，只有1/4大的软店门可罗雀，所以小二很热情，
我说先随便看看。找了一会儿果然发现了SB，做工真是不错，轻薄，仔细一看原来是来
弄我。。。继续找，找了半天没找到，只好问小二，小二说这不在门口么？看我有兴趣
就热情地给我介绍起来，说你看这样就能把板子弄下来了，你看这板子多轻，可以待机
3小时，还可以反着插。。。我自己合上了看看，果然合不拢，缝隙还很大。。。小儿
问您要下单不？我忙说我就是来看看然后就溜了。。。
结论是撇开软件不谈，我完全想不通买这种四不像有什么必要。。。

m*72015-11-01 07:11

3 楼

bless!!

pc2015-11-01 07:11

4 楼

必须合拢是啥道理？

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

: 先去的果店，与果店的人头攒动相比，只有1/4大的软店门可罗雀，所以小二很热情，
: 我说先随便看看。找了一会儿果然发现了SB，做工真是不错，轻薄，仔细一看原来是来
: 弄我。。。继续找，找了半天没找到，只好问小二，小二说这不在门口么？看我有兴趣
: 就热情地给我介绍起来，说你看这样就能把板子弄下来了，你看这板子多轻，可以待机
: 3小时，还可以反着插。。。我自己合上了看看，果然合不拢，缝隙还很大。。。小儿
: 问您要下单不？我忙说我就是来看看然后就溜了。。。
: 结论是撇开软件不谈，我完全想不通买这种四不像有什么必要。。。

m*72015-11-01 07:11

5 楼

第二题： constant space的方法， ANY HINT?

g*n2015-11-01 07:11

6 楼

板砖控

【在 pc 的大作中提到】

: 必须合拢是啥道理？

i*h2015-11-01 07:11

7 楼

bless

t*a2015-11-01 07:11

8 楼

处女座

【在 pc 的大作中提到】

: 必须合拢是啥道理？

n*e2015-11-01 07:11

9 楼

bless

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

: 下午刚刚面的，面试官是个国人大哥。上来他先自我介绍了一下，然后我自我介绍，说
: 了下phd的研究内容。然后就开始coding。
: 第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
: inplace，线性复杂度。这一题做的很顺利。面试官说good enough
: 第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
: 一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
: 上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
: 我试了一下，果断发现bug，修好。
: 然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
: 一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂

c*z2015-11-01 07:11

10 楼

因为所有的笔记本都是能合拢的，所以不合拢是不对的。这个逻辑你明白？

【在 pc 的大作中提到】

: 必须合拢是啥道理？

x*i2015-11-01 07:11

11 楼

我也不知道，他没细说。感觉想要constant memory的话，morris trasversal可以做到
constant memory遍历完整个树，不过他说那个方法不难的。
唉，很努力也，还是没做到bug free

【在 m********7 的大作中提到】

: 第二题： constant space的方法， ANY HINT?

p*e2015-11-01 07:11

12 楼

知道啥叫创新不？

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

: 因为所有的笔记本都是能合拢的，所以不合拢是不对的。这个逻辑你明白？

a*a2015-11-01 07:11

13 楼

bless
第一题是假设原来的数组的空间足够吗？是不是可以假设数组的空间有数组长度的两倍。

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

: 下午刚刚面的，面试官是个国人大哥。上来他先自我介绍了一下，然后我自我介绍，说
: 了下phd的研究内容。然后就开始coding。
: 第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
: inplace，线性复杂度。这一题做的很顺利。面试官说good enough
: 第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
: 一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
: 上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
: 我试了一下，果断发现bug，修好。
: 然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
: 一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂

c*z2015-11-01 07:11

14 楼

与众不同的事情，苹果做出来叫创新，微软做叫SB，这个逻辑你明白？

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

: 知道啥叫创新不？

s*z2015-11-01 07:11

15 楼

bless!
顺便问下,第一题能给个思路么?还是是不是假设数组大小足够大啊?

r*t2015-11-01 07:11

16 楼

先决定批判再找理由，这个逻辑是文革逻辑，你明白？！

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

: 与众不同的事情，苹果做出来叫创新，微软做叫SB，这个逻辑你明白？

s*p2015-11-01 07:11

17 楼

同问第一题啊

bless!顺便问下,第一题能给个思路么?还是是不是假设数组大小足够大啊?

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

: bless!
: 顺便问下,第一题能给个思路么?还是是不是假设数组大小足够大啊?

s*u2015-11-01 07:11

18 楼

合不拢也算创新？

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

: 与众不同的事情，苹果做出来叫创新，微软做叫SB，这个逻辑你明白？

a*a2015-11-01 07:11

19 楼

我估计得至少两倍空间存在，最惨的情况是字符串上全是a，然后又要求inplace的话。。
我的想法是把字符串先复制到数组的后面，然后再挨个拷回前面
void add_a_remove_b(char* a){
int len = strlen(a);
for(int i=0; iint p = 0;
for(int i=0; iif (*(a+len+i) == 'a') {
*(a+p) = 'a';
*(a+p+1) = 'a';
p = p+2;
}
else if (*(a+len+i) == 'b') continue;
else{
*(a+p) = *(a+len+i);
p++;
}
}
*(a+p) = '\0';
}

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

: bless!
: 顺便问下,第一题能给个思路么?还是是不是假设数组大小足够大啊?

j*22015-11-01 07:11

20 楼

合不拢确实挺着急的，特别对于强迫症患者。不信你随便找个laptop，放下盖子但留个
1寸左右张开放在客厅或者办公室有人经过的地方。
半小时之内就会有人帮你合上。

x*i2015-11-01 07:11

21 楼

。。
我的做法跟你差不多。区别是先把字符从后往前modify，然后拷回前面去

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

: 我估计得至少两倍空间存在，最惨的情况是字符串上全是a，然后又要求inplace的话。。
: 我的想法是把字符串先复制到数组的后面，然后再挨个拷回前面
: void add_a_remove_b(char* a){
: int len = strlen(a);
: for(int i=0; i: int p = 0;
: for(int i=0; i: if (*(a+len+i) == 'a') {
: *(a+p) = 'a';
: *(a+p+1) = 'a';

t*a2015-11-01 07:11

22 楼

昨天从软店回来，默默地订了MACBOOK

s*p2015-11-01 07:11

23 楼

a 加倍是把a 加到自己后面吗？还是放到数组的尾巴？假设数组的长度正好吗？能说说
思路吗？

同问第一题啊

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

: 同问第一题啊
:
: bless!顺便问下,第一题能给个思路么?还是是不是假设数组大小足够大啊?

a*a2015-11-01 07:11

24 楼

SB又不是前面合不拢。现在这设计更像个binder，强迫症患者还非得把binder压扁不成？

【在 j********2 的大作中提到】

: 合不拢确实挺着急的，特别对于强迫症患者。不信你随便找个laptop，放下盖子但留个
: 1寸左右张开放在客厅或者办公室有人经过的地方。
: 半小时之内就会有人帮你合上。

s*z2015-11-01 07:11

25 楼

你也是额外用一倍的空间么? 这样算inplace么...额

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

:
: 。。
: 我的做法跟你差不多。区别是先把字符从后往前modify，然后拷回前面去

y*b2015-11-01 07:11

26 楼

嘿嘿，你难道觉得这不可能？我觉得大多数人都可能偶有这冲动

x*i2015-11-01 07:11

27 楼

假设给的数组长度足够就好了么。leetcode上有类似题

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

: 你也是额外用一倍的空间么? 这样算inplace么...额

c*z2015-11-01 07:11

28 楼

如果苹果做那就叫创新，微软做出来就是傻逼。macbook全机只有一个usb-c口没有任何
扩展能力不也有sb叫好么。mac pro那个垃圾桶样还有人说革命。所以说苹果做出来合
不拢还不知道果粉怎么舔呢。

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

: 合不拢也算创新？

h*o2015-11-01 07:11

29 楼

level order咋弄？我怎么感觉还是要preorder呢

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

:
: 假设给的数组长度足够就好了么。leetcode上有类似题

i*r2015-11-01 07:11

30 楼

可以反复插。。。

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

: 先去的果店，与果店的人头攒动相比，只有1/4大的软店门可罗雀，所以小二很热情，
: 我说先随便看看。找了一会儿果然发现了SB，做工真是不错，轻薄，仔细一看原来是来
: 弄我。。。继续找，找了半天没找到，只好问小二，小二说这不在门口么？看我有兴趣
: 就热情地给我介绍起来，说你看这样就能把板子弄下来了，你看这板子多轻，可以待机
: 3小时，还可以反着插。。。我自己合上了看看，果然合不拢，缝隙还很大。。。小儿
: 问您要下单不？我忙说我就是来看看然后就溜了。。。
: 结论是撇开软件不谈，我完全想不通买这种四不像有什么必要。。。

Z*72015-11-01 07:11

31 楼

bless
现在FB也没那么难了

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

: 下午刚刚面的，面试官是个国人大哥。上来他先自我介绍了一下，然后我自我介绍，说
: 了下phd的研究内容。然后就开始coding。
: 第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
: inplace，线性复杂度。这一题做的很顺利。面试官说good enough
: 第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
: 一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
: 上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
: 我试了一下，果断发现bug，修好。
: 然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
: 一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂

r*e2015-11-01 07:11

32 楼

what the heck. binder? are you kidding? Jobs once said, MS has no taste,
what's so ever.

成？

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

: SB又不是前面合不拢。现在这设计更像个binder，强迫症患者还非得把binder压扁不成？

m*s2015-11-01 07:11

33 楼

Zan, Bless!

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

: 下午刚刚面的，面试官是个国人大哥。上来他先自我介绍了一下，然后我自我介绍，说
: 了下phd的研究内容。然后就开始coding。
: 第一题，给一个字符数组，要求将其中的'a'加倍，'b'删除，其他字符保持不变。要求
: inplace，线性复杂度。这一题做的很顺利。面试官说good enough
: 第二题，Sum Root to Leaf Numbers。这个题平时写起来很熟练的。可这是lz人生中第
: 一次求职面试，有点紧张。写完以后面试官说有点问题，然后我改了一下，没改到点子
: 上。面试官很nice的说，你为啥不找个testcase试一试呢，然后给了我两个testcase，
: 我试了一下，果断发现bug，修好。
: 然后面试官说时间不够做第三题了，让我把第二题recursion改成iterative的方法。我
: 一开始就动手写iterative版本的preorder traversal，写了一半面试官说没这么复杂

K*32015-11-01 07:11

34 楼

软店在我这里和苹果一样大，问题是没有太多的玩具，所以没多少人。果店人也没有那
么多了，特别是这次ｉＰｈｏｎｅ备货充分，连队伍第三天就没了。我还在等ｉＰａｄ
Ｐｒｏ，也许买买。
ＭＢＰ的最大问题是操作系统。换装Ｗｉｎ１０触摸屏没有全功能支持，真是熊掌。以
前的ＯＳＸ还有些有点，现在比起Ｗｉｎ７／１０优点荡然无存。我一下子想不起来Ｏ
ＳＸ有任何优势了，启动也很慢，关机也慢，ｂｕｇ也不少，病毒也开始了。。。除了
上次把一台ＧＰＳ救活了外，真可惜了MBP的硬件。
我还是觉得，用苹果硬件跑微软的ＯＳ要合理的多，比如用ｉＰｈｏｎｅ６ｓ跑ＷＰ１
０。。。

q*n2015-11-01 07:11

35 楼

是不是可以先traverse一遍，count the number of a, b.算出目标长度，然后inplace
from end to first copy each char to end, if it is a, double, if it is b,
skip it.
这样复杂度是O（2n），也是线性的。

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

:
: 假设给的数组长度足够就好了么。leetcode上有类似题

K*32015-11-01 07:11

36 楼

软店在我这里和苹果一样大，问题是没有太多的玩具，所以没多少人。果店人也没有那
么多了，特别是这次ｉＰｈｏｎｅ备货充分，连队伍第三天就没了。我还在等ｉＰａｄ
Ｐｒｏ，也许买买。
ＭＢＰ的最大问题是操作系统。换装Ｗｉｎ１０触摸屏没有全功能支持，真是熊掌。以
前的ＯＳＸ还有些有点，现在比起Ｗｉｎ７／１０优点荡然无存。我一下子想不起来Ｏ
ＳＸ有任何优势了，启动也很慢，关机也慢，ｂｕｇ也不少，病毒也开始了。。。除了
上次把一台ＧＰＳ救活了外，真可惜了MBP的硬件。
我还是觉得，用苹果硬件跑微软的ＯＳ要合理的多，比如用ｉＰｈｏｎｅ６ｓ跑ＷＰ１
０。。。

x*i2015-11-01 07:11

37 楼

update一下，这一轮过了，进下一轮。。感谢国人大哥放水。。

w*92015-11-01 07:11

38 楼

bless

x*n2015-11-01 07:11

39 楼

如果是缩小呢？就算不缩小，比如这个：btaa。会踩到自己的脚，把T弄没了。
应该先从左到右先把b的坑填了，顺便点a个数。然后从目标长度从右到左double a。

inplace

【在 q******n 的大作中提到】

: 是不是可以先traverse一遍，count the number of a, b.算出目标长度，然后inplace
: from end to first copy each char to end, if it is a, double, if it is b,
: skip it.
: 这样复杂度是O（2n），也是线性的。