第4次面试算法讲座byJuly.ppt

《第4次面试算法讲座byJuly.ppt》由会员分享，可在线阅读，更多相关《第4次面试算法讲座byJuly.ppt（33页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第4次面试算法讲座byJuly Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望面试成功必备的10大要素基础coding能力手写代码能力细节边界条件算法不断优化能力简历项目 or paper平等交流互动核心竞争力或潜力自信三大核心要素基础coding能力算法基础是根基有基础和一定的coding能力，再谈算法既然要参加笔试面试，那么便是想进公司上班在公司内，没有一定的coding能力，之前可能再华丽的研究也只是建立在一片废墟上根基不牢，理想大厦随时可能会轰然倒塌。百考

2、不厌的基础题1.TCP建立连接的三次握手2.死锁的条件3.线程与进程的区别4.指针与引用的区别5.C+内存分配堆、栈、自由存储区、全局/静态存储区，常量存储区6.sizeof字节大小/虚拟函数7.各排序算法的时间复杂度-快速排序、堆排、归并排序等8.Java中hashtable与hashmap的区别HashMap基于Hashtable实现，不同之处在于HashMap是非同步的，并且允许null，即null value和null key，Hashtable则不允许null9.动态链接库与静态链接库的区别coding能力是否能毫无障碍的实现心中想法是否能完整清晰的表达意图是否注意边界条件是否注意优

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

4、插入、删除合并有环无环，有无相交树查找、遍历最近公共祖先高级树：AVL树、红黑树、B树、B+树等set、maphash表如何构造hash函数如何避免冲突hashset、hashmap不断优化能力讲两个例子：XML验证器的设计为了验证一个字符串是否是一个合法的XML名字，迭代访问字符串中的每一个字符并检查它是否是由namechar内定义的合法字符代码之美第5章完美洗牌算法程序员编程艺术第35章：http:/ Jain在他发表一篇名为：“A Simple In-Place Algorithm for In-Shuffle”的论文中提出了完美洗牌算法。即给定一个数组a1,a2,a3,.an,b1,b

5、2,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-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)。若

6、给定的长度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 b2 b3 b42.然后解决后半部分：a5 a6 a7 b5 b6 b7完美洗牌算法流程输入数组A1.2*n1.找到 2*m=3k-1 使得 3k=2*n cbda-dcbathank you