bishi题

http://charpn.spaces.live.com/Blog/cns!AC6DB5E1F5B033F6!642.entry

http://hxraid.iteye.com/category/83702

 

2009年笔试题
1、编程题
判断字符串 b 的所有字符是否都再字符串 a 中出现过，a,b都是可能包含汉字的字符串。b中重复出现的汉字，那么a中也要至少出现相同的次数。
汉字使用gbk编码（简单的所，用两个字节表示一个汉字，高字节最高位为1的代表汉字，低字节最高位可以不为1）。
int is_include(char *a  ,  char *b)
返回0 表示没有都出现过，返回1表示都出现过。
 
2、 算法题
   序列 seq=[a,b,…,z,aa,ab,…,az,ba,bb,…,bz,…,za,zb,…,zz,aaa,…]类似于excel的字母序排列，任意给一字符串 s=[a-z]+(由a-z字符串组成的任意长度字符串)，请问s是序列seq的第几个字符串。
 
3、 系统设计
   需求：需要引入用户对搜索结果相关性的评分，100分制。希望用户的打分能帮助搜索引擎排序，但又避免恶意投票

 

------------------

 第一题：简要说明树的深度优先、广度优先遍历算法挤特点
   第二题：一个复数相加的编码挑错题
   第三题：告诉内存大小和cpu速度，计算可能的程序运行最长时间
   第四题：复杂项目的组件编译依赖，设计一个快速算法并计算复杂度
   第五题：写个c程序，返回字符串中最长数字字符串的长度和地址，不能用标准库函数
   第六题：设计个系统，存储100亿个url和属性信息，并可以更改属性信息和查找url，快速搜索站点的所有url及信息

---------------

 

【2010运维部笔试题】

http://bbs.yingjiesheng.com/thread-248069-1-1.html

总共三部分7道题
第一部分·简答
1·简述树的深度优先算法、广度优先算法，及非递归实现的特点。

2·在文件系统中，元数据（比如ext2中的inode）的基本作用是什么？ext2跟ext3的根本区别是什么？

3·在web服务中，负载均衡的基本作用是什么？请举例你熟悉的一款负载均衡软件或者实现方案，简述它们的实现原理。（这题后半部分为开放性，我也没记多深，大概就这样）

4·数据库事务的四大特性是什么？请你简单举例对一个完全不懂数据库的人解释这四个特性。投数据库管理员（DBA）必答。

5·一个微型处理器，1KB内存和1MHz（每MHz运算次数为10^6），在这样的计算机上面运行程序（程序到该终止时会自动终止，不会出现死循环）最长能运行多长时间？你可以进行任何需要的假定。

第二部分·算法和程序设计
1·int maxContinuNum(const char *inputstr,char * outputstr)
编写一段程序实现该函数，实现返回一个以“\0”结束的字符串中最长的数字串的长度，并把该数字子串的首地址赋给outputstr。不能使用任何库函数或已经存在的函数，如strlen。
例如：在字符串“abc123abcdef12345abcdefgh123456789”中，把该字符串的首地址赋给inputstr，返回9，outputstr指向字符串“123456789”的首地址。

 

第三部分·备份系统设计
（这题太长了，记住的不多，下面是大概的）
设计一个备份系统，要求符合三个备份场景，写出你的设计思路，框架模块设计，实现原理。
要求：1·该系统要能实现对多服务器备份工作（大概这样，还是。。）      
        2·该系统要具备很好容错性，不能因为多服务器中的一台出现故障儿导致整个备份工作不能进行。
        3·。。。
        4·。。。（这两点记不清了，不好意思）
        5·具有较强的扩展性，例如当服务器内存不够时，能灵活的添加内存。

扩展性是附加，在实现前面的要求后再考虑扩展性

备份场景           服务器              备份网络速度             备份开始时间
场景1             a1~a10                 10M/S               每天上午10点10分
场景2            a1,b1,c1,d1            30M/S               （忘了 - -！）
                     四台服务器
场景3            a1~a100                5M/S                 （也不大记得了。。）

 

 

 ----------------------------------------------------------------------------------------------

集合合并：

给定一个字符串的集合，格式如：

{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}

要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应

输出

{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

（1）请描述你解决这个问题的思路；

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

（3）请描述可能的改进（改进的方向如效果，性能等等，这是一个开放问题）。

 

----------------------------------------------------------------------

2010 A卷

 

1．  简要说明树的深度优先、广度优先遍历算法，及非递归实现的特点。

 

2．  在处理磁盘数据时，需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中，则可以直接访问内存。通常来说内存是有限的，因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据，内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求，要求它们必须按照给定的顺序被读取，同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。

 

3．  全体员工玩分组游戏，前面五分钟大家分头找队友，并将每个人找到的队友信息汇报给主持人，如果A和B是队友，B和C是队友，那么A和C也是队友；接着主持人不断地随机抽取两个人，希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友，说明程序的关键算法，不需要代码实现。

 

例如：

<小明，小王>，<小军，小王>，<小丽，小李>是队友，那么小军和小明是队友，小军和小丽不是队友。

 

4．  给定以下二叉树:

struct node_t

{

    node_t *left, *right;

    int value;

};

要求编写函数 node_t* foo(node_t *node, unsigned int m, unsigned int k);

输出以 node 为根的二叉树第 m 层的第 k 个节点值.

(level, k 均从 0 开始计数)

注意：

此树不是完全二叉树；

所谓的第K个节点，是本层中从左到右的第K个节点

 

5．  在一个复杂广告系统中，需要很多系统协同工作，其中包括众多定时任务(最初配置在linux crontab中调度\管理)的相互依赖，例如：A任务是一个每天定时处理日志的计算任务、B任务是一个反zuobi任务，B任务需要读取A任务产生的结果文件， A、B任务由于系统资源限制、运行在不同物理机器上。在这样一个环境中，为了保障这些任务的有序调度和运行，需要一个任务调度系统存在。这里请设计一个任务调度系统来取代原始的linux crontab模式。（提示：调度系统中尽量不要存在单点，如果存在单点、则请指出优缺点对比；任务之间的依赖关系需要机制来严格保证；）

 

根据以上背景完成如下问题：

1、给出一个系统整体结构图，并简要描述系统各个部份功能、整体调度运行流程；

2、任务调度系统中需要管理上千个定时任务，每个定时任务需要一个数据结构来描述，请用C结构体语法描述一个任务单元、并注释每个结构体成员的含义

 

------------------------

1、请编写函数foo(int x, int y, int n) 计算：随机生成x个大小为[1,y]的正整数，它们的和为n的概率是多少？语言仅限于PHP、C/C++、Java中的一种。

-------------------

输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
字符串\t数字\n

说明：
每行为1条记录；字符串中不含有\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。

要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机地输出字符串，输出N条记录

例如：
输入文件A.txt
abc\t20
a\t30
de\t50
输入为：10

即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
abc
de
a
de
a
de

--------------------------------

 

题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

程序输入：n个数
程序输出：联接成的多位数

例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）

 

 

-----------------------------------------------------------

 

编程： 用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。

 

 

 

寻找热门查询：

　　搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。
假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。
请你统计最热门的10个查询串，要求使用的内存不能超过1G。

（1）请描述你解决这个问题的思路；
（2）请给出主要的处理流程，算法，以及算法的复杂度。

 

 

-----------------------------------------------------------

 现有两个文件，

　　a)数据文件A，格式为：关键词、IP地址、时间，记录条数为1000万左右，该文件是无序排列的。

　　b)数据文件B是关键词ID到关键词的对应表文件，格式为：ID、关键词，记录条数在100万左右，也是无序排列的。
该对应表中的记录是一一对应的，不存在ID或者关键词重复的情况。

　　要求将数据文件A对应的关键词替换为B中的ID，生成新的数据文件C，数据文件C的格式为：关键词ID、IP地址、时间。

　　请设计一个程序，实现上述功能，并分析时间复杂度和空间复杂度。运行程序所使用的服务器的内存为1G，硬盘足够大。(至少要给出关键算法和设计思路)

 

 

-----------------------------------------------------------

设计一个函数实现获得原始字符串的子串的功能，从某个偏移位置开始，获取长度为n的子串，希望函数能够比较健壮。

 

 

-----------------------------------------------------------

在一棵一般的二叉树中找到指定的元素，如果有重复出现的元素，要求元素为深度最深的任何一个。
指定元素找不到时返回EMPTY_NODE，请用C语言实现，相关数据结构与函数声明如下：
struct Node
{
int iValue;
int id;
Node *pLeft;
Node *pRight;
};

const Node EMPTY_NODE = {0, 0, NULL, NULL};
Node findDeepest(Node *pRoot, int iWanted); //pRoot为根节点，wanted为指定元素的iValue

 

 

-----------------------------------------------------------

 

一个单词字典库，单词个数约为10万，每个单词长度不超过16，单词都是由小写字母组成，同时给出16个小写字母，
请设计一种高效算法来找到用这些给出字母拼出一个字典中最大长度的单词。给出的16个字母每个字母最多使用一次，也可以不使用。
存在多解的时候给出任意一个最优答案就行。

例如：给出adeenrstuvxyzuki可以拼出adventures
请详细描述你的算法思路（如需要，可给出代码\伪代码来辅助描述），并分析其时间复杂度。最后请分析下你的算法以及数据结构的优缺点，存在哪些可改进的地方。

----------------------------------------------------------

内存中有一个长数组，条目数为10万，数组单元为结构体struct array，sizeof(struct array)为512字节。结构有一int型成员变量weight。
现需要取得按weight值从大到小排序的前500个数组单元，请实现算法，要求效率尽可能高。

----------------------------------------------------------

 20.  http://blog.csdn.net/thinkingdeeply/archive/2006/10/13/1333500.aspx

一条1百万节点的单向链表，链表所有节点是按value字段从小到大的顺序链接；下面是一个节点的结构
 

   typedef struct node_t{
 

       int value;   /* 节点排序字段 */
 

       int group;   /* 组号: 0,1,2,3,4,5,6,7,8,9 */
 

       struct node_t *pnext;  /* 下个节点的指针 */
 

   }node_t;
 

   node_t head;    /*该单向链表的头节点，全局变量 */
 

   
 

试设计程序：针对各个group(0-->9)，根据value字段排序，输出各组top 10的节点。（top10是从小到大，取后面的大值top10.）
 

要求：尽量减少计算复杂度、遍历次数，不允许大量的辅助内存

 

 

----------------------------------------------------------

21.实现 void delete_char(char * str, char ch);
　把str中所有的ch删掉

22.把字符串S中所有A子串换成B,这个没给函数原型

23.搜索引擎的日志要记录所有查询串,有一千万条查询,不重复的不超过三百万
　要统计最热门的10条查询串. 内存<1G. 字符串长 0-255
　(1) 主要解决思路 //具体用词和原题不大一样
　(2) 算法及其复杂度分析

 

25.有字典,设计一个英文拼写纠正算法 (1) 思想 (2) 算法及复杂度 (3) 改进

 

26. { aaa, bb, ccc, dd }, { bbb, ff }, { gg } 等一些字符串的集合
　要求把交集不为空的集合并起来,如上例会得到 { aaa, bb, ccc, dd, ff }, {gg}
　(1) 思想 (2) 算法及复杂度 (3) 改进

 

 

 

-----------------------------------------------------------

动态规划问题

 

-----------------------------------------------------------

回朔问题

 

-----------------------------------------------------------

xunlei：http://blog.163.com/ecy_fu/blog/static/444512620098228849190/