百度软件工程师面试题大全(3)

　　这样可以做到O(n)的时间复杂度和O(n)的空间复杂度，满足题目的要求。

　　但是没有利用“一个数出现的次数超过了一半”这个特点。也许算法还有提高的空间。

　　答案2：

　　使用两个变量A和B，其中A存储某个数组中的数，B用来计数。开始时将B初始化为0。

　　遍历数组，如果B=0，则令A等于当前数，令B等于1;如果当前数与A相同，则B=B+1;如果当前数与A不同，则令B=B-1。遍历结束时，A中的数就是要找的数。

　　这个算法的时间复杂度是O(n)，空间复杂度为O(1)。

　　13、找出被修改过的数字

　　n个空间(其中n<1M)，存放a到a+n-1的数，位置随机且数字不重复，a为正且未知。现在第一个空间的数被误设置为-1。已经知道被修改的数不是最小的。请找出被修改的数字是多少。

　　例如：n=6，a=2，原始的串为5,3,7,6,2,4。现在被别人修改为-1,3,7,6,2,4。现在希望找到5。

　　回答：

　　由于修改的数不是最小的，所以遍历第二个空间到最后一个空间可以得到a的值。

　　a到a+n-1这n个数的和是total=na+(n-1)n/2。

　　将第二个至最后一个空间的数累加获得sub_total。

　　那么被修改的数就是total-sub_total。

　　14、设计DNS服务器中cache的数据结构。

　　要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。(题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等)

　　回答：

　　DNS服务器实现域名到IP地址的转换。

　　每个域名的平均长度为25个字节(估计值)，每个IP为4个字节，所以Cache的每个条目需要大概30个字节。

　　总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。(考虑到每秒5000次操作的限制，也只能放在内存中。)

　　可以考虑的数据结构包括hash_map，字典树，红黑树等等。

　　15、找出给定字符串对应的序号。

　　序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…]类似与excel的排列，任意给出一个字符串s=[a-z]+(由a-z字符组成的任意长度字符串)，请问s是序列Seq的第几个。

　　回答：

　　注意到每满26个就会向前进一位，类似一个26进制的问题。

　　比如ab，则位置为26*1+2;

　　比如za，则位置为26*26+1;

　　比如abc，则位置为26*26*1+26*2+3;

　　16、找出第k大的数字所在的位置。写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。

　　答案：

　　先找到第k大的数字，然后再遍历一遍数组找到它的位置。所以题目的难点在于如何最高效的找到第k大的数。

　　我们可以通过快速排序，堆排序等高效的排序算法对数组进行排序，然后找到第k大的数字。这样总体复杂度为O(NlogN)。

　　我们还可以通过二分的思想，找到第k大的数字，而不必对整个数组排序。从数组中随机选一个数t，通过让这个数和其它数比较，我们可以将整个数组分成了两部分并且满足，{x,xx,...,t}<{y,yy,...}。

　　在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。这样我们就可以确定第k大的数字在哪个子数组中。

　　然后我们继续对包含第k大数字的子数组进行同样的划分，直到找到第k大的数字为止。

　　平均来说，由于每次划分都会使子数组缩小到原来1/2，所以整个过程的复杂度为O(N)。

　　17、给40亿个不重复的unsigned int的整数，没排过序的，然后再给几个数，如何快速判断这几个数是否在那40亿个数当中?

　　答案：

　　unsigned int的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存，用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0，然后每处理一个数字就将其对应的bit设置为1。当需要查询时，直接找到对应bit，看其值是0还是1即可。

　　18、在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。

　　回答：

　　不妨假设10G个整数是64bit的。

　　2G内存可以存放256M个64bit整数。

　　我们可以将64bit的整数空间平均分成256M个取值范围，用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后，我们便知道中数在那个范围内出现，以及这个范围内总共出现了多少个整数。

　　如果中数所在范围出现的整数比较少，我们就可以对这个范围内的整数进行排序，找到中数。如果这个范围内出现的整数比较多，我们还可以采用同样的方法将此范围再次分成多个更小的范围(256M=2^28，所以最多需要3次就可以将此范围缩小到1，也就找到了中数)。

　　19、时分秒针在一天之类重合多少次?(24小时)

　　2次

　　而时针和分针重合了22次。

　　20、将多个集合合并成没有交集的集合。

　　给定一个字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaabbbcccdddhhh}，{eeefff}，{ggg}。

　　(1)请描述你解决这个问题的思路;

　　(2)请给出主要的处理流程，算法，以及算法的复杂度

　　(3)请描述可能的改进。

　　回答：

　　集合使用hash_set来表示，这样合并时间复杂度比较低。

　　1、给每个集合编号为0，1，2，3...

　　2、创建一个hash_map，key为字符串，value为一个链表，链表节点为字符串所在集合的编号。遍历所有的集合，将字符串和对应的集合编号插入到hash_map中去。

　　3、创建一个长度等于集合个数的int数组，表示集合间的合并关系。例如，下标为5的元素值为3，表示将下标为5的集合合并到下标为3的集合中去。开始时将所有值都初始化为-1，表示集合间没有互相合并。在集合合并的过程中，我们将所有的字符串都合并到编号较小的集合中去。

原文转自：http://www.ltesting.net