Finian’s WebLog

Google 笔试

Sep 23

finianUncategorized 1 Comment

终于如愿以偿地前去被Google鄙视了，事实上，Google的笔试题目还是很基础的，可惜对于我来说，Google还是来得太早了，对于笔试我现在还是没找到太多的感觉，看来得加快复习进度了，后面很多笔试都快杀过来了，希望能够复习得充分一些，争取更多的机会吧。Anyway，感受了一下Google的宣讲会，感受了一下第一场笔试，还是蛮不错的。

P.S. 第二道算法题值得做一下，题目大意是“给定一个集合A，元素为0～9（不一定都出现），现给定一个正整数k，求由集合A元素所组成的大于k的最小整数。如给定集合A{0,1}和k:12，则结果为100”。在考场时想到了大概思路但没来得及写完（手写代码还是不习惯）。最没效率的做法当然就是生成一个靠近k的整数区间，然后从中选出符合的解。如果k很大，这个做法的效率就相当低（生成了一些不必要的数，当然可以适当优化一些，尽量少地产生不必要的数）。想到的一个较好的算法是，从左到右扫描k（把k当字符串），对于k中的每一位，在集合中选出最接近的数（对于接近程度来说，“大于等于”优于“小于”），然后和k中的这一位进行对比，如果“等于”，则继续下一位的处理；如果“大于“，则将后面（右边）的各位全部置为集合A中最小的元素，输出结果；如果”小于“，则往左回一位（此时该位与k中相应位的关系必然是“等于”），看是否可以“提升”该位的值，如果可以，提升该位的值并把其后面（右边）各位全置为集合A中最小的元素，如果不可以，则再往左回一位，做同样的判断，直到可以提升或者到达最左边一位为止，如果最左边一位也不可以提升，则所求的结果显然是比k多一位的最小整数了。

举个实际例子，比如A为{0,1,5,7}，k为17196，结果为xxxxx。从左到右遍历k，第1位是1，在A中找到最接近的数1，和k中的1相等，则继续处理第2位，此时结果为1xxxx；k中第2位是7，在A中找到最接近的数7，和k中的相等，继续处理第3位，此时结果为17xxx；k中第3位是1，类似地，继续处理第4位，此时结果为171xxx；k中第4位为9，在A中找到最接近的数为7，比k中的小，所以往回处理第3位1，看是否可以提升到比1大的数，显然，1可以提升为5，所以把第3位后面各位全置为A中最小的元素，亦即0，输出结果为17500。