kazi1@的部落格

Phone Interview:
1. 一个sorted的linked list，最后一个node会link回第一个node（相当于是一个loop），现在要把一个新的node插入其中，使整个loop仍旧保持一个sorted的状态。
2. 如何测试Gmail。

On-site Interview:
第一轮，美国女：
给出一个String，要求rearrange这个String，相邻的两个characters不能相同。如果String不能满足这个要求（比如abbbb），就返回空String。
. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
第二轮，美国小哥：
做code review。给出几个class，用来连接数据库、建立table、获取数据等等。要review的code是一个连接database，根据给出的key去fetch data，然后输出结果的function。

（Code review之外，面试官提到了在做test时每次到database去fetch data都要很久，问是否有优化的方法。另外，因为给出的class本身是implement了一个interface，所以面试官询问了一堆Java interface相关的问。）


第三轮，中国小哥：
一个graph，如果把其中一个点挪动位置，得到一个新的graph。看起来这两个graphs好像“长得”不一样，但是实际上是相同的。给出两个graph，要求编程判断这两个graphs是否相同。（complexity不计，也就是说可以完全不考虑时间空间复杂度，只要能够解决问题即可。）



第四轮，美国小哥：
1. 给出一个integer array，求其中consecutive的sub-array的最大长度（LeetCode原题，No. 128）。
2. 给出一个tree（不一定是binary，也就是说每个node的children个数不定），求其中元素是consecutive的最大长度。——类似Leetcode原题No. 298，区别是这里的tree不一定是binary tree。

3. 如果题2中的tree大到memory无法运行，要怎么办

鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 
第五轮，中国女：
给出一个binary tree，其中有一个node出了问题，它链接到了一个illegal的位置——比如说，C是D的child，但是有一个链接把C又连回了D，相当于D又是C的child，这不是一个valid的binary tree。要求编程找到这个出错的node，相当于Validate a Binary Tree。
. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴