k****n
发帖数: 369 | 1 攒rp。兄弟们一起努力，共度时艰。
五轮技术加一个午饭。
第一轮主要问project。还问了怎么改进page rank算法。
这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
最后出了一道简单coding题，就是两个dim都分别有序的
matrix，怎么查找。我先说了binary search，用master theorem估算了一下
发现是大于linear的，就说了正常的算法。然后是实现。
这个发挥一般，open questin让我准备不足。
第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
先用状态机做了，看是否会跳到合法的结束，还是跳到非法状态。
写完代码经过提示才发现可以直接用一个256大小的数组判断是否合法。
弄完了之后暗骂自己，这么明显的空间换时间都没看出来。发挥太差了
第二题是设计一个数据结构存储soduku，目标是判断没有完全填好的行/列/方块
是否合法。因为有第一题地教训，我直接就往那边想了，说存三份数据，一共
才243个字节，更新的时候更新三份，方便又简洁。估计哥们自己也没想过这个
办法，直接被我搞懵了。讨论了几分钟确认的确work。
然后我就问他你原来是什么想法，他说never mind。。。
因为还有五分钟左右下一个才来，我估计他原来的想法是怎样快速索引
一个matrix中的若干元素之类的。因为之前看过numpy实现的一个设计文档
就拿过来吹了一通，哥们也么听说过，听我吹得挺高兴的，应该算是把第一题补上了点
这个第一题发挥不好，第二题超预期，应该会strong support我吧，我猜。
第三个是个特腼腆的三弟。上来问我google hint words。这个之前版友就提过
我还重点研究了一下，就神吹了一通，挺欢乐的，到时间了还没吹完，连coding都没做
这个因为前面吹顺嘴了，侃的特别欢乐，如果不是以外，应该会support我。
然后是午饭，主要是听对方神吹。我饿坏了，啃了两个大汉堡，真挺难吃的。。。
我问他google买moto之后是不是hiring就会停。哥们说moto的bar太低，估计不会大批
transfer过来人。。。不过就算有影响哥们也不会跟我说么，必须的。。。
第四个是个德国人。哥们特别严肃。先问了个基本的map reduce的问题。记不住了
反正两句话就答出来了。然后问了两句现在做的项目。然后又是一道coding。
是那道底在x轴上的矩形数组求外轮廓的成题。
讨论了一下，用line sweeping加priority queue做，哥们也认可了。
写程序的时候发现我发现delete操作最坏是O(n)的，所以应该用个bst什么的。
当时没说，最后忘了，不知道他是不是就懒得提醒我了。
然后要求写了几个test case。我最后说其实矩形之间的关系就三种
最保险就写个script create all combination就好了。。。
这个发挥的不能算好，哥们口音重，很少笑，不知道最后他是不是认同
最后一个是个三妹，这个最坑爹。我觉得如果死肯定死在她身上。
出的题特简单，直方图盛水最大容量。我之前在版上扫过一眼知道是O(n)的
看讨论也不多，觉得应该挺简单就没好好做。结果上来就卡住了。
经过提示发现需要对每个点算它左右的最大值，brute force是n^2的
因为我之前推过笛卡尔树，这题看起来用笛卡尔树可以解的样子
我就提了一句。结果在这坑爹的事儿来了，姐们没听说过笛卡尔树。
我就傻逼兮兮的给讲了一遍怎么构造，为啥是O(n)。。。
构造特麻烦，O(n)也不是直观的，三姐半天才弄明白，一下子时间就快到了
最后讲完说加一个辅助域可能就可以解这道题了，反正也是O(n)的
结果发现没有明显的方式加这个辅助域。。。只能做到nlgn
我就慌了，三姐说那你把brute force写出来吧。
来不及想了，赶紧写。还好写得快，写出来还有几分钟，三姐检查了一下
然后就是例行公事，说你还有啥问题。我心里憋屈啊，
就说你把email给我吧，我回去做出来这道题发给你。三姐不给
我就怒了说这题肯定有O(n)解。然后突然就想出来原来直接扫描两遍
生成个最大值数组就行了。。。但是真是没时间写代码了。
妈的坑死哥们了。丫要是知道笛卡尔树，直接画个树两分钟就否了
下面应该还能做第二题，也不算太惨。这么一搞基本就挂了。
总结：
1. 其实已经没什么新题了。遇到老题的概率极大，一定要做熟所有题
2. 面试官也是普通程序员，神人肯定有，不过大部分人都跟你我差不多。
3. 不要把面试当面试，就当平时讨论问题好了，该拍就拍，该吹就吹。
4. 一分积累就有一分收获，能少上网多看书就多看看。不知道什么时候就能用上。
5. 三哥不可怕，三姐才可怕。。。实在是反应慢又一根筋
最后，看到这个的谷歌的哥们手下留情，这些题都不是新题，也没啥可保密的了。
中国人在这边混都不容易，尤其是在这个时节，给自己人留条活路吧。 |
l*****k
发帖数: 1059 | |
g*****i
发帖数: 2162 | 3 bless,第二轮的两题能讲讲你的解法吗?243字节怎么出来的?第一个unicode不是很熟,
也解释下吧.谢谢. |
k****n
发帖数: 369 | 4 不是讽刺我吧。。。
我觉得三妹真的一般，第一个面试官是大牛
其它都还是不错的，对得起google这个牌子
【在 l*****k 的大作中提到】
: 你就是神人，比大部分面试官都强！
|
f**b
发帖数: 3043 | |
c******o
发帖数: 534 | |
z*********n
发帖数: 203 | |
s***c
发帖数: 50 | 8 强Bless!!
楼主好牛啊，handle了这么多难题。我onsite时碰到的题都很弱智。。。
【在 k****n 的大作中提到】
: 攒rp。兄弟们一起努力，共度时艰。
: 五轮技术加一个午饭。
: 第一轮主要问project。还问了怎么改进page rank算法。
: 这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
: 最后出了一道简单coding题，就是两个dim都分别有序的
: matrix，怎么查找。我先说了binary search，用master theorem估算了一下
: 发现是大于linear的，就说了正常的算法。然后是实现。
: 这个发挥一般，open questin让我准备不足。
: 第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
: 因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
|
P**********c
发帖数: 3417 | 9 最后一道题是用stack, 遇到比前面一个大的就pop出之前stack里的所有值。有些很简
单的题目确实真正做的时候方向想错了也挺麻烦的。
不过我觉得问题不大了，你展示了自己丰富的知识面，呵呵，相信这个会给面试官留下
好印象。
【在 k****n 的大作中提到】
: 攒rp。兄弟们一起努力，共度时艰。
: 五轮技术加一个午饭。
: 第一轮主要问project。还问了怎么改进page rank算法。
: 这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
: 最后出了一道简单coding题，就是两个dim都分别有序的
: matrix，怎么查找。我先说了binary search，用master theorem估算了一下
: 发现是大于linear的，就说了正常的算法。然后是实现。
: 这个发挥一般，open questin让我准备不足。
: 第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
: 因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
|
f*******t
发帖数: 7549 | 10 晕，感觉好难啊，特别是数学题我完全看不懂……
楼主不是new grad吧？ |
|
|
y********n
发帖数: 205 | 11 感谢
bless
【在 k****n 的大作中提到】
: 攒rp。兄弟们一起努力，共度时艰。
: 五轮技术加一个午饭。
: 第一轮主要问project。还问了怎么改进page rank算法。
: 这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
: 最后出了一道简单coding题，就是两个dim都分别有序的
: matrix，怎么查找。我先说了binary search，用master theorem估算了一下
: 发现是大于linear的，就说了正常的算法。然后是实现。
: 这个发挥一般，open questin让我准备不足。
: 第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
: 因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
|
t*******i
发帖数: 4960 | 12 我也不会，lz的专业研究这些东西的？
【在 f*******t 的大作中提到】
: 晕，感觉好难啊，特别是数学题我完全看不懂……
: 楼主不是new grad吧？
|
d********y
发帖数: 2114 | 13 第一题是指两维矩阵横向和纵向都是有序，然后查找？
是不是可以把矩阵分成4份递归？ |
d*******d
发帖数: 2050 | |
d********y
发帖数: 2114 | |
I******y
发帖数: 176 | |
k****n
发帖数: 369 | 17 哪里有数学题。。。我数学烂的要命
【在 f*******t 的大作中提到】
: 晕，感觉好难啊，特别是数学题我完全看不懂……
: 楼主不是new grad吧？
|
a********m
发帖数: 15480 | |
h******n
发帖数: 68 | 19 很赞，多谢
【在 k****n 的大作中提到】
: 攒rp。兄弟们一起努力，共度时艰。
: 五轮技术加一个午饭。
: 第一轮主要问project。还问了怎么改进page rank算法。
: 这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
: 最后出了一道简单coding题，就是两个dim都分别有序的
: matrix，怎么查找。我先说了binary search，用master theorem估算了一下
: 发现是大于linear的，就说了正常的算法。然后是实现。
: 这个发挥一般，open questin让我准备不足。
: 第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
: 因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
|
s**x
发帖数: 7506 | 20 你那个 hint words and sodoku 是怎么答的？ 多谢分享。 |
|
|
C*****s
发帖数: 292 | |
l****y
发帖数: 1461 | 22 bless!!
★ Sent from iPhone App: iReader Mitbbs Lite 7.21 |
r*******g
发帖数: 1335 | 23 HI
能不能详细讲讲是题目是什么，这4道没看明白，出了两个dim有序的search那道其他都
不清楚。。。
1，设计一个数据结构存储soduku，what is soduku?
2, google hint words
3, 那道底在x轴上的矩形数组求外轮廓的成题?
4, 直方图盛水最大容量
谢谢了。
【在 k****n 的大作中提到】
: 攒rp。兄弟们一起努力，共度时艰。
: 五轮技术加一个午饭。
: 第一轮主要问project。还问了怎么改进page rank算法。
: 这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
: 最后出了一道简单coding题，就是两个dim都分别有序的
: matrix，怎么查找。我先说了binary search，用master theorem估算了一下
: 发现是大于linear的，就说了正常的算法。然后是实现。
: 这个发挥一般，open questin让我准备不足。
: 第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
: 因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
|
a****e
发帖数: 428 | 24 Thanks for sharing your experience. There are more interview questions and
interview experience at "Job Interview Experience" Forum at OverseaTalents (
the dedicated oversea Chinese professional community)
below: such as "140 Google Interview Questions"
http://www.overseatalents.com/forum/1942 |
p*******1
发帖数: 270 | |
m*********6
发帖数: 609 | |
k****n
发帖数: 369 | 27 hit words太open了，实在讲不清楚
可以看看modern information retrieval以及introduction to information
retrieval之类的书
按我理解，应该是对Search Engine的基本数据的重复利用什么的
sudoku就是把每行每列每个正方形都单独存一份，所以一共有
int rows[9][9]
int cols[9][9]
int squares[9][9]
这样，更新就更新三次，取数随便从哪个取当然都行
关键是他要求的判断是否合法的操作，就对27个int[9]做同样的判断就行了
【在 s**x 的大作中提到】
: 你那个 hint words and sodoku 是怎么答的？ 多谢分享。
|
k****n
发帖数: 369 | 28
sudoku，数独
how do you design google suggestion if you are the designer
一个矩形数组，每个矩形由x1,x2,y决定（因为底在x轴上），y>0
给你一个直方图，假设天上一直下雨，问最后直方图里面能盛多少水
【在 r*******g 的大作中提到】
: HI
: 能不能详细讲讲是题目是什么，这4道没看明白，出了两个dim有序的search那道其他都
: 不清楚。。。
: 1，设计一个数据结构存储soduku，what is soduku?
: 2, google hint words
: 3, 那道底在x轴上的矩形数组求外轮廓的成题?
: 4, 直方图盛水最大容量
: 谢谢了。
|
t**********0
发帖数: 1700 | 29 笛卡尔树，这是自己找死么，你写得出来那个code么？
【在 k****n 的大作中提到】
: 攒rp。兄弟们一起努力，共度时艰。
: 五轮技术加一个午饭。
: 第一轮主要问project。还问了怎么改进page rank算法。
: 这个是老本行，不过都忘差不多了。吭哧半天想起来一些，不是很爽。
: 最后出了一道简单coding题，就是两个dim都分别有序的
: matrix，怎么查找。我先说了binary search，用master theorem估算了一下
: 发现是大于linear的，就说了正常的算法。然后是实现。
: 这个发挥一般，open questin让我准备不足。
: 第二轮两道比较简单的题，一个是识别一个字符串是否是一个合法的utf-8串。
: 因为合法utf8字符可能是变长字节的，就是1/2/3字节都有可能
|
k*j
发帖数: 153 | 30 这个直方图盛水，其实就是直方图里求最大矩形那道经典题吗？
我看过的解法都是用stack。lz说的用辅助数组的算法没见过，能讲讲吗？谢谢。 |
|
|
g**e
发帖数: 6127 | 31 不是
【在 k*j 的大作中提到】
: 这个直方图盛水，其实就是直方图里求最大矩形那道经典题吗？
: 我看过的解法都是用stack。lz说的用辅助数组的算法没见过，能讲讲吗？谢谢。
|
k*j
发帖数: 153 | 32 ok. 又读了一遍题，明白了意思。谢谢
【在 g**e 的大作中提到】
: 不是
|
