PYTHON程序员面试宝典

第1章 技术面试的方法论 1 1.1 一道亚马逊面试题的情景分析 1 1.1.1 暴力枚举法 2 1.1.2 分而治之法 4 1.1.3 *优解法 6 1.1.4 解题流程总结 7 1.2 面试的流程，心态建设，相关准备 8 1.2.1 面试前流程 8 1.2.2 简历的制作 10 1.2.3 有效的面试策略 11 1.2.4 编码实现 12 1.2.5 面试过程中的交流要点 13 1.3 知己知彼，百战不殆——从面试官角度看面试 14 1.3.1 如何进行一场良好的面试 15 1.3.2 面试官如何主导面试流程 17 1.3.3 面试官如何评估候选人 17 第2章 算法面试的技术路线图 19 2.1 算法面试中的数据结构 19 2.1.1 基础数据类型 20 2.1.2 数组与字符串 21 2.1.3 链表 21 2.1.4 堆栈 22 2.1.5 二叉树 22 2.1.6 堆 23 2.1.7 哈希表 23 2.2 算法的设计模式 24 2.2.1 排序 24 2.2.2 递归 26 2.2.3 分而治之 27 2.2.4 动态规划 29 2.2.5 贪婪算法 29 2.2.6 逐步改进 29 2.2.7 排除法 30 2.3 抽象分析模式 30 2.3.1 样例覆盖 31 2.3.2 小量数据推导 31 2.3.3 简单方案的逐步改进 32 2.3.4 问题还原 33 2.3.5 图论模拟 34 第3章 基础数据类型的算法分析 35 3.1 基础数据类型中二进制位的操作算法 35 3.1.1 整型变量值互换 35 3.1.2 常用的二进制位操作 36 3.1.3 解析一道二进制操作相关算法面试题 37 3.1.4 总结 40 3.2 用二进制操作求解集合所有子集 40 3.2.1 题目描述 40 3.2.2 算法描述 40 3.2.3 代码实现 41 3.2.4 算法分析 43 3.3 使用二进制求解*大公约数 43 3.3.1 题目描述 43 3.3.2 算法描述 45 3.3.3 代码实现 47 3.3.4 算法分析 49 3.4 素数判定 50 3.4.1 题目描述 50 3.4.2 算法描述 50 3.4.3 代码实现 52 3.4.4 算法分析 53 3.5 判断矩形交集 54 3.5.1 题目描述 54 3.5.2 算法描述 54 3.5.3 代码实现 56 3.6 数字与字符串相互转化，简单题目的隐藏陷阱 58 3.6.1 题目描述 58 3.6.2 算法描述 58 3.6.3 代码实现 59 3.6.4 算法分析 60 3.7 Elias Gamma编码算法 62 3.7.1 题目描述 62 3.7.2 算法描述 63 3.7.3 代码实现 63 3.7.4 算法分析 66 3.8 整型的二进制乘法 67 3.8.1 题目描述 67 3.8.2 算法描述 67 3.8.3 代码实现 69 3.8.4 算法分析 73 第4章 数组和字符串 74 4.1 数组的定位排序 74 4.1.1 题目描述 74 4.1.2 算法描述 75 4.1.3 代码实现 76 4.1.4 算法分析 78 4.2 在整型数组中构建元素之和能整除数组长度的子集 78 4.2.1 题目描述 78 4.2.2 算法描述 78 4.2.3 代码实现 79 4.2.4 算法分析 82 4.3 计算等价类 82 4.3.1 题目描述 82 4.3.2 算法描述 83 4.3.3 代码实现 85 4.3.4 代码分析 86 4.4 大型整数相乘 87 4.4.1 题目描述 87 4.4.2 算法描述 87 4.4.3 代码实现 88 4.4.4 代码分析 91 4.5 数组的序列变换 92 4.5.1 题目描述 92 4.5.2 算法描述 92 4.5.3 代码实现 94 4.5.4 代码分析 96 4.6 字符串的旋转 96 4.6.1 题目描述 96 4.6.2 算法描述 96 4.6.3 代码实现 97 4.6.4 代码分析 99 4.7 二维数组的启发式搜索算法 99 4.7.1 题目描述 99 4.7.2 算法描述 99 4.7.3 代码实现 100 4.7.4 代码分析 101 4.8 二维数组的旋转遍历 102 4.8.1 题目描述 102 4.8.2 算法描述 102 4.8.3 代码实现 104 4.8.4 代码分析 105 4.9 矩阵的90°旋转 105 4.9.1 题目描述 106 4.9.2 算法描述 106 4.9.3 代码实现 107 4.9.4 代码分析 109 4.10 游程编码 109 4.10.1 题目描述 110 4.10.2 算法描述 110 4.10.3 代码实现 110 4.10.4 代码分析 112 4.11 字符串中单词的逆转 113 4.11.1 题目描述 113 4.11.2 算法描述 113 4.11.3 代码实现 114 4.11.4 代码分析 115 4.12 Rabin-Karp字符串匹配算法 115 4.12.1 题目描述 115 4.12.2 算法描述 115 4.12.3 代码实现 118 4.12.4 代码分析 120 4.13 用有限状态自动机匹配字符串 120 4.13.1 题目描述 120 4.13.2 算法描述 121 4.13.3 代码实现 124 4.13.4 代码分析 127 4.14 KMP算法——字符串匹配算法的创意巅峰 127 4.14.1 题目描述 127 4.14.2 算法描述 127 4.14.3 代码实现 129 4.14.4 代码分析 131 4.15 正则表达式引擎的设计和实施 132 4.15.1 题目描述 132 4.15.2 算法描述 133 4.15.3 代码实现 138 4.15.4 代码分析 178 第5章 队列和链表 179 5.1 递归式实现链表快速倒转 179 5.1.1 题目描述 179 5.1.2 算法描述 180 5.1.3 代码实现 181 5.1.4 代码分析 184 5.2 链表成环检测 184 5.2.1 题目描述 185 5.2.2 算法描述 185 5.2.3 代码实现 186 5.2.4 代码分析 189 5.3 在O(1)时间内删除单链表非末尾节点 190 5.3.1 题目描述 190 5.3.2 算法描述 190 5.3.3 代码实现 191 5.3.4 代码分析 192 5.4 获取重合列表的**个相交节点 192 5.4.1 题目描述 193 5.4.2 算法描述 193 5.4.3 代码实现 194 5.4.4 代码分析 196 5.5 单向链表的奇偶排序 196 5.5.1 题目描述 196 5.5.2 算法描述 196 5.5.3 代码实现 198 5.5.4 代码分析 199 5.6 双指针单向链表的自我复制 199 5.6.1 题目描述 200 5.6.2 算法描述 200 5.6.3 代码实现 202 5.6.4 代码分析 206 5.7 利用链表层级打印二叉树 206 5.7.1 题目描述 206 5.7.2 算法描述 206 5.7.3 代码实现 207 5.7.4 代码分析 209 第6章 堆栈和队列 210 6.1 利用堆栈计算逆向波兰表达式 210 6.1.1 题目描述 210 6.1.2 算法描述 210 6.1.3 代码实现 211 6.1.4 代码分析 213 6.2 计算堆栈当前元素*大值 213 6.2.1 题目描述 213 6.2.2 算法描述 213 6.2.3 代码实现 214 6.2.4 代码分析 216 6.3 使用堆栈判断括号匹配 216 6.3.1 题目描述 216 6.3.2 算法描述 216 6.3.3 代码实现 217 6.3.4 代码分析 218 6.4 使用堆栈解决汉诺塔问题 218 6.4.1 题目描述 218 6.4.2 算法描述 219 6.4.3 代码实现 219 6.4.4 代码分析 222 6.5 堆栈元素的在线排序 222 6.5.1 题目描述 223 6.5.2 算法描述 223 6.5.3 代码实现 224 6.5.4 代码分析 225 6.6 计算滑动窗口内的*大网络流量 225 6.6.1 题目描述 226 6.6.2 算法描述 226 6.6.3 代码实现 231 6.6.4 代码分析 234 6.7 使用堆栈模拟队列 234 6.7.1 题目描述 235 6.7.2 算法描述 235 6.7.3 代码实现 235 6.7.4 代码分析 236 第7章 二叉树 238 7.1 二叉树的平衡性检测 238 7.1.1 题目描述 239 7.1.2 算法描述 239 7.1.3 代码实现 239 7.1.4 代码分析 242 7.2 镜像二叉树的检测 242 7.2.1 题目描述 243 7.2.2 算法描述 243 7.2.3 代码实现 244 7.2.4 代码分析 246 7.3 二叉树的Morris遍历法 247 7.3.1 题目描述 247 7.3.2 算法描述 247 7.3.3 代码实现 250 7.3.4 代码分析 251 7.4 使用前序遍历和中序遍历重构二叉树 252 7.4.1 题目描述 252 7.4.2 算法描述 253 7.4.3 代码实现 254 7.4.4 代码分析 256 7.5 逆时针打印二叉树外围边缘 256 7.5.1 题目描述 256 7.5.2 算法描述 257 7.5.3 代码实现 257 7.5.4 代码分析 259 7.6 寻找两个二叉树节点的*近共同祖先 259 7.6.1 题目描述 260 7.6.2 算法描述 260 7.6.3 代码实现 260 7.6.4 代码分析 264 7.7 设计搜索输入框的输入提示功能 264 7.7.1 题目描述 264 7.7.2 算法描述 264 7.7.3 代码实现 265 7.7.4 代码分析 269 第8章 堆 270 8.1 使用堆排序实现系统Timer机制 270 8.1.1 题目描述 270 8.1.2 算法描述 270 8.1.3 代码实现 273 8.1.4 代码分析 279 8.2 波浪形数组的快速排序法 279 8.2.1 题目描述 279 8.2.2 算法描述 280 8.2.3 代码实现 281 8.2.4 代码分析 287 8.3 快速获取数组中点的相邻区域点 287 8.3.1 题目描述 287 8.3.2 算法描述 287 8.3.3 代码实现 289 8.3.4 代码分析 292 第9章 二分查找法 293 9.1 隐藏在《编程珠玑》中20年的bug 293 9.1.1 题目描述 294 9.1.2 算法描述 294 9.1.3 代码实现 295 9.1.4 代码分析 297 9.2 在lg(k)时间内查找两个排序数组合并后第k小元素 297 9.2.1 题目描述 297 9.2.2 算法描述 297 9.2.3 代码实现 299 9.2.4 代码分析 301 9.3 二分查找法寻求数组截断点 302 9.3.1 题目描述 302 9.3.2 算法描述 302 9.3.3 代码实现 304 9.3.4 代码分析 306 9.4 在双升序数组中快速查找给定值 306 9.4.1 题目描述 307 9.4.2 算法描述 307 9.4.3 代码实现 307 9.4.4 代码分析 309 第10章 图论 310 10.1 地图着色问题 310 10.1.1 问题描述 310 10.1.2 算法描述 310 10.1.3 代码实现 311 10.1.4 代码分析 315 10.2 迪杰斯特拉*短路径算法 316 10.2.1 题目描述 316 10.2.2 算法描述 316 10.2.3 代码实现 319 10.2.4 代码分析 326 10.3 使用深度优先搜索解决容器倒水问题 327 10.3.1 问题描述 327 10.3.2 算法描述 327 10.3.3 代码实现 329 10.3.4 代码分析 333 第11章 贪婪算法 335 11.1 *小生成树 335 11.1.1 题目描述 335 11.1.2 算法描述 336 11.1.3 代码实现 339 11.1.4 代码分析 344 11.2 霍夫曼编码 344 11.2.1 题目描述 345 11.2.2 算法描述 345 11.2.3 代码实现 347 11.2.4 代码分析 349 11.3 离散点集的*大覆盖率问题 350 11.3.1 题目描述 350 11.3.2 算法描述 351 11.3.3 代码实现 352 11.3.4 代码分析 355 第12章 动态规划 356 12.1 钢管*优切割方案 356 12.1.1 问题描述 357 12.1.2 算法描述 357 12.1.3 代码实现 358 12.1.4 代码分析 360 12.2 查找*大共同子串 361 12.2.1 问题描述 362 12.2.2 算法描述 362 12.2.3 代码实现 364 12.2.4 代码分析 366 12.3 将*大共同子串算法的空间复杂度从O(n2)改进为O(n) 366 12.3.1 问题描述 367 12.3.2 算法描述 367 12.3.3 代码实现 368 12.3.4 代码分析 371