面试算法培训讲座.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,面试算法培训讲座,1,你最大的资本是什么？,2,你最大的资本就是你的自信!,3,So，keep relaxed，have fun!,4,第一部分,2014校招梳理,5,2014校招热点,2014校招笔试面试题集锦,下面试题前的题号对应上文中的题号,6,总体思路,笔试偏基础,涵盖语言，计算机组成原理、操作系统、网络协议、数据库、概率期望等知识,面试偏算法,且极具针对性的根据简历提问,无论是笔试还是面试，两者都很看重你的实际编程能力,7,笔面关键,基础,coding能力,算法,8,三者关系,有基础和一定的coding能力，再谈算法。,既然要参加笔试面试，那么便是想进公司上班,在公司内，没有一定的coding能力，之前可能再华丽的研究也只是建立在一片废墟上，根基不牢，理想大厦随时可能会轰然倒塌。,9,百考不厌的基础题,TCP建立连接的三次握手,死锁的条件,线程与进程的区别,指针与引用的区别,C+内存分配,堆、栈、自由存储区、全局/静态存储区，常量存储区,sizeof字节大小/虚拟函数,各排序算法的时间复杂度,-快速排序、堆排、归并排序等,Java中hashtable与hashmap的区别,HashMap基于Hashtable实现，不同之处在于HashMap是非同步的，并且允许null，即null value和null key，Hashtable则不允许null,动态链接库与静态链接库的区别,10,面试中手写code的能力极为重要,11,算法,字符串处理,字符串翻转、匹配,字符串库函数的编写,最长公共子串、子序列,基于各种数据结构,链表、数组、树、hash表,二分查找,动态规划,海量数据处理,数理逻辑,经典问题变形,系统设计,数据挖掘、机器学习,12,时间复杂度,不断优化，不断精简,13,字符串处理,字符串翻转,微软面试100题第10题、,翻转句子中单词的顺序，例如输入“I am a student.”，则输出“student.a am I”。,编程艺术第1章、,字符串的左旋转操作，如把字符串abcdef左旋转2位得到字符串cdefab，要求时间O(n)，空间O(1)。,18,、在原字符串中把尾部m个字符移动到字符串的头部，如原字符串为”Ilovebaofeng”，m=7，输出结果：”baofengIlove”。,34,、设计一个反转字符串的函数 char*reverse_str(char*str),不使用系统函数。,14,字符串库函数编写,字符串库函数,3,、已知memcpy的函数为：void*memcpy(void*dest,const void*src,size_t count)其中dest是目的指针，src是源指针，请实现memcpy。,22,、写一个memmove的函数,15,、字符串转换为整数，实现atoi的,22,、实现C的strstr,-功能：从字符串str1中查找是否有字符串str2，,-如果有，从str1中的str2位置起，返回str1中str2起始位置的指针，如果没有，返回null。,15,字符串中的串中串,最长公共子序列,不要求连续,最长公共子串,要求连续,16,8分钟手写memcpy,17,18,其它数据结构,数组、图,链表,翻转,遍历、查找、插入、删除,合并,有环无环，有无相交,树,查找、遍历,最近公共祖先,高级树：AVL树、红黑树、B树、B+树等,set、map,hash表,如何构造hash函数,如何避免冲突,hashset、hashmap,19,二分查找,二分查找相关,请实现二分查找,5,&,8、,杨氏矩阵查找,杨氏矩阵变形,给定n*n的实数杨氏矩阵，求这n2个数的中位数,20,21,动态规划,适用条件,最优子结构+重叠子问题,例子,11,、输入两个整数 n 和 sum，从数列1，2，3.n 中 随意取几个数,使其和等于 sum,要求将其中所有的可能组合列出来。,list1.push_front(n);/典型的01背包问题,find_factor(sum-n,n-1);/放n，n-1个数填满sum-n,list1.pop_front();,find_factor(sum,n-1);/不放n，n-1个数填满sum,21,海量数据处理,hash函数映射+hashmap统计+堆排,26,、单机5G内存，磁盘200T的数据，分别为字符串，然后给定一个字符串，判断这200T数据里面有没有这个字符串，怎么做？如果查询次数会非常的多,怎么预处理？,31,、有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。,42,、假设已有10w个敏感词，现给你50个单词，查询这50个单词中是否有敏感词。,22,hash映射+hashmap+堆&归并,31,、有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。,先把100W个关键字hash映射到小文件，根据题意，100W*50B=50*106B=50M，而内存只有1M，故干脆搞一个hash函数%50，分解成50个小文件；,针对对每个小文件依次运用hashmap(key，value)完成每个key的value次数统计，后用堆找出每个小文件中value次数最大的top 10；,最后依次对每两小文件的top 10归并，得到最终的top 10。,细节很重要。,23,数理逻辑,纯粹考智力,1,、一个桶里面有白球、黑球各100个，现在按下述规则取球：每次从通里面拿出来两个球；,i、如果取出的是两个同色的求，就再放入一个黑球；,ii、如果取出的是两个异色的求，就再放入一个白球。,问：最后桶里面只剩下一个黑球的概率是多少？,6.1,、宿舍内5个同学一起玩对战游戏。每场比赛有一些人作为红方，另一些人作为蓝方。请问至少需要多少场比赛，才能使任意两个人之间有一场红方对蓝方和蓝方对红方的比赛？,12,、,24,快排partition的变形,三色球问题,22,、相同的球放到一起，让你按顺序输出红白蓝三种颜色的球，可以用012来表示，要求只能扫描一次数组,将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。,这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗,25,三色球问题思路,类似快排中partition过程，用三个指针，一前begin，一中current，一后end，俩俩交换。,current遍历，整个数组序列，current指1不动，,current指0，与begin交换，而后current+，begin+，,current指2，与end交换，而后，current不动，end-。,快排中的partition过程？,26,三色球解决步骤1,27,三色球解决步骤2,28,子数组最大和的变形,36,、输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。,i)一维：输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。,ii)二维：,29,iii)子数组”并不只是一个二维数组或矩形，而是联通的元素(上下或左右相邻即视为联通),iv)如果是个轮胎呢？,30,系统设计,合适的数据结构+算法,输入“结构之”，会提示“结构之法”，“结构之法 算法之道”等搜索词,31,第二部分,资料推荐,32,准备资料,3个系列,3本书,一个讲座,3个网站/论坛,一个微信公众账号,33,3个系列,程序员编程艺术,从最容易想到的思路开始讲起，一步步优化,而不是其它题解那样一上来就给你所谓的标准速成答案，面试亦如此,秒杀99%的海量数据处理面试题,涵盖腾讯、百度、阿里巴巴等公司最喜欢考的关于海量数据处理的试题,微软面试100题系列,涵盖2011、2012、2013、2014各大校招笔试面试题,34,3本书,编程之美,剑指offer；,Cracking the Coding Interview:150 Programming Questions and Solutions,顺便贴个此本书的题解：the Coding Interview:150 Programming Questions and Solutions,顺便贴个此本书的题解：