2013第3次面试算法讲座byJuly.ppt

1,2013第3次面试/典型的01背包问题find_factor(sum-n,n-1);/放n，n-1个数填满sum-nlist1.pop_front();find_factor(sum,n-1);/不放n，n-1个数填满sum,22,海量数据处理,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*106B=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，俩俩交换。current遍历，整个数组序列，current指1不动，current指0，与begin交换，而后current+，begin+，current指2，与end交换，而后，current不动，end-。快排中的partition过程？,27,三色球解决步骤1,28,三色球解决步骤2,29,子数组最大和的变形,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个网站/论坛一个微信公众账号,34,3个系列,程序员编程艺术从最容易想到的思路开始讲起，一步步优化而不是其它题解那样一上来就给你所谓的标准速成答案，面试亦如此秒杀99%的海量数据处理面试题涵盖腾讯、百度、阿里巴巴等公司最喜欢考的关于海量数据处理的试题微软面试100题系列涵盖2011、2012、2013、2014各大校招笔试面试题,35,3本书,编程之美剑指offer；CrackingtheCodingInterview:150ProgrammingQuestionsandSolutions顺便贴个此本书的题解：,36,3本书,编程之美剑指offer；CrackingtheCodingInterview:150ProgrammingQuestionsandSolutions顺便贴个此本书的题解：,37,一个讲座,38,3个网站/论坛,一个刷面试题的leetcode,39,一个微信公众账号,待字闺中,40,第三部分,谈谈几个轻松的话题,41,有没有搞错，offer太多？,选择哪个offer去A做什么，去B做什么？你更喜欢做什么？哪个公司更适合做这个？创始人的特征（不一定对）商人出身：赚的钱可能多点技术出身：给的尊重可能多点,42,程序员求职俱乐部,为什么要成立club？网友说：找工作，找妹子/帅哥，找基友，码农三大需求July说：互帮互助，帮助彼此让更多人都能顺利找到工作形式：办讲座，或交流讨论会时间：每月定期举行成员：正找工作已有offer愿分享经验已上班能内推意义：我的存在能为社会带来什么价值我能为他人带来什么帮助？,43,算法公开课,内容堆排、快排hash表、二分查找、二叉查找树红黑树、B树/B+树/B*树、R树、Trie树、后缀树贪心算法、动态规划DFS、BFS、最小