Google电话面试常见问题汇总

这是由好办法汇总通过面经整理汇总的Google电面常见题目。

Google电话面试是电话交流，面试官会直接把题目复制到google doc里面，代码则是在google doc里面写。

1. Wiggle Sort

2. Maximum Depth of Binary Tree

binary tree的max height，我先是写了个方法，然后他说既然你用Java，那就把他变成class的method吧，然后就做了点小改动，没什么大问题。

Maximum Depth of Binary Tree题目及参考解答

描述在地址栏输入url address后整个过程……..

简单的回答，就是：
1. 你的浏览器首先询问 DNS 找到 domain 对应的 IP
2. 得到 IP 之后，你的浏览器向这个 IP 的服务器 (web server) 发 Http 请求 (request)
3. 服务器收到你的request之后做处理，期间包括从数据库拿数据等等，然后把结果作为一条回复response向你发来，也就是一个网页
4. 浏览器展示这个网页给你，并异步的下载图片之类的静态文件，并 cache这些静态文件。

这样答之后，然后就看面试官还需要你再详细说明什么你就再继续详细说明。每一个步骤都还包括更多的细节

4. 投硬币游戏

1枚硬币，来选择出1-3的数字（比如3部电影，选出看哪一部），我想很简单啊，投两次不就有0-3四个数字么，不可以选出来了么，然后他说万一投到0咋办，我说那继续重投，毕竟1/4的概率不是总能遇到的，然后他说可以优化这样，如果投到0，那再投一次，那么就有0-7 8个数字，那么可以：
1-2 -》1
3-4 -》2
5-6 -》3

0-7 -》再投一次

5. 排序算法解释

选一种排序算法解释，我选了MergeSort

6. Number of Islands

找一个 m*n 的 map 中的 Island 数量。每个点和它上下左右相连的点都是同一个 Island。例如：
000×0000
00xxx00x
000xx0x0
00xxx000

这个里面就有三个 Island。

Number of Islands LintCode算法题原创参考解答Java

7. Android Unlock Patterns

要求计算android手机九宫格滑动解锁的combination一共有多少种。 combination的长度要求从4到9。

8. Decode String

我就只有一道题，是string decompression.
example
3[ab]2[abc]e 变成 ababababcabce.
3[2[de]f] 变成  dedefdedefdedef

9. Moving Average from Data Stream

题目很简单，就是leetcode 346 题，moving average from datastreaming。但楼主做的时候这道题还没post 出来。目测只要将time complexity 降到O（1） 就行，楼主就是维护一个window size 大小的List，和一个window size 内所有数的和。但要注意corner case。

LeetCode 346. Moving Average from Data Stream Java参考解答

中国大哥出的题:

Given a set of integers, print out all the subsets

For example, {1, 2, 3}

output: {}, {1,2}, …., {1,2,3}