XXXX第3次面试算法讲座_byJuly

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