第4面试算法讲座July

1、2013年第4次面试&算法讲座july面试成功必备的10大要素中科院计算所二零一三年十一月二十四日面试成功必备的10大要素 基础 coding能力 手写代码能力 细节边界条件 算法 不断优化能力 简历 项目 or paper 平等交流互动 核心竞争力或潜力 自信三大核心要素 基础 coding能力 算法基础是根基 有基础和一定的coding能力，再谈算法 既然要参加笔试面试，那么便是想进公司上班 在公司内，没有一定的coding能力，之前可能再华丽的研究也只是建立在一片废墟上 根基不牢，理想大厦随时可能会轰然倒塌。百考不厌的基础题1. tcp建立连接的三次握手2. 死锁的条件3. 线程

2、与进程的区别4. 指针与引用的区别5. c+内存分配 堆、栈、自由存储区、全局/静态存储区，常量存储区6. sizeof字节大小/虚拟函数7. 各排序算法的时间复杂度-快速排序、堆排、归并排序等8. java中hashtable与hashmap的区别 hashmap基于hashtable实现，不同之处在于hashmap是非同步的，并且允许null，即null value和null key，hashtable则不允许null9. 动态链接库与静态链接库的区别coding能力 是否能毫无障碍的实现心中想法 是否能完整清晰的表达意图 是否注意边界条件 是否注意优化 可读性如何手写code能力十分钟手

3、写快速排序快排的两段参考实现快排为何快？细节边界条件 字符串转换成整数 输入一个表示整数的字符串，把该字符串转换成整数并输出，例如输入字符串345，则输出整数345。思路 每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再加上当前字符表示的数字。1. 正负+，-2. 非法输入，如输入是指针，判断是否为空3. 非法字符，不是数字4. 溢出问题12算法 字符串处理 字符串翻转、匹配 字符串库函数的编写 最长公共子串、子序列 基于各种数据结构 链表、数组、树、hash表 二分查找 动态规划 海量数据处理 数理逻辑 经典问题变形 系统设计 数据挖掘、机器学习其它数据结构 数组、图 链表 翻转

4、遍历、查找、插入、删除 合并 有环无环，有无相交 树 查找、遍历 最近公共祖先 高级树：avl树、红黑树、b树、b+树等 set、map hash表 如何构造hash函数 如何避免冲突 hashset、hashmap不断优化能力讲两个例子： xml验证器的设计为了验证一个字符串是否是一个合法的xml名字，迭代访问字符串中的每一个字符并检查它是否是由namechar内定义的合法字符 代码之美第5章 完美洗牌算法 程序员编程艺术第35章：http:/ 第一个版本数字验证o（n）似乎大功告成？能否继续优化？ 英雄会后台判题代码o（n*longn）优化 受启发，改进后：o（1）优化 hash表，然后查

5、表完美洗牌算法 有个长度为2n的数组a1,a2,a3,.,an,b1,b2,b3,.,bn，希望排序后a1,b1,a2,b2,.,an,bn，请考虑有无时间复杂度o(n)，空间复杂度0(1)的解法。蛮力变换 步步前移中间交换 仍然是蛮力变换：完美洗牌算法 2004年，microsoft的peiyush jain在他发表一篇名为：“a simple in-place algorithm for in-shuffle”的论文中提出了完美洗牌算法。即给定一个数组a1,a2,a3,.an,b1,b2,b3.bn,最终把它置换成b1,a1,b2,a2,.bn,an两个圈起始序列：a1 a2 a3 a4

6、b1 b2 b3 b4数组下标：1 2 3 4 5 6 7 8最终序列：b1 a1 b2 a2 b3 a3 b4 a4走圈算法cycle_leader：一个是1 - 2 - 4 - 8 - 7 - 5 - 1；一个是3 - 6 - 3。 1 2 3 4 5 6 7 8 5 1 3 2 7 6 8 4 5 1 6 2 7 3 8 4任意的第i个元素，最终都将换到：第（2*i） % （2*n+1）个元素的位置。神级结论 对于2*n = （3k-1）这种长度的数组，恰好只有k个圈，且每个圈头部的起始位置分别是1,3,9，.3(k-1)。 若给定的长度n，分而治之把整个数组一分为二，即拆分成两个部分： 让一部分的长度满足神级结论：若2*m = （3k-1），则恰好k个圈，且每个圈头部的起始位置分别是1,3,9，.3(k-1)。其中mn，m往神级结论所需的值上套； 剩下的n-m部分单独计算。原始数组下标：1.m m+1. n， n+1 . n+m, n+m+1,.2*n目标数组下标：1.m n+1.n+m m+1 . n n+m+1,.2*n原始数组：a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 b4 b5 b6 b7目标数组：a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 b5 b6 b71. 前面部分开始走圈：a1 a2 a3 a4 b1