《第4次面试算法讲座byJuly培训课件》由会员分享，可在线阅读，更多相关《第4次面试算法讲座byJuly培训课件（33页珍藏版）》请在金锄头文库上搜索。
1、2013年第4次面试&算法讲座,July 面试成功必备的10大要素 中科院计算所 二零一三年十一月二十四日,面试成功必备的10大要素,基础 coding能力 手写代码能力 细节边界条件 算法 不断优化能力 简历 项目 or paper 平等交流互动 核心竞争力或潜力 自信,三大核心要素,基础 coding能力 算法,百考不厌的基础题,TCP建立连接的三次握手 死锁的条件 线程与进程的区别 指针与引用的区别 C+内存分配 堆、栈、自由存储区、全局/静态存储区，常量存储区 sizeof字节大小/虚拟函数 各排序算法的时间复杂度 -快速排序、堆排、归并排序等 Java中hashtable与hashm
2、ap的区别 HashMap基于Hashtable实现，不同之处在于HashMap是非同步的，并且允许null，即null value和null key，Hashtable则不允许null 动态链接库与静态链接库的区别,coding能力,是否能毫无障碍的实现心中想法 是否能完整清晰的表达意图 是否注意边界条件 是否注意优化 可读性如何,手写code能力,十分钟手写快速排序,快排的两段参考实现,快排为何快？,细节边界条件,字符串转换成整数 输入一个表示整数的字符串，把该字符串转换成整数并输出，例如输入字符串345，则输出整数345。 思路 每扫描到一个字符，我们便把在之前得到的数字乘以10，然后再
3、加上当前字符表示的数字。 正负+，- 非法输入，如输入是指针，判断是否为空 非法字符，不是数字 溢出问题,12,算法,字符串处理 字符串翻转、匹配 字符串库函数的编写 最长公共子串、子序列 基于各种数据结构 链表、数组、树、hash表 二分查找 动态规划 海量数据处理 数理逻辑 经典问题变形 系统设计 数据挖掘、机器学习,其它数据结构,数组、图 链表 翻转 遍历、查找、插入、删除 合并 有环无环，有无相交 树 查找、遍历 最近公共祖先 高级树：AVL树、红黑树、B树、B+树等 set、map hash表 如何构造hash函数 如何避免冲突 hashset、hashmap,不断优化能力,讲两个例
4、子： XML验证器的设计 为了验证一个字符串是否是一个合法的XML名字，迭代访问字符串中的每一个字符并检查它是否是由namechar内定义的合法字符 代码之美第5章 完美洗牌算法 程序员编程艺术第35章：,XML验证器的基本实现,第一个版本,数字验证O（N）,似乎大功告成？,能否继续优化？,英雄会后台判题代码,O（N*longN）优化,受启发，改进后：,O（1）优化,hash表，然后查表,完美洗牌算法,有个长度为2n的数组 a1,a2,a3,.,an,b1,b2,b3,.,bn，希望排序后 a1,b1,a2,b2,.,an,bn， 请考虑有无时间复杂度o(n)，空间复杂度0(1)的解法。,蛮力
5、变换,步步前移,中间交换,仍然是蛮力变换：,完美洗牌算法,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 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 -
6、 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往神级结论所需的值上套； 剩下的
7、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 b7 前面部分开始走圈：a1 a2 a3 a4 b1 b2 b3 b4 然后解决后半部分：a5 a6 a7 b5 b6 b7,完美洗牌算法流程,输入数组A1.2 * n 找到 2 * m = 3k - 1 使得 3k = 2 * n 3(
8、k +1) 把am + 1.n + m那部分循环移m位 对每个i = 0,1,2.k - 1，3i是个圈的头部，做cycle_leader算法，数组长度为m，所以对2 * m + 1取模。 对数组的后面部分A2 * m + 1. 2 * n继续使用本算法, 这相当于n减小了m。,10大要素,基础 coding能力 手写代码能力 细节边界条件 算法 不断优化能力 简历 项目 or paper 平等交流互动 核心竞争力或潜力 自信,简历,看似微小却非常重要,项目 or paper 平等交流互动 核心竞争力或潜力 自信,现场coding，讲座结束优胜者奖书一本,给定一个两个字符串，它们包含了相同字符。求把一个字符串变成另外一个字符串的最小操作次数。 这里的操作是把某个字符移动到此字符串中的开头。 例如“bcda dcba 需要操作2次 方法bcda-cbda-dcba,thank you,
