数据结构题目
类型一：数据结构实现
类型二：数据结构应用
类型一：经典算法实现题
类型二：思维益智题
面试 IT 企业的研发岗位，数据结构和算法显然是必考的项目。俺只学过普通的数据结构课程，没读过 STL，也没有过 ACM 的训练和比赛经历，在一开始面对这样类型题目的时候，心里还是十分忐忑的。大大小小几十场面试下来，自己在这方面总算有了一定的心得积累，在此抛砖引玉，以飨读者。
在正式介绍题目和准备方法之前，有两点需要说明，
Google 和 Facebook 这类对算法有很高要求的公司的在线测试我没有参加过（不过在牛人内推帮助下有过面试体验……），这超出了我目前的编码能力范围，网上有不少拿到 Google、Facebook offer 的经验总结文章，可以移步观赏；
前段时间在微博上又看到有人说自己把 leetcode 刷了好几遍，不过一些转发评论者觉得， IT 公司面试中的算法考察没有价值，一来工作里用不太上，二来把程序员素质考察搞成了应试教育，他们认为更重要的是应聘者的工程能力。遇到这样的讨论，我一般喜欢和一把稀泥。若干年前， Google、微软的面试题让大家眼前一亮，觉得能选拔出个性十足的聪明人来，不过随着大家对这类题目的适应，可能选拔出来的人也在趋同，至少很多人都会在面试前用心准备，。没有什么一劳永逸、一成不变的考查方式，毕竟面试是人和人之间的动态“较量”。不要贪恋算法的奇技淫巧，也不要因为题目筛选力度的衰减而否定考察初衷。面试不仅是考验求职者，也同样在考验面试官，如果问的都是老题儿，那本山大叔肯定都会抢答了。
言归正传，以下分数据结构题目、算法题目、开放题目三部分来介绍我在面试中碰到的问题。
数据结构题目
虽然课本由简到繁、由难到易地介绍了诸多数据结构，我在面试中被问到的却还都是基本类型，比如堆栈、队列、链表、二叉树。题目主要有两类，数据结构实现和具体情境下数据结构的应用。
类型一：数据结构实现
实现 java.util.List 中的基础功能；
实现栈，使得 添加、删除、max 操作的复杂度为 O(1)（我脚着好像是不可实现的，想到最好的是添加、删除 O(log)， max 是 O(1)），实现见
同学给出的评论，参考 leetcode 中的，惭愧；
选取任意数据结构实现添加、删除、随机返回三个功能，分析复杂度；
用数组实现队列，各操作的复杂度分析。
类型二：数据结构应用
两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值；
用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环；
如何在语料中寻找频繁出现的字串，分析复杂度（tire树）；
中缀表达式转逆波兰表达式，逆波兰表达式求值；
数据解压缩，3(a4(ab)) -& aababababaababababaabababab；
上上之选当然是看《算法导论》， 和
都算。时间精力不足又想临时抱佛脚，清华大学计算机系邓俊辉老师的
是好选择，也可以看 。注意熟记不同数据结构的不同操作的不同实现方式（比如 ）的复杂度分析，不管面试官给你出的题目是难是易，妥妥儿的会问复杂度。
有过面试经历的企业（BAT、小米、宜信、猿题库、FreeWheel等）当中，还没有谁问过我需要复杂算法（比方说
中的很多知识点）才能解决的问题。我遇到的算法题目大致可以分为两类：
经典算法实现题 快速排序、归并排序、堆排序、KMP算法等都是重点，重要的是代码的正确性，其次是复杂度分析，当然，人家也不都是直接问你怎么实现这个具体算法，而是包装到情境里；
思维益智题 考察你分析问题的能力，大部分可以归结到二分、动态规划、递归上，重要的是思路，其次是尽量低的复杂度，再次是代码的正确性。
下面具体介绍我遇到的两种类型题目中的问题。
类型一：经典算法实现题
实现快速排序、归并排序、堆排序，各排序算法复杂度分析；
实现KMP，解释原理；
迷宫的深度搜索、广度搜索；
写 find 函数，在目标串中匹配模式串（要考虑中文字符的情况）。
类型二：思维益智题
数列中找第 k 大的数字（与快排或堆排序有关）；
两个有序数组，寻找归并排序后数组的中位数/第 k 大数字（与二分有关）；
一维数组，swap 其中的几对数字（每个数字只属于一次 swap 操作），实现查找（与二分有关）；
一个有序数组，其中一个数字发生变异，但不知道变异后会不会影响整体序，如何实现查找；
二维数组，每行递增，每列递增
实现查找；
二维数组，每行递增，每列递增，求第 k 大的数；
任意交换其中的两数，发现并恢复；
寻找字符串中第一个只出现一次的字符；
统计数列中的逆序对（归并排序有关）；
最长公共子串（动态规划有关）；
最大子序列和，；
给定数组，寻找 next big（堆排序有关）；
一维有序数组，经过循环位移后，最小的数出现在数列中间
如果原数组严格递增，如何找这个最小数；
如果原数组严格递增或递减，如何找这个最小数；
如果原数组非严格递增或递减，如何找这个最小数；
数组可能是递增、递减、递减后递增、递增后递减四种情况，递增递减都是非严格的，如果有转折点，返回转折点的值，否则返回-1；
单向网络，起点和终点唯一且连通，寻找那些一旦被删除将导致起点终点无法连通的点；
有序数组寻找和为某数的一对数字；
打印螺旋数组；
打印组合数；
字符数组，统计指定区间内的回文串个数。
不要纠结于是否是最佳思路，要保证能在 10-15 分钟内给出一个解决方案，并分析复杂度；
基础的可以读读
的这本 ，更深入的可以阅读 CSDN 等博客中大牛们写的 ACM 解题报告；
、、、、 等网站择一练手;
在 Github 中有高质量的学习资料，适合系统学习 & 临时抱佛脚
这类开放题目让你自主选择数据结构，主要是考察求职者对于数据结构的特性与使用场景的综合理解，在面对具体应用场景时能否运用已有的数据结构和算法知识提出合理的解决方案。一般来说在这类问题里哈希表的出场率会比较高……例题如下
大数据量的 url log，怎么去重且统计每个 url 的出现次数，复杂度分析；
设计 cache 系统
设计 cache 的接口；
可以用什么数据结构实现；
如何实现可伸缩的容量；
cache 的空间管理策略，比如 cache 哪些条目，何时清理；
cache 系统启动时分配多大的空间，之后按照怎样的策略增大；
设计爬虫；
流媒体播放客户端从多个完全相同的发送方接收视频包，同一发送方的包会按序到达，不同发送方的包则不一定，有可能会丢包，但还是要保证播放流畅度，设计播放客户端的算法。
数据结构和算法的基础知识还是十分重要的，大部分题目的思路来源于此；
训练自己算法复杂度的分析能力，有的时候对复杂度的分析会反过来会帮助你找到更好的算法；
一定量的题目积累很重要，就好像准备高考数学压轴题一样，见识的越多，思路来得越快，当然，前提是你能够不断总结反思。
转载请注明来自36大数据（)： &
除非特别注明，本站所有文章均不代表本站观点。报道中出现的商标属于其合法持有人。请遵守理性，宽容，换位思考的原则。1、100亿个数字找出最大的10个
1、首先一点，对于海量数据处理，思路基本上是确定的，必须分块处理，然后再合并起来。
2、对于每一块必须找出10个最大的数，因为第一块中10个最大数中的最小的，可能比第二块中10最大数中的最大的还要大。
3、分块处理，再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器，每个服务器又有很多的CPU，因此，100亿个数分成100块，每个服务器处理一块，1亿个数分成100块，每个CPU处理一块。然后再从下往上合并。注意：分块的时候，要保证块与块之间独立，没有依赖关系，否则不能完全并行处理，线程之间要互斥。另外一点，分块处理过程中，不要有副作用，也就是不要修改原数据，否则下次计算结果就不一样了。
4、上面讲了，对于海量数据，使用多个服务器，多个CPU可以并行，显著提高效率。对于单个服务器，单个CPU有没有意义呢？
　　也有很大的意义。如果不分块，相当于对100亿个数字遍历，作比较。这中间存在大量的没有必要的比较。可以举个例子说明，全校高一有100个班，我想找出全校前10名的同学，很傻的办法就是，把高一100个班的同学成绩都取出来，作比较，这个比较数据量太大了。应该很容易想到，班里的第11名，不可能是全校的前10名。也就是说，不是班里的前10名，就不可能是全校的前10名。因此，只需要把每个班里的前10取出来，作比较就行了，这样比较的数据量就大大地减少了。
2、寻找热门查询
&&& 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
&&& 假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
必备知识：
&&& 什么是哈希表？
&&& 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
&&& 哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
&&& 而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位（文章第二、三部分，会针对Hash表详细阐述）。
问题解析：
&&& 要统计最热门查询，首先就是要统计每个Query出现的次数，然后根据统计结果，找出Top 10。所以我们可以基于这个思路分两步来设计该算法。
&&& 即，此问题的解决分为以下俩个步骤：
第一步：Query统计
&&& Query统计有以下俩个方法，可供选择：
&&& 1、直接排序法
&&& 首先我们最先想到的的算法就是排序了，首先对这个日志里面的所有Query都进行排序，然后再遍历排好序的Query，统计每个Query出现的次数了。
&&& 但是题目中有明确要求，那就是内存不能超过1G，一千万条记录，每条记录是225Byte，很显然要占据2.55G内存，这个条件就不满足要求了。
&&& 让我们回忆一下数据结构课程上的内容，当数据量比较大而且内存无法装下的时候，我们可以采用外排序的方法来进行排序，这里我们可以采用归并排序，因为归并排序有一个比较好的时间复杂度O(NlgN)。
&&& 排完序之后我们再对已经有序的Query文件进行遍历，统计每个Query出现的次数，再次写入文件中。
&&& 综合分析一下，排序的时间复杂度是O(NlgN)，而遍历的时间复杂度是O(N)，因此该算法的总体时间复杂度就是O(N+NlgN)=O（NlgN）。
&&& 2、Hash Table法
&&& 在第1个方法中，我们采用了排序的办法来统计每个Query出现的次数，时间复杂度是NlgN，那么能不能有更好的方法来存储，而时间复杂度更低呢？
题目中说明了，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash
Table绝对是我们优先的选择，因为Hash Table的查询速度非常的快，几乎是O(1)的时间复杂度。
那么，我们的算法就有了：维护一个Key为Query字串，Value为该Query出现次数的HashTable，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。
&&& 本方法相比算法1：在时间复杂度上提高了一个数量级，为O（N），但不仅仅是时间复杂度上的优化，该方法只需要IO数据文件一次，而算法1的IO次数较多的，因此该算法2比算法1在工程上有更好的可操作性。
3、海量日志数据，提取出某日访问百度次数最多的那个IP
首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。
或者如下阐述（雪域之鹰）：
算法思想：分而治之+Hash
1、IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；
2、可以考虑采用分而治之的思想，按照IP地址的Hash(IP) % 1024值，把海量IP日志分别存储到1024个小文件中，这样，每个小文件最多包含4MB个IP地址；
& & &这里解释一下为什么用Hash(IP)
1024值，如果不用，而直接分类的话，可能会出现这样一种情况，就是有个IP在每个小文件中都存在，而且这个IP并不一定在那个小文件中是数量最多的，那么最终可能选择的结果会有问题，所以这里用了Hash(IP)%1024值，这样的话，通过计算IP的Hash值，相同IP肯定会放到一个文件中，当然了不同的IP的Hash值也可能相同，就存在一个小文件中。
3、对于每一个小文件，可以构建一个IP为key，出现的次数为value的Hash Map，同时记录当前出现次数最多的那个IP地址；
4、可以得到1024个小文件中的出现次数最多的那个IP，再依据常规的排序算法得出总体上出现次数最多的IP。
4、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
思路：首先要求得每个词的频率，1G无法放入内存，需要分成多个小文件，对每个小文件的词进行统计
（1）顺序读取文件，对每个词，可以hash(x)P00(只要不小于1024个文件，是为了保证每个小文件可以放入内存)， 这样被映射为5000个小文件，每个文件大概200K，每个文件最少1250个单词
（2）对于每个小文件，利用hash_map记录每个单词出现的频率，选出频率最大的100个单词（可以用100个元素的最小堆），再生成对应的5000个文件分别包含这100个单词和频率，这分的文件太多了（关于分多少文件有什么准则吗？， 100*16*5000字节 & 1M, 无法放入内存），
（3）对这5000个小文件进行归并排序，选出最大的100个。
&&&&&&&以上也可以将从5000个文件得到的100个数，最后放入100个小文件吧，最后使用100路归并。
5、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
（1）hash映射这10个文件到另外的10个文件中（hash（query）），这是为了让相同的query放入一个文件中
（2）对每个文件进行hash统计，统计出每个单词的频率，然后按照频率进行排序，使用快速/堆/归并都可以。将每个文件的结果，包含query和频率输出到10个文件中。
（3）对这10个文件进行归并排序。
&&&&&&&令因为重复查询比较多，对于所有的查询可以同时放入内存，这样可以将分成的10个文件一次装入内存，进行排序。
6、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
&&&&思路：每个文件的大小5G*64 = 32G，远远大于内存，需要对a，b分别分成小文件
（1）利用一个hash(url)00，分别将a，b文件分别映射成1000个小文件，因为通过相同的映射函数，所以对于a，b，相同的url都在对应的文件中，（a0 vs b0, a1 vs b1等等）
（2）分别比对这1000个对应的小文件，可以通过先将a映射到一个hash表中，然后依次遍历b，判断是否在a中出现，出现过则说明重复
7、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。
思路1：总共大小2.5*10^8*4字节=1G
（1）将这么多整数先hash(val)00分成1000个小文件，相同的数就在相同的文件中
（2）对每个小文件进行hash映射，统计出现次数，然后将对应次数为1的输出。
思路2：采用2-Bitmap(每个数分配2bit, 00表示不存在，01表示出现多次，11无意义)，所有的整数总共需内存2^32次方，2^32 * 2 bit = 1G内存，如果可以存入内存，首先全部置为0， 依次遍历这2.5忆个整数，如果bitmap中是00则变01，01变10， 10保持不变，把01对应的数输出即可。
8、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？&&&&&
思路1：同样采用位图，40忆个不重复的数，每个数用1bit表示，出现或不出现，40*10^8*1 = 0.5G大小。遍历这40忆个数，如果出现将对应位置为1，对于给定的数直接判断位图中对应的值。
思路2：编程珠玑上的一个思路。将每个整数都看成32位的二进制数，从最高位，依次按位来分，按最高位0，1分成两个文件，每个文件数字个数小于20亿，与所要判断的数的最高为进行比较，从而知道去哪个文件继续比较，然后对于选定的文件再按照次高位比较再分成2个文件，再比较判断数对应的位数，依次循环，直到最后一位，就可以找到或判断没有该数了。时间复杂度O（log2n）,因为每次都将数据减少一半，直到最后一个。
9、怎么在海量数据中找出重复次数最多的一个？
思路：hash分成小文件，分别统计每个小文件数据出现次数，找出出现次数最大的，然后在将每个小文件的最大值进行比较，找到最大值，与上面思路一样的。
10、100w个数中找出最大的100个数。
思路1：最小堆，找最大100个数
思路2：快速排序，每次分割之后只考虑比轴大的一部分（快速选择的思想），直到比轴大的一部分比100多时，采用传统排序，取前100个
思路3：选取前100个元素，排序，然后扫描剩余的元素，与排好序的元素中最小的相比，如果比它大，替换，重排前面，这跟堆排序思路一样。
11、5亿个整数找他们的中位数
思路：遍历这个文件，按照数的大小分别放入不同的文件，例如2^16个区域，每个区域大概9000个数的范围，然后统计每个区域的个数，然后就可以计算中位数落入哪个区域，并且可以计算出中位数是这个区域的第几大数，然后求出这个区域的第k个数就可以了。
海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？
&&&&&&&分析：思路其实是一样的，这只不过是分不到了n台电脑上，首先你不能保证一个元素只出现在一台电脑上，所以需要先通过hash映射，遍历所有的数据，对于第一道题，将所有相同的数据映射到同一台机器上，对于第2个问题，每个电脑上存放不同范围的数据，然后再进行统计，第1道题就可以用前面题的思路，对于找出每台机子的前10个数，然后再统计这些数，找到top10,
第2道题，统计每台机子数的个数，找出中位数所在机子，并计算出中位数是这个机子的第几个就找到了。&
&&&&&&&&总结：这些海量数据处理的题，思路基本差不多，首先是hash映射，成为不同类型的文件,然后hash统计，之后进行排序等等。以下是july总结的，以上也是参考其中博客整理一些思路的产物。。：
分而治之/hash映射 + hash统计 + 堆/快速/归并排序（频率最高，最大等）；
双层桶划分（中位数， 不重复数）：本质上还是分而治之的思想，重在&分&的技巧上！适用范围：第k大，中位数，不重复或重复的数字基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行
Bloom filter/Bitmap（可以用来实现数据字典，进行数据的判重，或者集合求交集，不重复数）；
Trie树（数据量大，重复多，但是数据种类小可以放入内存）/数据库（适用范围：大数据量的增删改查）/倒排索引（适用范围：搜索引擎，关键字查询）；
外排序：大数据排序，去重，外部排序的归并算法，置换选择败者树原理，最优归并数
分布式处理之Hadoop/Mapreduce：数据量大，但数据种类小可以放入内存，将数据交给不同的机器去处理，数据划分，结果规约
阅读(...) 评论()