q***h
发帖数: 13 | 1 在国内面试的，两轮电面 + 四轮onsite，已挂
一方面说是正逢校招，北京这边的面试官资源比较紧张，另外应该也是中间面的不太好
，所以整个过程历经了快两个月，刚开始是挺焦急地等着下一步的消息，后来也淡定。
终于在这周面完最后两轮后，并于周五晚收到了HR的拒信，算是一个了结。
电面一： 安排的是硅谷的面试官，时间为北京早8点。结果从7点多开始等到9点都没有
接到电话，只好联系了HR，HR很快联系到了面试官并道歉说面试官有事给错过了，问是
接着面试还是另外安排一个时间，并说面试官马上要出差，另外安排的话可能要一两周
之后了。当时想反正都等了一个多小时了，就接着面吧。很快面试官就打了电话过来，
然后直接扔了一道题过来。 题目是：给两个以字符串形式表示的大整数，求其和。现
在回头看，其实这是一道挺普通的题目，但当时就不知怎么没能一开始就理清两个大数
的正负等不同情况了。所以最后是基本做了出来，但中间改了又改，代码很乱，存在不
少冗余，时间花得也比较长。。。
结束之后，整个人情结很低落，也懊恼万分，感觉人生的第一次谷歌面试就要至此结束
了。
大约一周左右，HR给打电话，问上次面得怎样，我回答不好，他说是的，并说让他考虑
下是否安排另一次电面。在此得再次感谢HR（以及帮忙内推的师兄，后来了解到的）很
快地很帮我安排了下一次电面，让这次谷歌面试之行得以继续。
电面二：也是硅谷的面试官。这次倒蛮顺利的，一上来开始聊了几分钟项目，然后开始
做题。第一道是二叉树相关的，假定允许交换二叉树中任意节点下的左子树与右子树，
然后给定两棵二叉树，判断它们之间是否满足这种交换关系。第二道是括号匹配验证问
题（算是leetcode的原题，虽说我是第一次电面后才开始看 待字闺中，并知道
leetcode 的，当时还没刷到这一题）。最后还有几分钟的时间就是问了些问题。
onsite 四轮，分为两次，每次两轮。中间间隔了半个多月。因为签了协议，就不细说
了，主要是题目有：
onsite 一 & 二
1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。（自
己觉得是硊在了这题。面试过程中一直没找到正确的思路，面试官开始试图给了一些引
导，但无奈没找到他所想的方向，后来他也有些不知道如何引导，因为他觉得除了答案
好像也无法给其它提示了。感觉就是两人都很无奈：他觉得都提示得那么明显了，你怎
么还不能想到呢，我自己也很着急，觉得某个点没想到，想到了就会简单，但到底是哪
个点呢。。。面试官也看他的code review去了）
2. 找出两链表的交叉节点。（经典老题，但因为前一轮的题目没时间做完，这时心里
比较着急，就急切地先把代码写了出来，并没有注意代码的精练。写完给面试官看时，
自己也指出一处冗余了，并说了是因为赶时间的原因，平时的话自己肯定还会再
refactor。不过从后来HR的反馈来看还是在这里失了分。）
3. 在一个正整数的数组中找出不在数组中的最小正整数。（leetcode原题，但我又是
在面试后才发现的。。。不过感觉答得还好，而且当时自己是想了另一种不是交换元素
的思路。怪不得当时面试官对我的思路想了好一会，最后确认是可行的。）
onsite 三 & 四
4. 设计 api 并用 mutex 实现一个读写锁。
5. 设计 api 并实现所有操作都为O(1)的 LRUCache.
6. 用 C/C++ 的基本语言特性判断某个系统上栈的生长方向。
这几题除了LRUcache那题之前有看过，其它都没接触过，但感觉现场答得还可以吧。只
是担心可能无法挽回 onsite 1& 2 的一般表现，果然两天之后收到了拒信。
最后说下自己对这次谷歌面试的感想：就是后来从这里也了解到对于FLAG等注重算法的
公司，大家都会在面试之前刷题。所以至少感觉谷歌面试官对于solution的要求比较高
，方法要是最优的，代码得是清晰无死角的。老实说，如果是一个完全没见过的新题目
，要做45分钟内做到一点，还是挺挑战的。因为有时光是想想有哪些需要注意的Corner
case 都要花不少时间。不过好像这也是当前的风气以及大势所趋，所以想去这些公司
的同学，在投简历面试之前，还是要多花些时间做题，做好准备，哪怕没能遇到原题，
至少在面试时心态上也会有底气得多。
呵呵，啰哩啰嗦写了这么，谢谢你的耐心看完，也希望能所有所帮助。
========
另外，版上有对国内amazon了解的同学吗？现在手上有一个sde的口头offer，做
payment 相关的。自己毕业后在国内ms做传统软开，两年多了，之前项目比较动荡，接
下来可能也会有变化。所以也想趁些换个环境做一些新的东西，扩展下自己，顺便增点
工资，不知那边值得跳过去吗？谢谢！ |
c********e
发帖数: 186 | |
n****e
发帖数: 678 | |
n****e
发帖数: 678 | 4 能说说第一题：
1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。
面试官是如何引导的吗？ |
v***n
发帖数: 562 | 5 多谢分享！
【在 q***h 的大作中提到】
: 在国内面试的，两轮电面 + 四轮onsite，已挂
: 一方面说是正逢校招，北京这边的面试官资源比较紧张，另外应该也是中间面的不太好
: ，所以整个过程历经了快两个月，刚开始是挺焦急地等着下一步的消息，后来也淡定。
: 终于在这周面完最后两轮后，并于周五晚收到了HR的拒信，算是一个了结。
: 电面一： 安排的是硅谷的面试官，时间为北京早8点。结果从7点多开始等到9点都没有
: 接到电话，只好联系了HR，HR很快联系到了面试官并道歉说面试官有事给错过了，问是
: 接着面试还是另外安排一个时间，并说面试官马上要出差，另外安排的话可能要一两周
: 之后了。当时想反正都等了一个多小时了，就接着面吧。很快面试官就打了电话过来，
: 然后直接扔了一道题过来。 题目是：给两个以字符串形式表示的大整数，求其和。现
: 在回头看，其实这是一道挺普通的题目，但当时就不知怎么没能一开始就理清两个大数
|
P*******r
发帖数: 210 | 6 同问，这个好像没什么思路。
【在 n****e 的大作中提到】
: 能说说第一题：
: 1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
: 度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。
: 面试官是如何引导的吗？
|
c********e
发帖数: 186 | |
s********u
发帖数: 1109 | 8 r-k算法? 为什么要拆开没太听明白，能具体说说么
, |
l*n
发帖数: 529 | 9 就是我naive的想法，拆开了无非就是找最长的片段在长串中的位置，看其前后是否能
对应上。
学界的研究太多了，不是我等能随便山寨的。
Faster algorithms for string matching with k mismatches
dl.acm.org/citation.cfm?id=338641
A guided tour to approximate string matching
http://scholar.google.com/scholar?cluster=15894901928968181925&
【在 s********u 的大作中提到】
: r-k算法? 为什么要拆开没太听明白，能具体说说么
:
: ,
|
q***h
发帖数: 13 | 10 在国内面试的，两轮电面 + 四轮onsite，已挂
一方面说是正逢校招，北京这边的面试官资源比较紧张，另外应该也是中间面的不太好
，所以整个过程历经了快两个月，刚开始是挺焦急地等着下一步的消息，后来也淡定。
终于在这周面完最后两轮后，并于周五晚收到了HR的拒信，算是一个了结。
电面一： 安排的是硅谷的面试官，时间为北京早8点。结果从7点多开始等到9点都没有
接到电话，只好联系了HR，HR很快联系到了面试官并道歉说面试官有事给错过了，问是
接着面试还是另外安排一个时间，并说面试官马上要出差，另外安排的话可能要一两周
之后了。当时想反正都等了一个多小时了，就接着面吧。很快面试官就打了电话过来，
然后直接扔了一道题过来。 题目是：给两个以字符串形式表示的大整数，求其和。现
在回头看，其实这是一道挺普通的题目，但当时就不知怎么没能一开始就理清两个大数
的正负等不同情况了。所以最后是基本做了出来，但中间改了又改，代码很乱，存在不
少冗余，时间花得也比较长。。。
结束之后，整个人情结很低落，也懊恼万分，感觉人生的第一次谷歌面试就要至此结束
了。
大约一周左右，HR给打电话，问上次面得怎样，我回答不好，他说是的，并说让他考虑
下是否安排另一次电面。在此得再次感谢HR（以及帮忙内推的师兄，后来了解到的）很
快地很帮我安排了下一次电面，让这次谷歌面试之行得以继续。
电面二：也是硅谷的面试官。这次倒蛮顺利的，一上来开始聊了几分钟项目，然后开始
做题。第一道是二叉树相关的，假定允许交换二叉树中任意节点下的左子树与右子树，
然后给定两棵二叉树，判断它们之间是否满足这种交换关系。第二道是括号匹配验证问
题（算是leetcode的原题，虽说我是第一次电面后才开始看 待字闺中，并知道
leetcode 的，当时还没刷到这一题）。最后还有几分钟的时间就是问了些问题。
onsite 四轮，分为两次，每次两轮。中间间隔了半个多月。因为签了协议，就不细说
了，主要是题目有：
onsite 一 & 二
1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。（自
己觉得是硊在了这题。面试过程中一直没找到正确的思路，面试官开始试图给了一些引
导，但无奈没找到他所想的方向，后来他也有些不知道如何引导，因为他觉得除了答案
好像也无法给其它提示了。感觉就是两人都很无奈：他觉得都提示得那么明显了，你怎
么还不能想到呢，我自己也很着急，觉得某个点没想到，想到了就会简单，但到底是哪
个点呢。。。面试官也看他的code review去了）
2. 找出两链表的交叉节点。（经典老题，但因为前一轮的题目没时间做完，这时心里
比较着急，就急切地先把代码写了出来，并没有注意代码的精练。写完给面试官看时，
自己也指出一处冗余了，并说了是因为赶时间的原因，平时的话自己肯定还会再
refactor。不过从后来HR的反馈来看还是在这里失了分。）
3. 在一个正整数的数组中找出不在数组中的最小正整数。（leetcode原题，但我又是
在面试后才发现的。。。不过感觉答得还好，而且当时自己是想了另一种不是交换元素
的思路。怪不得当时面试官对我的思路想了好一会，最后确认是可行的。）
onsite 三 & 四
4. 设计 api 并用 mutex 实现一个读写锁。
5. 设计 api 并实现所有操作都为O(1)的 LRUCache.
6. 用 C/C++ 的基本语言特性判断某个系统上栈的生长方向。
这几题除了LRUcache那题之前有看过，其它都没接触过，但感觉现场答得还可以吧。只
是担心可能无法挽回 onsite 1& 2 的一般表现，果然两天之后收到了拒信。
最后说下自己对这次谷歌面试的感想：就是后来从这里也了解到对于FLAG等注重算法的
公司，大家都会在面试之前刷题。所以至少感觉谷歌面试官对于solution的要求比较高
，方法要是最优的，代码得是清晰无死角的。老实说，如果是一个完全没见过的新题目
，要做45分钟内做到一点，还是挺挑战的。因为有时光是想想有哪些需要注意的Corner
case 都要花不少时间。不过好像这也是当前的风气以及大势所趋，所以想去这些公司
的同学，在投简历面试之前，还是要多花些时间做题，做好准备，哪怕没能遇到原题，
至少在面试时心态上也会有底气得多。
呵呵，啰哩啰嗦写了这么，谢谢你的耐心看完，也希望能所有所帮助。
========
另外，版上有对国内amazon了解的同学吗？现在手上有一个sde的口头offer，做
payment 相关的。自己毕业后在国内ms做传统软开，两年多了，之前项目比较动荡，接
下来可能也会有变化。所以也想趁些换个环境做一些新的东西，扩展下自己，顺便增点
工资，不知那边值得跳过去吗？谢谢！ |
|
|
c********e
发帖数: 186 | |
n****e
发帖数: 678 | |
n****e
发帖数: 678 | 13 能说说第一题：
1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。
面试官是如何引导的吗？ |
v***n
发帖数: 562 | 14 多谢分享！
【在 q***h 的大作中提到】
: 在国内面试的，两轮电面 + 四轮onsite，已挂
: 一方面说是正逢校招，北京这边的面试官资源比较紧张，另外应该也是中间面的不太好
: ，所以整个过程历经了快两个月，刚开始是挺焦急地等着下一步的消息，后来也淡定。
: 终于在这周面完最后两轮后，并于周五晚收到了HR的拒信，算是一个了结。
: 电面一： 安排的是硅谷的面试官，时间为北京早8点。结果从7点多开始等到9点都没有
: 接到电话，只好联系了HR，HR很快联系到了面试官并道歉说面试官有事给错过了，问是
: 接着面试还是另外安排一个时间，并说面试官马上要出差，另外安排的话可能要一两周
: 之后了。当时想反正都等了一个多小时了，就接着面吧。很快面试官就打了电话过来，
: 然后直接扔了一道题过来。 题目是：给两个以字符串形式表示的大整数，求其和。现
: 在回头看，其实这是一道挺普通的题目，但当时就不知怎么没能一开始就理清两个大数
|
P*******r
发帖数: 210 | 15 同问，这个好像没什么思路。
【在 n****e 的大作中提到】
: 能说说第一题：
: 1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
: 度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。
: 面试官是如何引导的吗？
|
c********e
发帖数: 186 | |
s********u
发帖数: 1109 | 17 r-k算法? 为什么要拆开没太听明白，能具体说说么
,
【在 l*n 的大作中提到】
: 就是我naive的想法，拆开了无非就是找最长的片段在长串中的位置，看其前后是否能
: 对应上。
: 学界的研究太多了，不是我等能随便山寨的。
: Faster algorithms for string matching with k mismatches
: dl.acm.org/citation.cfm?id=338641
: A guided tour to approximate string matching
: http://scholar.google.com/scholar?cluster=15894901928968181925&
|
l*n
发帖数: 529 | 18 就是我naive的想法，拆开了无非就是找最长的片段在长串中的位置，看其前后是否能
对应上。
学界的研究太多了，不是我等能随便山寨的。
Faster algorithms for string matching with k mismatches
dl.acm.org/citation.cfm?id=338641
A guided tour to approximate string matching
http://scholar.google.com/scholar?cluster=15894901928968181925&
【在 s********u 的大作中提到】
: r-k算法? 为什么要拆开没太听明白，能具体说说么
:
: ,
|
A******g
发帖数: 612 | |
s**x
发帖数: 7506 | 20
这个太变态了，还有前几天那个 de bruijn sequence 看了半天也没看懂。
【在 l*n 的大作中提到】
: 就是我naive的想法，拆开了无非就是找最长的片段在长串中的位置，看其前后是否能
: 对应上。
: 学界的研究太多了，不是我等能随便山寨的。
: Faster algorithms for string matching with k mismatches
: dl.acm.org/citation.cfm?id=338641
: A guided tour to approximate string matching
: http://scholar.google.com/scholar?cluster=15894901928968181925&
|
|
|
q***h
发帖数: 13 | 21 不清楚，但我没碰到。
【在 A******g 的大作中提到】
: 请问国内面试也会碰上阿三吗？
|
l*n
发帖数: 529 | 22 你不会是真下功夫研读吧？！
【在 s**x 的大作中提到】
:
: 这个太变态了，还有前几天那个 de bruijn sequence 看了半天也没看懂。
|
g*********e
发帖数: 14401 | 23
我的想法是滚动hash
比如短串是abcd
那么把它本身和误差为一个或两个char的短串的滚动hash值都算出来放到一个set里面
e.g.
abcd
bbcd
cbcd
...
zbcd
aacd
...
azcd
一共有26*10+45*26*26个备选的短串。
然后在长串里match就行了
hash function随便找个小的质数就ok
比如abcd ==>> a*7^4+b*7^3+c*7^2+d*7
【在 n****e 的大作中提到】
: 能说说第一题：
: 1. 近似字符串匹配。比如给定一个长串（10G以上的量级），再给定一个短串（比如长
: 度为10），然后允许最多有两个字符的匹配误差，让找出长串中所有的匹配位置。
: 面试官是如何引导的吗？
|
d***n
发帖数: 832 | |
p*u
发帖数: 136 | |
c********p
发帖数: 1969 | |
q***h
发帖数: 13 | 27 不太喜欢总部那边的气候，也不想一直待在MS，感觉那样接触的东西比较有限。
【在 d***n 的大作中提到】
: 为什么不先transfer到MS总部呢
|
w*****t
发帖数: 485 | 28 赞楼主面筋，很有参考价值，感谢～
【在 q***h 的大作中提到】
: 在国内面试的，两轮电面 + 四轮onsite，已挂
: 一方面说是正逢校招，北京这边的面试官资源比较紧张，另外应该也是中间面的不太好
: ，所以整个过程历经了快两个月，刚开始是挺焦急地等着下一步的消息，后来也淡定。
: 终于在这周面完最后两轮后，并于周五晚收到了HR的拒信，算是一个了结。
: 电面一： 安排的是硅谷的面试官，时间为北京早8点。结果从7点多开始等到9点都没有
: 接到电话，只好联系了HR，HR很快联系到了面试官并道歉说面试官有事给错过了，问是
: 接着面试还是另外安排一个时间，并说面试官马上要出差，另外安排的话可能要一两周
: 之后了。当时想反正都等了一个多小时了，就接着面吧。很快面试官就打了电话过来，
: 然后直接扔了一道题过来。 题目是：给两个以字符串形式表示的大整数，求其和。现
: 在回头看，其实这是一道挺普通的题目，但当时就不知怎么没能一开始就理清两个大数
|
