百度面试算法题

1.代码编译过程

  1. 在cpp文件中展开include文件。
  2. 将每个cpp文件编译为一个对应的obj文件。
  3. 连接obj文件成为一个exe文件(或者其它的库文件)

2.100W个整数中求最小的k个数,有哪些方法,优缺点

快速排序: 分区时,根据数P将数组分为两部分,设大于P的数个数为a,小于P的数的个数为b。如果,a>=k,则从这a个数取最大的k个数,若a<k,则从b个数取最大的k-a-1个。

3.两个10G的文件中,求含有相同整数,有哪些方法,优缺点

(1)快排+二分查找 (2)位图法

位图法的应用

1、给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中   首先,将这40亿个数字存储到bitmap中,然后对于给出的数,判断是否在bitmap中即可。

2、使用位图法判断整形数组是否存在重复       遍历数组,一个一个放入bitmap,并且检查其是否在bitmap中出现过,如果没出现放入,否则即为重复的元素。

3、在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这2.5亿个整数       参 考的一个方法是:采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)。其实,这里可以使用两个普 通的Bitmap,即第一个Bitmap存储的是整数是否出现,如果再次出现,则在第二个Bitmap中设置即可。这样的话,就可以使用简单的1- Bitmap了。

hash_map:

其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。  但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。  hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。

其插入过程是:

1. 得到key

2. 通过hash函数得到hash值

3. 得到桶号(一般都为hash值对桶数求模)

4. 存放key和value在桶内。

其取值过程是:

1. 得到key

2. 通过hash函数得到hash值

3. 得到桶号(一般都为hash值对桶数求模)

4. 比较桶的内部元素是否与key相等,若都不相等,则没有找到。

5. 取出相等的记录的value。  hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当许多桶内没有值时,许多查询就会更快了(指查不到的时候).  由此可见,要实现哈希表, 和用户相关的是:hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。

有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

方案1:顺序读文件中,对于每个词x,取,然后按照该值存到5000个小文件(记为)中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,知道分解得到的小文件的大小都不超过1M。对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100词及相应的频率存入文件,这样又得到了5000个文件。下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。

海量日志数据,提取出某日访问百度次数最多的那个IP。

方案1:首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。

4.僵尸进程产生的原因及解决方式:

如果子进程先于父进程退出, 同时父进程又没有调用wait/waitpid,则该子进程将成为僵尸进程。通过ps命令,我们可以看到该进程的状态为Z(表示僵死)。

一般,为了防止产生僵尸进程,在fork子进程之后我们都要wait它们;同时,当子进程退出的时候,内核都会给父进程一个SIGCHLD信号,所以我们可以建立一个捕获SIGCHLD信号的信号处理函数,在函数体中调用wait(或waitpid),就可以清理退出的子进程以达到防止僵尸进程的目的。

给你一个长度为N的链表。N很大,但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个,且它们是完全随机的(出现概率均等)。

解:先选中前k个, 从第k+1个元素到最后一个元素为止, 以k/i (i=k+1, k+2,...,N)的概率选中第i个元素,并且随机替换掉一个原先选中的元素,这样遍历一次得到k个元素, 可以保证完全随机选取。这个算法叫做蓄水池抽样

有20个数组,每个数组里面有500个数组,降序排列,每个数字是32位的unit,求出这10000个数字中最大的500个。

将 20 个数组合并为 1 个,挨着连接起来即可,不必保证有序。在合并的数组中随机选取一个元素,然后将所有小于此元素的元素放在其左侧,大于到右侧。完成操作后,如果原来被选中的元素刚好处在右数第 500 的位置,那从它开始向右的元素即为所求。否则,如果右端元素数目大于 500,则对右端序列递归使用此方法;否则,如果左端序列数目大于 10000-500,则对左端序列递归使用此方法。复杂度 expected O(n)

在一个数组中除两个数字只出现1次外,其它数字都出现了2次, 要求尽快找出这两个数字。

位操作方法

单链表:

找出单链表的倒数第4个元素:建立两个指针,第一个先走4步,然后第2个指针也开始走,两个指针步伐(前进速度)一致。

从无头单链表中删除节点:这里采用了“移花接木”的方法。设该节点为B,下一个节点为C。那么,首先将B节点的内容替换为C节点的内容,然后,将C节点删除

判断两个链表是否相交并找出交点:先遍历第一个链表到他的尾部,然后将尾部的next指针指向第二个链表(尾部指针的next本来指向的是null)。这样两个链表就合成了一个链表,判断原来的两个链表是否相交也就转变成了判断新的链表是否有环的问题了

找出带环链表中环的起点:用两个步长分别为1和2的指针遍历链表,直到两者相遇,此时慢指针走过的长度就是环的长度。另外相遇后把其中指针重新设定为起始点,让两个指针以步长1再走一遍链表,相遇点就是环的起始点。

单链表反序,并返回新链表的头指针:

1. struct ListNode *reverseList(struct ListNode *head)

2. {

3.     struct ListNode *newHead = NULL;

4.     struct ListNode *tmp = NULL;

5.     while(head != NULL)

6.     {

7.         tmp = head;

8.         head = head -> next;

9.         tmp->next = newHead;

10.         newHead = tmp;

11.     }

12.     return newHead;

13. }

栈问题:

如何用一个数组实现两个栈:分别用数组的两端作为两个栈的起点,向中间扩展,两个栈中的元素总和不超过n时,两个栈不会相遇。

二叉树:

找出二叉树上任意两个结点的最近共同父结点:首先数一下两个结点的深度,然后比较深的那个往上走(深-浅)步,最后同时往上走,肯定会命中最近共同父节点的。如果你把二叉树的所有节点看成N的话,我这个算法只需要lg(N)就可以搞定了

在二叉树中找出和为某一值的所有路径:到达一个节点之后计算当前节点和sum的和,如果为target,输出路径返回,如果大于target,则直接返回,如果小于,则将当前节点的值入栈,更新sum的值,继续遍历,遍历完成之后,也就是从当前节点返回的时候,将其从栈中弹出,更新sum

时间: 05-12

百度面试算法题的相关文章

一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等.由于时间仓促,加之面试时头昏脑涨,这道题没做出来甚至没有给出思路,这让我多少有些遗憾和不甘.因为最近接触算法的东西较多而且本身对算法感兴趣,所以回家之后绞尽脑汁想把这题做出来.其实刚看到这题时感觉不难,但是因为数字个数及数值的不确定,我感觉这题越想越难.昨天一晚上没有睡好,甚至做梦都在想这题! 今天上午在多个群里问了这题,都没有给出思路,真是绝望至极.很多人都说 n/3 的思路,其实这种思路一开始就是死胡同.本人属于那种不会

面试算法题:爬楼梯,N级楼梯有多少种走法?

By Long Luo 个人博客链接 最近去面试时,在一家小公司面试时,公司小BOSS给我出了一道算法题: 一个人爬楼梯,一步可以迈一级,二级,三级台阶,如果楼梯有N级,要求编写程序,求总共有多少种走法. 这个问题应该是一个很老的题目了,用中学数学来说,就是一个排列组合问题.当时拿到这个题目之后,首先想到使用递归的思想去解决这个问题: N级楼梯问题可以划分为:N-1级楼梯,N-2级楼梯,N-3级楼梯的走法之和. 先计算下0,1,2,3及楼梯有多少种走法: 1 --> 1 2 --> 11 2

常考面试算法题之暴力枚举

结合2017春招和秋招真题,以下几类算法题最常考,汇总了一下: 好多鱼! 牛牛有一个鱼缸.鱼缸里面已经有n条鱼,每条鱼的大小为fishSize[i] (1 ≤ i ≤ n,均为正整数),牛牛现在想把新捕捉的鱼放入鱼缸.鱼缸内存在着大鱼吃小鱼的定律.经过观察,牛牛发现一条鱼A的大小为另外一条鱼B大小的2倍到10倍(包括2倍大小和10倍大小),鱼A会吃掉鱼B.考虑到这个,牛牛要放入的鱼就需要保证: 1.放进去的鱼是安全的,不会被其他鱼吃掉 2.这条鱼放进去也不能吃掉其他鱼 鱼缸里面已经存在的鱼已经相

远景面试算法题——FolderSize

描述 文件被存储在磁盘上的时候,通常为cluster方式.每个cluster具有固定的大小,一个文件所消耗的空间量始终是cluster大小的整数倍.因此,如果cluster的大小为100字节,165字节的文件将会使用实际使用200字节的存储空间,造成35个空间的浪费. 一个folder会有多个file,每个file单独计算浪费空间:如果某个folder没有出现,浪费空间为0 定义 Method signature: int[] calculateWaste(String[] files, int

偶然看到的面试算法题_最短时间找出十包粉末中的两蓝粉末。

题目:有4个杯子,10包粉末,其中有2包溶于水变蓝,其余无色,粉末溶于水2min才能显现颜色.求找出两包蓝色粉末的最短时间.假设水和粉末用不完. 解:以下给出四种解法,标记10包粉末为(1,2 ... ) 杯子为[1,2,3,4]首先我想会不会是有某种算法,dp 二分..@[email protected]..没有,懵懵的. 法一:这是我最初想到的比较傻的方法 第一趟:[12,34,56,78] 每个杯子分别放两包加水融化,剩下两包不管.可能的情况: (1)0个杯子变色,说明剩下两包就是蓝粉末

实习生面试--算法题之一

题目:在整型数中只有1位是1,求1在整型数中的位置? 通常,面试者给的答案是一位一位的右移,并判断是否移位后的值是1,如果是1,输出被移位的位数就是我们要的答案了. 但是这并不是最优的答案,时间复杂度是O(n).那么更好的算法是什么样的呢,其实我们可以采用二分法更高效的解决本问题,时间复杂度是O(logn). 下面给出代码,并测试时间消耗. 算法1 1 int scan(unsigned int value) 2 { 3 int len = sizeof (unsigned int) * 8;

[面试算法题重做]翻转句子中单词的顺序

话说工作中算法用的真的多么?????? 虽然工作中用不到,但是你总得换工作吧,防不住笔试面试中问你些这么个玩意. 而且,多思考,有助于活跃头脑了.深深扎入项目中童鞋们还可以活跃活跃,防止生锈. 话不多说,题目如下: 题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变.句子中单词以空格符隔开.为简单起见,标点符号和普通字母一样处理. 例如输入“I am a student.”,则输出“student. a am I”. 在何海涛的日记中,分析方法是 先颠倒句子中的所有字符.这时,

实习生面试--算法题之字符串最长公共子序列长度

题目:求两字符串的最长公共子序列的长度. 题外话:最长公共子串,子序列问题是被充分讨论的问题,网上一搜一大把,请bing之. 本题只要求求最长公共子序列的长度,而不需要记录最长的公共子序列,给予了我们便利,请参考代码: 1 int max(int a, int b) 2 { 3 return a > b ? a : b; 4 } 5 6 int lcs(char* str1, char* str2) 7 { 8 if (str1 == nullptr || str2 == nullptr) 9

C++经典面试算法题

转自:http://blog.csdn.net/f_r_e_e_x/article/details/50770907 1 //1.实现strcpy. 2 char* MyStrCpy( char *pDest, const char *pSrc ) 3 { 4 if( nullptr == pDest || nullptr == pSrc ) 5 { 6 return nullptr; 7 } 8 if( pDest == pSrc ) 9 { 10 return pDest; 11 } 12