人民搜索的笔试题
人民搜索的笔试题
1、打印汉诺塔移动步骤,并且计算复杂度
2、计算两个字符串的是否相似(字符的种类,和出现次数相同)
3、定义二叉树,节点值为int,计算二叉树中的值在[a,b]区间的节点的个数
4、动态规划题:一条路有k可坑,每次能跳平方数步长(1 4 9 16。。),不能跳到坑里,从a跳到b最少几步?
5、给一个整数数组,求数组中重复出现次数大于数组总个数一半的数。
1、对以孩子兄弟链接的树进行遍历,不能用递归,也不能借助任何辅助空间
2、假设数组B是升序Int数组A循环移若干得到的位,实现对数组B进行查找的高效算法
3、只有整数和+-*/四种运算组成的算术表达书,实现其求值
4、还有一个是考贪心算法的,你让他们看算法导论那本书,关于fractional knapsack problem的那一段,就是0-1背包的一种变形;
5、链表相邻元素翻转,如a->b->c->d->e->f-g,翻转后变为:b->a->d->c->f->e->g
6、求正整数n所有可能的和式的组合(如;4=1+1+1+1、1+1+2、1+3、2+1+1、2+2)
1、实现一个atoi函数==>’注意正负号的判定’
2、翻转一个句子,其中单词是正序的==>两次旋转
3、二叉树两个结点中的最小公共子结点==>求长度,长度之差,远的先走,再一起走
4、三角阵中从第一行到最后一行(给出搜索方向的限制)找一个连续的最大和==>广度优先搜索√
5、实现一个STL中的vector中的尽量多的方法。
6、字符串移动(字符串为*号和26个字母的任意组合,把*号都移动到最左侧,把字母移到最右侧并保持相对顺序不变),要求时间和空间复杂度最小
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | /** ** author :hackbuteer ** date :2012-10-03 **/ void Arrange(char *str , int n) { int i , k = n-1; for(i = n - 1 ; i >= 0 ; --i) { if(str[i] != '*') { if(str[k] == '*') { str[k] = str[i]; str[i] = '*'; } --k; } } } |
7、说说outer join、inner join、left join、right join的区别是什么?
内连接:进行连接的两个表对应的相匹配的字段完全相同的连接。join
外连接又分为左外连接和右外连接。
左连接即LEFT OUTER JOIN:
两个表进行左连接时会返回左边表中的所有的行和右边表中与之相匹配的列值没有相匹配的用空值代替。
右连接即RIGHT OUTER JOIN:
两个表进行右连接时会返回右边表中的所有的行和左边表中与之相匹配的列值没有相匹配的用空值代替。
我们建立两张表,students、class并插入测试数据
students
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | --------------------------- id name classId 1 name1 1 2 name2 null 3 name3 2 --------------------------- class ----------------------- id name 1 class1 2 class2 3 class3 ----------------------- 实验结果如下: mysql> select s.name,c.name from students s join class c where s.classId=c.id ; (注:inner join和join一样) +-------+-------+ | name | class | +-------+-------+ | name1 | 1 | | name3 | 2 | +-------+-------+ 2 rows in set mysql> select s.name,c.name from students s left join class c on s.classId=c.id ; (left join 和 left outer join 一样) +-------+-------+ | name | class | +-------+-------+ | name1 | 1 | | name2 | NULL | | name3 | 2 | +-------+-------+ 3 rows in set mysql> select s.name,c.name from students s right join class c on s.classId=c.id ; (right join 和 right outer join 一样) +-------+-------+ | name | class | +-------+-------+ | name1 | 1 | | name3 | 2 | | NULL | 3 | +-------+-------+ 3 rows in set |
本文固定链接: http://www.chepoo.com/renmin-search-interview.html | IT技术精华网