XXXX第3次面试算法讲座课件

2013第3次面试&算法讲座July18:00-21:30北理工二零一三年十月二十七日12013第3次面试&算法讲座1你最大的资本是什么？22你最大的资本就是你的自信!33So，keeprelaxed，havefun!44第一部分2014校招梳理5第一部分52014校招热点2014校招笔试面试题集锦下面试题前的题号对应上文中的题号62014校招热点2014校招笔试面试题集锦6总体思路笔试偏基础涵盖语言，计算机组成原理、操作系统、网络协议、数据库、概率期望等知识面试偏算法且极具针对性的根据简历提问无论是笔试还是面试，两者都很看重你的实际编程能力7总体思路笔试偏基础7笔面关键基础coding能力算法8笔面关键8三者关系有基础和一定的coding能力，再谈算法。既然要参加笔试面试，那么便是想进公司上班在公司内，没有一定的coding能力，之前可能再华丽的研究也只是建立在一片废墟上，根基不牢，理想大厦随时可能会轰然倒塌。9三者关系有基础和一定的coding能力，再谈算法。9百考不厌的基础题TCP建立连接的三次握手死锁的条件线程与进程的区别指针与引用的区别C++内存分配堆、栈、自由存储区、全局/静态存储区，常量存储区sizeof字节大小/虚拟函数各排序算法的时间复杂度-快速排序、堆排、归并排序等Java中hashtable与hashmap的区别HashMap基于Hashtable实现，不同之处在于HashMap是非同步的，并且允许null，即nullvalue和nullkey，Hashtable则不允许null动态链接库与静态链接库的区别10百考不厌的基础题10面试中手写code的能力极为重要1111算法字符串处理字符串翻转、匹配字符串库函数的编写最长公共子串、子序列基于各种数据结构链表、数组、树、hash表二分查找动态规划海量数据处理数理逻辑经典问题变形系统设计数据挖掘、机器学习12算法字符串处理12时间复杂度不断优化，不断精简13时间复杂度不断优化，不断精简13字符串处理字符串翻转微软面试100题第10题、翻转句子中单词的顺序，例如输入“Iamastudent.”，则输出“student.aamI”。编程艺术第1章、字符串的左旋转操作，如把字符串abcdef左旋转2位得到字符串cdefab，要求时间O(n)，空间O(1)。18、在原字符串中把尾部m个字符移动到字符串的头部，如原字符串为”Ilovebaofeng”，m=7，输出结果：”baofengIlove”。34、设计一个反转字符串的函数char*reverse_str(char*str),不使用系统函数。14字符串处理字符串翻转14字符串库函数编写字符串库函数3、已知memcpy的函数为：void*memcpy(void*dest,constvoid*src,size_tcount)其中dest是目的指针，src是源指针，请实现memcpy。22、写一个memmove的函数15、字符串转换为整数，实现atoi的22、实现C的strstr-功能：从字符串str1中查找是否有字符串str2，-如果有，从str1中的str2位置起，返回str1中str2起始位置的指针，如果没有，返回null。15字符串库函数编写字符串库函数15字符串中的串中串最长公共子序列不要求连续最长公共子串要求连续16字符串中的串中串168分钟手写memcpy178分钟手写memcpy171818其它数据结构数组、图链表翻转遍历、查找、插入、删除合并有环无环，有无相交树查找、遍历最近公共祖先高级树：AVL树、红黑树、B树、B+树等set、maphash表如何构造hash函数如何避免冲突hashset、hashmap19其它数据结构数组、图19二分查找二分查找相关请实现二分查找5&8、杨氏矩阵查找杨氏矩阵变形给定n*n的实数杨氏矩阵，求这n^2个数的中位数20二分查找2021动态规划适用条件最优子结构+重叠子问题例子11、输入两个整数n和sum，从数列1，2，3.......n中随意取几个数,使其和等于sum,要求将其中所有的可能组合列出来。 list1.push_front(n);//典型的01背包问题find_factor(sum-n,n-1);//放n，n-1个数填满sum-nlist1.pop_front();find_factor(sum,n-1);//不放n，n-1个数填满sum2121动态规划适用条件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*10^6B=50M，而内存只有1M，故干脆搞一个hash函数%50，分解成50个小文件；②针对对每个小文件依次运用hashmap(key，value)完成每个key的value次数统计，后用堆找出每个小文件中value次数最大的top10；③最后依次对每两小文件的top10归并，得到最终的top10。细节很重要。hash映射+hashmap+堆&归并2331、有100W个关键字，长度小于等于50字节。用高效的算法数理逻辑纯粹考智力1、一个桶里面有白球、黑球各100个，现在按下述规则取球：每次从通里面拿出来两个球；i、如果取出的是两个同色的求，就再放入一个黑球；ii、如果取出的是两个异色的求，就再放入一个白球。问：最后桶里面只剩下一个黑球的概率是多少？6.1、宿舍内5个同学一起玩对战游戏。每场比赛有一些人作为红方，另一些人作为蓝方。请问至少需要多少场比赛，才能使任意两个人之间有一场红方对蓝方和蓝方对红方的比赛？12、24数理逻辑纯粹考智力24快排partition的变形三色球问题22、相同的球放到一起，让你按顺序输出红白蓝三种颜色的球，可以用012来表示，要求只能扫描一次数组将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗25快排partition的变形三色球问题25三色球问题思路类似快排中partition过程，用三个指针，一前begin，一中current，一后end，俩俩交换。current遍历，整个数组序列，current指1不动，current指0，与begin交换，而后current++，begin++，current指2，与end交换，而后，current不动，end--。快排中的partition过程？26三色球问题思路类似快排中partition过程，用三个指针，三色球解决步骤127三色球解决步骤127三色球解决步骤228三色球解决步骤228子数组最大和的变形36、输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。i)一维：输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。ii)二维：29子数组最大和的变形36、输入一个整形数组，数组里有正数也有负iii)子数组”并不只是一个二维数组或矩形，而是联通的元素(上下或左右相邻即视为联通)iv)如果是个轮胎呢？30iii)子数组”并不只是一个二维数组或矩形，而是联通的元素系统设计合适的数据结构+算法输入“结构之”，会提示“结构之法”，“结构之法算法之道”等搜索词31系统设计合适的数据结构+算法31第二部分资料推荐32第二部分32准备资料3个系列3本书一个讲座3个网站/论坛一个微信公众账号33准备资料333个系列程序员编程艺术从最容易想到的思路开始讲起，一步步优化而不是其它题解那样一上来就给你所谓的标准速成答案，面试亦如此秒杀99%的海量数据处理面试题涵盖腾讯、百度、阿里巴巴等公司最喜欢考的关于海量数据处理的试题微软面试100题系列涵盖2011、2012、2013、2014各大校招笔试面试题343个系列程序员编程艺术343本书《编程之美》《剑指offer》；《CrackingtheCodingInterview:150ProgrammingQuestionsandSolutions》顺便贴个此本书的题解：/posts/ctci-solutions-contents.html其它编程珠玑算法导论深入理解计算机系统深度探索C++对象模型353本书353本书《编程之美》《剑指offer》；《CrackingtheCodingInterview:150ProgrammingQuestionsandSolutions》顺便贴个此本书的题解：/posts/ctci-solutions-contents.html其它编程珠玑算法导论深入理解计算机系统深度探索C++对象模型363本书36一个讲座37373个网站/论坛383个网站/论坛38一个微信公众账号待字闺中39一个微信公众账号39第三部分谈谈几个轻松的话题40第三部分40有没有搞错，offer太多？选择哪个offer去A做什么，去B做什么？你更喜欢做什么？哪个公司更适合做这个？创始人的特征（不一定对）商人出身：赚的钱可能多点技术出身：给的尊重可能多点41有没有搞错，offer太多？选择哪个offer41程序员求职俱乐部为什么要成立club？网友说：找工作，找妹子/帅哥，找基友，码农三大需求July说：互帮互助，帮助彼此让更多人都能顺利找到工作形式：办讲座，或交流讨论会时间：每月定期举行成员：正找工作已有offer愿分享经验已上班能内推意义：我的存在能为社会带来什么价值我能为他人带来什么帮助？42程序员求职俱乐部为什么要成立club？42算法公开课内容堆排、快排hash表、二分查找、二叉查找树红黑树、B树/B+树/B*树、R树、Trie树、后缀树贪心算法、动态规划DFS、BFS、最小生成树、Dijkstra微积分、矩阵、概率论与数理统计、最优化决策树、贝叶斯、SVM、神经网络问题：需要找几个老师一起讲？推荐或自荐，ACMer，乐于分享谁愿意帮忙申请教室？时间：11月开始43算法公开课内容43thankyou中场休息10分钟4444演讲完毕，谢谢观看！演讲完毕，谢谢观看！2013第3次面试&算法讲座July18:00-21:30北理工二零一三年十月二十七日462013第3次面试&算法讲座1你最大的资本是什么？472你最大的资本就是你的自信!483So，keeprelaxed，havefun!494第一部分2014校招梳理50第一部分52014校招热点2014校招笔试面试题集锦下面试题前的题号对应上文中的题号512014校招热点2014校招笔试面试题集锦6总体思路笔试偏基础涵盖语言，计算机组成原理、操作系统、网络协议、数据库、概率期望等知识面试偏算法且极具针对性的根据简历提问无论是笔试还是面试，两者都很看重你的实际编程能力52总体思路笔试偏基础7笔面关键基础coding能力算法53笔面关键8三者关系有基础和一定的coding能力，再谈算法。既然要参加笔试面试，那么便是想进公司上班在公司内，没有一定的coding能力，之前可能再华丽的研究也只是建立在一片废墟上，根基不牢，理想大厦随时可能会轰然倒塌。54三者关系有基础和一定的coding能力，再谈算法。9百考不厌的基础题TCP建立连接的三次握手死锁的条件线程与进程的区别指针与引用的区别C++内存分配堆、栈、自由存储区、全局/静态存储区，常量存储区sizeof字节大小/虚拟函数各排序算法的时间复杂度-快速排序、堆排、归并排序等Java中hashtable与hashmap的区别HashMap基于Hashtable实现，不同之处在于HashMap是非同步的，并且允许null，即nullvalue和nullkey，Hashtable则不允许null动态链接库与静态链接库的区别55百考不厌的基础题10面试中手写code的能力极为重要5611算法字符串处理字符串翻转、匹配字符串库函数的编写最长公共子串、子序列基于各种数据结构链表、数组、树、hash表二分查找动态规划海量数据处理数理逻辑经典问题变形系统设计数据挖掘、机器学习57算法字符串处理12时间复杂度不断优化，不断精简58时间复杂度不断优化，不断精简13字符串处理字符串翻转微软面试100题第10题、翻转句子中单词的顺序，例如输入“Iamastudent.”，则输出“student.aamI”。编程艺术第1章、字符串的左旋转操作，如把字符串abcdef左旋转2位得到字符串cdefab，要求时间O(n)，空间O(1)。18、在原字符串中把尾部m个字符移动到字符串的头部，如原字符串为”Ilovebaofeng”，m=7，输出结果：”baofengIlove”。34、设计一个反转字符串的函数char*reverse_str(char*str),不使用系统函数。59字符串处理字符串翻转14字符串库函数编写字符串库函数3、已知memcpy的函数为：void*memcpy(void*dest,constvoid*src,size_tcount)其中dest是目的指针，src是源指针，请实现memcpy。22、写一个memmove的函数15、字符串转换为整数，实现atoi的22、实现C的strstr-功能：从字符串str1中查找是否有字符串str2，-如果有，从str1中的str2位置起，返回str1中str2起始位置的指针，如果没有，返回null。60字符串库函数编写字符串库函数15字符串中的串中串最长公共子序列不要求连续最长公共子串要求连续61字符串中的串中串168分钟手写memcpy628分钟手写memcpy176318其它数据结构数组、图链表翻转遍历、查找、插入、删除合并有环无环，有无相交树查找、遍历最近公共祖先高级树：AVL树、红黑树、B树、B+树等set、maphash表如何构造hash函数如何避免冲突hashset、hashmap64其它数据结构数组、图19二分查找二分查找相关请实现二分查找5&8、杨氏矩阵查找杨氏矩阵变形给定n*n的实数杨氏矩阵，求这n^2个数的中位数65二分查找2066动态规划适用条件最优子结构+重叠子问题例子11、输入两个整数n和sum，从数列1，2，3.......n中随意取几个数,使其和等于sum,要求将其中所有的可能组合列出来。 list1.push_front(n);//典型的01背包问题find_factor(sum-n,n-1);//放n，n-1个数填满sum-nlist1.pop_front();find_factor(sum,n-1);//不放n，n-1个数填满sum6621动态规划适用条件21海量数据处理hash函数映射+hashmap统计+堆排26、单机5G内存，磁盘200T的数据，分别为字符串，然后给定一个字符串，判断这200T数据里面有没有这个字符串，怎么做？如果查询次数会非常的多,怎么预处理？31、有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。42、假设已有10w个敏感词，现给你50个单词，查询这50个单词中是否有敏感词。67海量数据处理hash函数映射+hashmap统计+堆31、有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。①先把100W个关键字hash映射到小文件，根据题意，100W*50B=50*10^6B=50M，而内存只有1M，故干脆搞一个hash函数%50，分解成50个小文件；②针对对每个小文件依次运用hashmap(key，value)完成每个key的value次数统计，后用堆找出每个小文件中value次数最大的top10；③最后依次对每两小文件的top10归并，得到最终的top10。细节很重要。hash映射+hashmap+堆&归并6831、有100W个关键字，长度小于等于50字节。用高效的算法数理逻辑纯粹考智力1、一个桶里面有白球、黑球各100个，现在按下述规则取球：每次从通里面拿出来两个球；i、如果取出的是两个同色的求，就再放入一个黑球；ii、如果取出的是两个异色的求，就再放入一个白球。问：最后桶里面只剩下一个黑球的概率是多少？6.1、宿舍内5个同学一起玩对战游戏。每场比赛有一些人作为红方，另一些人作为蓝方。请问至少需要多少场比赛，才能使任意两个人之间有一场红方对蓝方和蓝方对红方的比赛？12、69数理逻辑纯粹考智力24快排partition的变形三色球问题22、相同的球放到一起，让你按顺序输出红白蓝三种颜色的球，可以用012来表示，要求只能扫描一次数组将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。这个问题之所以叫荷兰国旗，是因为我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗70快排partition的变形三色球问题25三色球问题思路类似快排中partition过程，用三个指针，一前begin，一中current，一后end，俩俩交换。current遍历，整个数组序列，current指1不动，current指0，与begin交换，而后current++，begin++，current指2，与end交换，而后，current不动，end--。快排中的partition过程？71三色球问题思路类似快排中partition过程，用三个指针，三色球解决步骤172三色球解决步骤127三色球解决步骤273三色球解决步骤228子数组最大和的变形36、输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。i)一维：输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。ii)二维：74子数组最大和的变形36、输入一个整形数组，数组里有正数也有负iii)子数组”并不只是一个二维数组或矩形，而是联通的元素(上下或左右相邻即视为联通)iv)如果是个轮胎呢？75iii)子数组”并不只是一个二维数组或矩形，而是联通的元素系统设计合适的数据结构+算法输入“结构之”，会提示“结构之法”，“结构之法算法之道”等搜索词76系统设计合适的数据结构+算法31第二部分资料推荐77第二部分32准备资料3个系列3本书一个讲座3个网站/论坛一个微信公众账号78准备资料333个系列程序员编程艺术从最容易想到的思路开始讲起，一步步优化而不是其它题解那样一上来就给你所谓的标准速成答案，面试亦如此秒杀99%的海量数据处理面试题涵盖腾讯、百度、阿里巴巴等公司最喜欢考的关于海量数据处理的试题微软面试100题系列涵盖2011、2012、2013、2014各大校招笔试面试题793个系列程序员编程艺术343本书《编程之美》《剑指offer》；《