Google面试题精讲.ppt

Google面试题精讲七月算法曹鹏 2015年6月12日2/提纲?关于面试?一些例题?例1 被3和5整除的数的和?例2 合法单词?例3 和0交换的序列排序?例4 放到结尾的序列排序?例5 BFS及其推广?例6 单词对?总结关于面试?各个公司有没有自己的题库?题库里的题目来源?员工?网络?笔试和面试?笔试:没有交流?面试?展现思路?给面试官好印象3/例1 被3和5整除的数的和?例1 给定一个数n, 求不超过n的所有的能被3或者5整除的数的和。例如: n = 9,答案3 + 6 + 5 + 9 = 23。?分析:数学问题?被3整除的数, 3,6,9,…[n / 3] * 3?被5整除的数, 5,10,15, [n / 5] * 5?重复的数同时是3和5的倍数 15, 30, …[n / 15] * 15?注意点? n的范围4/例1 续?等差数列求和公式? x是首项,y是项数, d是公差?(x + x + d * (y – 1)) * y / 2, 注意y = 0也适用?关键是项数!?加 x = 3, d = 3, y = n / 3?加 x = 5, d = 5, y = n / 5?减 x = 15, d = 15, y = n / 155/例2 合法字符串?例2 字符串只有可能有A、B、C三个字母组成,如果任何紧邻的三个字母相同,就非法。求长度为n的合法字符串有多少个?比如:ABBBCA是非法,A是合法的。?分析:动态规划的思路——真的要枚举么??dp[i][0] : 长度为i的、最后两位不同的合法串的个数?dp[i][1]: 长度为i的、最后两位相同的合法串的个数?递推: dp[i][0] = (dp[i-1][0] * 2 + dp[i-1][1] * 2) dp[i][1] = dp[i-1][0]6/例2 续?初值?dp[1][0] = 3, dp[1][1] = 0?结果?dp[n][0] + dp[n][1]?空间优化?dp[i][0,1]只与dp[i-1][0,1]相关,可以省掉高维?时间复杂度?O(n)7/例3 和0交换的排序?例3 一个整数组里包含0-(n-1)的排列(0到(n-1)恰好只出现一次),如果每次只允许把任意数和0交换,求排好顺序至少交换多少次。(PAT 1067)?分析:组合数学里的圈。?例如0占了1的位置,1占了2的位置,2占了0的位置。?一个排列,总可以划分为若干个不相交的圈?上例我们交换0和1,再交换0和2,则排好顺序了8/例3 续?一个长度为m的圈,如果包含0,则交换(m -1)次可以恢复所有的数到原位?如果一个长度为m的圈不包含0,则交换(m+ 1) 次可以恢复所有的数到原位?例如1在2的位置,2在3的位置,3在1的位置?我们先交换0和任意一个数,例如交换0和1?则变成1在0的位置,0在2的位置,2在3的位置,3在1的位置。9/例3 续2 代码10/