Dell T20 升级内存# Hardware - 计算机硬件
k*n
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. 三哥不可怕，三姐才可怕。。。实在是反应慢又一根筋
最后，看到这个的谷歌的哥们手下留情，这些题都不是新题，也没啥可保密的了。
中国人在这边混都不容易，尤其是在这个时节，给自己人留条活路吧。
五轮技术加一个午饭。
第一轮主要问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. 三哥不可怕，三姐才可怕。。。实在是反应慢又一根筋
最后，看到这个的谷歌的哥们手下留情，这些题都不是新题，也没啥可保密的了。
中国人在这边混都不容易，尤其是在这个时节，给自己人留条活路吧。
