计算机专业求职面试问题

1 / 19 计算机专业求职面试问题 计算机专业求职面试问题 1、线形表 a、 b 为两个有序升序的线形表，编写一程序，使两个有序线形表合并成一个有序升序线形表 h； 2、运用四色定理，为 色为 1、2、 3、 4四种，另有数组 N，如 ij=1 则表示i 区域与 j 区域相邻，数组 ，如 i=1,表示i 区域的颜色为 1 号颜色。 3、用递归算法判断数组 aN是否为一个递增数组。 4、编写算法，从 10亿个浮点数当中，选出其中最大的 10000 个。 5、编写一 止僵尸进程的出现 . 同学的 4道题，应聘的职位是搜索引擎工程师，后两道超级难，（希望大家多给一些算发） 有一动态开辟的内存，求交集，把交集放到动态内存 且返回交集个数 a,b,) a -z26 个字母插入到连表中，并且倒 叙，还要打印！ 2 / 19 象搜索的输入信息是一个字符串，统计 300 万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过 255存使用只有 1G, 请描述思想，写出算发（ 空间和时间复杂度， 几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（ 空间和时间复杂度， 时间问题，我不发代码了，但这些问题书上都有，我给你说一下书名 1、线形表 a、 写一程序，使两个有序线形表合并成一个有序升序线形表 h； 答案在 请化大学 严锐敏数据结构第二版第二章例题（有错字不好意思 下同） 2、运用四色定理，为 色为 1、2、 3、 4四种，另有数组 N，如 ij=1 则表示i 区域与 j 区域相邻，数组 ，如 i=1,表示i 区域的颜色为 1 号颜色。 答案在 中国水利出版社 引进的一套国外数据结构教材上，单兰色的封皮（这套书包括操作系 统（利用的多媒体都有，估计有年岁了） 3、用递归算法判断数组 aN是否为一个递增数组。 这个我没在教才上看到过 但不难！ 3 / 19 一会贴代码 4、编写算法，从 10亿个浮点数当中，选出其中最大的 10000 个。 用外部排序，在数据结构书上有！ 5、编写一 止僵尸进程的出现 . 你说的 僵尸进程 是死锁吗？ 序我不会 有一动态开辟的内存，求交集，把交集放到动态内存 且返回交集个数 a,b,) 这个我没在教才上看到过 但不难！ 一会贴代码 a -z26 个字母插入到连表中，并且倒叙，还要打印！ 这个有点读不懂 象搜索的输入信息是一个字符串，统计 300 万输入信息中的最热门的前十条，我们每次输入的一个字符 串为不超过 255存使用只有 1G, 请描述思想，写出算发（ 空间和时间复杂度， 的确可怕， 4 / 19 几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最好，请描述思想，写出算发（ 空间和时间复杂度 . 的确可怕， 1、线形表 a、 写一程序，使两个有序线形表合并成一个有序升序 二路归并 ,不难 2、运用四色定理，为 色为 1、2、 3、 4四种，另有数组 N，如 ij=1 则表示i 区域与 j 区域相邻，数组 ，如 i=1,表示i 区域的颜色为 1 号颜色。 可转化位图论问题 ,将各个区域视为图上的点 ,相邻的点之间连上一条线 ,构成一个无向图 ,可得其邻接矩阵 ,根据邻接矩阵得色数 . 3、用递归算法判断数组 aN是否为一个递增数组。 楼上有正解 4、编写算法，从 10亿个浮点数当中，选出其中最大的 10000 个。 用快排 0亿个浮点数当中选出第 10000大 的数 ,设位 M,在选 M 位基值 ,利用一趟快速排序 ,M 之后的数即为所求 . 有一动态开辟的内5 / 19 存，求交集，把交集放到动态内存 且返回交集个数 a,b,) 我想到的是蛮力法 , 时间复杂度位O(想必大家都知道了 ! a -z26 个字 母插入到连表中，并且倒叙，还要打印！ 在创建单链表的时候使之逆序 ,不难 . 象搜索的输入信息是一个字符串，统计 300 万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过 255存使用只有 1G, 请描述思想，写出算发（ 空间和时间复杂度， 25500 万 注 :法受 看不到源代码 . 1、线形表 a、 写一程序，使两个有序线形表 合并成一个有序升序线形表 h； 已知： a0 b0 一、 an 二、 bn 三、插入排序 &二分排序 # # 6 / 19 i,j,k; h20; a10=2,5,6,9,11,24,56,78,80,81; b10=1,3,8,7,10,21,32,45,65,79; i=0; j=0; k=0;k if(aibj) hk=bj;j+; hk=ai;i+; i=0;i %d ,hi); ; /单连表的建立，把 a -z26 个字母插入到连表中，并且倒叙，还要打印！ p = q = (; ; (; 7 / 19 a; p = z - b; i=0; i (; b+i;q= p;p=q; i+; 其实第四题这样的题目楼上没有人说对。 说是从 10 亿个数中选 ，实际上是说数很多。当然用外部排序是一个方法。 估计想考的是看你会不会二叉排序树。 10000 个最大的数，就是 10000 个结点，这个内存是可以装下的。 但 10亿个数就要从外部文件读出来了。每读入一个 /组，就试图将之放入排序树中。等 10 亿个数全读完了， 10000个结点按中序输出就行了。 我还在 见过类似的题目，答案也是二叉排序8 / 19 树，好像没人回答出来。 象搜索的输入信息是一个字符串，统计 300 万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过 255存使用只有 1G, 请描述思想，写出算发（ 空间和时间复杂度， 这道题不是很难吧，用哈希的方法，将这些字符串哈希到不同的桶中，然后判断那个最多就行了 关于第 4题的我写的程序 # #000000 /设置总数，我这里设置了一百万，也可以到一千万，一亿的话内存受不了，但是我的程序是串行读出数据的，所以也是可以处理更大的数据的，这里全部放在数据里是为了方便 #000 , if( i = j = if(i=j)/只有两个数据，直接处理完了事 9 / 19 if(i i+1 = i ; i = i ; i i+); ; j if(i=j) i; i = j; j = if(i!= = i; i = i+1, 10 / 19 ;/ 最好结果 i=0, j=k=0; h=0; 0;/据计数器 ; i =0; i /)%77 + 1; / )%i = ); / /可加入一些测试数据，看看大的能否排到前面 = 100000; 0 =300002; 1 =200002; =200007; 11 / 19 ; 0; = , /k =0;k / i = j = ; 0; ; ; i+ = if(i=) / i 满 了 = 3; i = 0; j = ; n=0; n 12 / 19 = 2; if(n if(i!=n)i = n; /大的放到 i+; j+ = n; /小的放到 if(i i = 5; i+ = j; k = ; h = ; ;k = 2; 13 / 19 if(k i+ = k; if(h!=k) h = k; h+; j = h; /i100 了，选择排在 100 名后的分割数的操作完毕 ; /这里是全排序输出前 ，看看后面的结果是否和这个相同，但必须在 则堆栈溢出 / 14 / 19 /* , k=0; k */ / /输出前 , k =0;k ); ; 算法的题不难啊。 我说个思路吧： 1、线形表 a、 写一程序，使两个有序线形表合并成一个有序升序线形表 h； 这个问题和下面那个第一题本质是一样的，我 =一起说。 3、用递归算法判断数组 aN是否为一个递增数组。 这个就是每次拿最后一个和边界上的比下缩小规模，没难度。 4、编写算法，从 10亿个浮点数当中，选出其中最大的 10000 个。 15 / 19 外部排序 5、编写一 止僵尸进程的出现 . 和算法没关系。我不会。 的大小，还有一动态开辟的内存，求交集，把交集放到动态内存 且返回交集个数 先排序 O（ N*N），然后进行的步骤和第一题一样就对了。对这题是：取小头，比较，一样进内存，不一样小的扔 O（ N）内完成。加上排序 O（ N*N）搞定。 对上面那题 不用讲应该都知道了，就是比完合并就行了。 a -z26 个字母插入到连表中，并且倒叙，还要打印！ 链表是基本功，没什么好说的。 象搜索的输入信息是一个字符串，统计 300 万输入信息中的最热门的前十条，我们每次输入的一个字符串为不超过 255存使用只有 1G, 请描述思想，写出算发（ 空间和时间复杂度， 我不知道。不过你算下就知道空间肯定是够的：全部装入都够（当然我们不会这么做） 几十万个主题，假设每一个主题都有上亿的跟帖子，怎么样设计这个系统速度最16 / 19 好，请描述思想，写出算发（ 空间和时间复杂度， 我不知道。没学过着方面知识 楼上几个朋友回排序的，我们一起来讨论一个问 题。 结果要求的是 10000个排好顺序的数而已，并没有要求你把 10亿个数都拿出来排序。 所以更有效率的思路应当是 1、读入的头 10000 个数，直接创建二叉排序树。 O(1) 2、对以后每个读入的数，比较是否比前 10000 个数中最小的大。 (如果小的话接着读下面的数。 O(N) 3、如果大，查找二叉排序树，找到应当插入的位置。 4、删除当前最小的结点。 5、重复步骤 2，直到 10亿个数全都读完。 6、按照中序遍历输出当前二叉排序 树中的所有 10000个数字。 基本上算法的时间复杂度是 O(N)次比较 算法的空间复杂度是 10000(常数 ) 我来回答后面两道 难题 吧： 1. 最近时有公司出这种从几百万词条中找出频率最大的前几条或者重复的条目的问题。 对于这种问题实际上并不需要太多所谓的搜索专业知识，想想数据库是怎么实现或者数据结构中关于词典索引的章节就不难知道，这些题目的解决办法不外乎，采用二种17 / 19 数据结构： 树（二叉树， 树）和哈希表。对于 300 万词条来说，构建一个开 地址哈希肯定用不了 1G 内存，如果还不放心，就构建一棵 ，如果还怕内存不够就构建B+树进行多级索引。至于复杂度分析，稍微回忆一下你的数据结构书吧。 询与更新问题。 一级是个主题， 10多万主题为了效率直接哈希就成，查询时候这些主题肯定是要全部载入内存的； 二 级索引是上亿数据，查询或者更新时内存肯定不能放呀，自然就要用 B树。稍微补充一下，为啥要用 B+树就是为了解决内存中不能载入全部数据的时候用来分级 载入数据，这样可以充分利用内存的换 入换出来解决海量数据操作的问题。这和操作系统的文件系统设计以及数据库实现原理是相似的。 4、编写算法，从 10亿个浮点数当中，选出其中