北京谷歌中国（Google）iOS面试经验

问的都是leetcode类似的题，没有原题但都是稍微改变过的变种。面试官很注重交流，一开始会把问题故意模糊，等着你问问题。 写代码的时候一边写一边解释，不要闭着眼写，交流非常重要，比写bug free的代码重要得多。

March 27/2015第一个题目和黄西的题目一样，就是说给定一个string，然后让你把所有vowel给reverse。很简单的，但是其实要写的简洁还是比较有难度的，以下是我的code，大家可以参考一下。（见*1）接着就是让我写一下test case去test我的code。然后follow up是说，如果你的vowel是不定的，有多种可能，那要怎么样设计。那我就说在内部maintain一个list，存放所有的可能的vowel的情况，然后我再提供一个addVowel()function去往类里面添加Vowel。然后每次都在isVowel里面一个一个判断。然后他问我说用什么数据结果去存储vowel，我说用hashset，他说如果多线程会有什么问题，这个我就答不太上来了。但是我感觉到面试官哥哥仔貌似对这样子一个solution不是特别满意，现在回想起来，其实他应该是想要我用OO design的方法去设计这个问题。现在想起来，应该可以用factory pattern去完成这一个东西，但是面试官没有把我往那个方向guide，感觉比较奇怪，因为这个面试官好像并没有特别想把我往他预想的一个solution上面guide的念头。 第二个题目也很简单，假设你有一个infinite的list，里面存放的东西是1111111111…………111000000000。然后让你判断出前面1的数目，接着他就扔了这个interface给我：interface InfiniteList{ public int get(int index){}}这个其实在Medallia的面试里面见过类似的，就是用一个数字去probe，直到probe到0为止，每一次我都让数字左移，那我就能在O(log n)的时间里面得到数字0的位置。然后再用binary search去查找第一个0所在的数字，那这个就是binary search，获取第一个duplicate的技巧。以下是我写的code：（见*2）写完这个题目，面试官倒是没有提出什么followup，就是直接让我写了一下test case，接着跑一下，然后就跳到下一个题目了。 第三个题目有点蛋疼，开始的时候没有理解他的题意，他的意思是让我写一个Scheduler的class，然后假设你已经有了一个function叫做submit的，每次调用这个function，它就会把任务提交给系统，系统会在timeMs之后才执行这个任务。然后要求保证系统minTimeMs之内只执行一个task，这个题目应该是做错了，呵呵呵，时间太紧了，而且面试官也没有怎么guide我，我觉得这个面试官有点***咯。以下是我在面试的时候的答案：（见*3）我到现在还没有想到一个很好的解法April 3/2015今天面了Google的onsite，Google果然不愧是目前所有IT公司题目的发源地，题目都很难，而且让人觉得无从下手。以下是每一轮的题目，面试经验啥的也没有什么好说的了，题目不会就不会，即使面试官给hints，问题是那个题目本身就很难的了，实在很难在面试反应过来一个正确的答案。所以，如果要面Google，还是要提前把近期的面经全部刷一遍。 第一轮：这一轮考了两个题目，第一个是给你一个array，这个array是binomial max heap，然后让你求出前k个最大的数，同时不改变binomial heap的结构和性质。这个题目其实是要自己去maintain另外一个maxHeap，之后每次我都把top给拿出来，放到result里面，同时把这个top的children节点给放到maxHeap里面。于是就***掉了。第二题，给定一个String text和pattern，要你把pattern在text里面的pattern的character放到结果的string前面，其他就无所谓顺序地放到结果的string就ok了。比如Text = “afkkiiiaakkshf”, Pattern = “fish”，那输出就应该是“ffiiishaaakkkk”。这个题目简单，但是因为第一个题目和面试官讨论了太久，所以没有时间写完。第二轮：这一轮也是两个题目，第一个是，给你一个String，它由是+和-组成。然后假设有两个player，每个player能够把连续的两个-变成+，如果其中一个player没有连续的-可以更改，那他就会输掉比赛。开始的时候是让我写一个function去生成所有的可能的next generation的的String，follow up是说，假设两个player都是绝对理性的，之后让写一个function，判断给定一个string，当前的player能不能够获胜。第一个问题很简单啦，写一个for循环就好了。第二个问题我和面试官讨论了很久，甚至马尔科夫模型都出来了，但是都没有给出一个好的解法，所以最后只能暴暴力力地去解它了，就是求出每一个next generation可能的string，接着recurse每一个string。第三轮：这一轮因为是设计题啦，所以还比较简单。题目就是说，假设我一个image的size和一个screen的size，然后我要让整个screen都被image充满，然后要求你返回最小的缩放比例。这个很简单，就是screen的宽和image的宽比，screen的高和image的高比，之后返回最小的那个。接着followup就是假设我在server端有很多image，接着server会接收到mobile的request请求某一个image，接着server就要把image处理好，之后发送到mobile。假设image拉伸的method，fill()执行的代价很昂贵，那要怎么样提高执行的效率。那我就说用cache咯，把image的id，screen size合在一起作为key，拉伸好之后的image放到HashMap里面。接着我们就一直在讨论如何cache，他就说，假设给你两个diagram，第一个diagram是关于每一个image在某个时间被调用的数。第二个diagram是不同screen size的query的频数。那我就说，把尽量频繁出现的image按照最频繁出现的screen size用LRU cache去存储。之后面试官就让我写一下应该怎么样cache。之后这一轮就没有了。 第四轮：这个面试官开始的时候先问我之前已经面过了，是跪在哪一轮，之后我超级诚实地跟他说，很傻地跪在电面了。然后面试官就开始问我第一个问题了，第一个问题是spiral matrix，然后不能再外加两个loop去把剩下的一行或者一列去处理，之前黄西有给我看过这个解法，无奈不太记得了，所以就只能尽量回忆了。 之后第二题是说，给你一个string的长度L，还有一个list的word，之后让你把这些string按照word list里面的顺序填到一个长为L的char array里面，要求word与word之间必须至少有一个空格，那这样子就有可能有很多种情况。然后要求返回一个长度为L的数组，标识出所有总是不为空格的位置。

一面是电话面试，主要考察基础的数据结构和算法。45分钟，第一道题较容易，第二道题会在第一道题的基础上延伸。一面过后就是onsite，一共5轮，每轮都是技术面，45分钟。面试官都比较和蔼，会适当进行提示。