发Google面经，为明天MS攒rp - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

发Google面经，为明天MS攒rp

发Google面经，为明天MS攒rp# JobHunting - 待字闺中

c*m2010-02-11 08:02

1 楼

Google和MS都是summer intern，phone interview
以为google上来就是alg & coding呢。
结果被问了超多概念问题。。。都没准备。
coding题都很简单，可惜是最后问的，时间不多
第一个人，老印，有点口音，听不太清。。。不过人还不错。
问了超多概念，包罗万象。我答不出的，他自己就解释给我。
最后还有10分钟，问coding，5分钟后改题目。。。我在google doc上就写了5分钟。然
后问 time complexity。
第二个人，老美，说话挺快的。
也是先问概念，晕。。。
然后是design的题，没搞懂他到底想问啥。
最后是coding。先讲算法。然后拿例子过一遍。然后在google doc上写。然后问下time
complexity和improvment。
具体题目如下：
interviewer 1:
1. C++/Java concepts: inherent, virtual, interface, implementation, abstract
class, ... (Many)
2. Operating system: m

z*32010-02-11 08:02

2 楼

你shortest substring那题是怎么做的？

c*o2010-02-11 08:02

3 楼

可不可以用trie阿？

S*n2010-02-11 08:02

4 楼

你的怎么会有这么多概念问题？我一个概念都没有问，要是问这么多概念和数据库的
东西我估计会比较惨，你是做什么方向的？
问一下，google doc的链接是什么时候发给你的，是面之前，还是过程中？我昨天面了
第一个最后
都没有要求写code,明天还有一面，面后再写面经

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

: Google和MS都是summer intern，phone interview
: 以为google上来就是alg & coding呢。
: 结果被问了超多概念问题。。。都没准备。
: coding题都很简单，可惜是最后问的，时间不多
: 第一个人，老印，有点口音，听不太清。。。不过人还不错。
: 问了超多概念，包罗万象。我答不出的，他自己就解释给我。
: 最后还有10分钟，问coding，5分钟后改题目。。。我在google doc上就写了5分钟。然
: 后问 time complexity。
: 第二个人，老美，说话挺快的。
: 也是先问概念，晕。。。

s*i2010-02-11 08:02

5 楼

dp. o(n)

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

: 你shortest substring那题是怎么做的？

b*g2010-02-11 08:02

6 楼

什么是dp?

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

: dp. o(n)

r*o2010-02-11 08:02

7 楼

是不是应该是o(mn)，
m和n分别是字符串的个数和特殊字符的个数。

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

: dp. o(n)

z*32010-02-11 08:02

8 楼

能不能展开说说? 用dp的话，不能保证两个子串的shortest substring合起来也是
shortest substring吧，中间还有很多字符

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

: dp. o(n)

z*32010-02-11 08:02

9 楼

dynamic programming

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

: 什么是dp?

c*m2010-02-11 08:02

10 楼

恩，我确实是database方向的。
google doc都面之前发的，就一空白文档

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

: 你的怎么会有这么多概念问题？我一个概念都没有问，要是问这么多概念和数据库的
: 东西我估计会比较惨，你是做什么方向的？
: 问一下，google doc的链接是什么时候发给你的，是面之前，还是过程中？我昨天面了
: 第一个最后
: 都没有要求写code,明天还有一面，面后再写面经

c*m2010-02-11 08:02

11 楼

我当时写了个O(m*n)的
然后他问我能不能speed up到linear的
因为已经超时了，我就稍微讲了一下optimize的思路

【在 r****o 的大作中提到】

: 是不是应该是o(mn)，
: m和n分别是字符串的个数和特殊字符的个数。

m*k2010-02-11 08:02

12 楼

shortest string question:
hashtable, key is each covered character, value is count.
从头开始扫描，如果是covered letter,则更新count，直到找到所有count都大于0.然
后从开始字母删除，并且更新count.直到其中一个变为0。则这个string是当前最短的
。如此这样扫描整个string，如果找到比这个短的就更新.
例如， abcabcdeddeabbc ,找abcde. (这个例子我只用的covered letters在长string
中，同理包含其他字符)。
刚开始找到 abcabcde, table: a=2,b=2,c=2,d=1,e=1.然后，从第一个字母删除，a=>1
,b=>1,c=>1,直到a=>0停止，则abcde是当前最短的。然后从ddeabbc开始找。
这么做对吗？

c*m2010-02-11 08:02

13 楼

恩，这个思路跟我当时写的很像。
我能想到的speed up的方法就是在扫描string的过程中记录下covered letters的位置
。这样就可以直接jump到下一个需要update的位置，省去中间那些无关的字符。

b*r2010-02-11 08:02

14 楼

不能直接跳到“ddeabbc”吧，要继续向右扫描，知道再次COVER所有char

string
>1

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

: shortest string question:
: hashtable, key is each covered character, value is count.
: 从头开始扫描，如果是covered letter,则更新count，直到找到所有count都大于0.然
: 后从开始字母删除，并且更新count.直到其中一个变为0。则这个string是当前最短的
: 。如此这样扫描整个string，如果找到比这个短的就更新.
: 例如， abcabcdeddeabbc ,找abcde. (这个例子我只用的covered letters在长string
: 中，同理包含其他字符)。
: 刚开始找到 abcabcde, table: a=2,b=2,c=2,d=1,e=1.然后，从第一个字母删除，a=>1
: ,b=>1,c=>1,直到a=>0停止，则abcde是当前最短的。然后从ddeabbc开始找。
: 这么做对吗？

m*k2010-02-11 08:02

15 楼

你说的对，继续扫描。

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

: 不能直接跳到“ddeabbc”吧，要继续向右扫描，知道再次COVER所有char
:
: string
: >1