创新工厂笔试 - 行者无疆 始于足下 - 行走,思考,在路上
创新工厂笔试
慕开复之名,一个小时的笔试,十一道题目,不算多,时间还算充裕。
选择题/填空题
-
关于c union type,求下列程序的输出结果(具体程序既不清楚了,考点在于union type的内存分布):
#include <stdio.h> union u { int i; char x[2]; }a; int main() { a.x[0] = '1'; a.x[1] = '2'; printf("%d\n", a.i); return 0; }
-
关于什么叫数据库主键。
-
关于路由器和交换机的区别,哪个用来连接不同网段、分隔子网或者是分隔不同网段、连接子网。
-
进程和线程的区别(调度、控制、共享内存、通讯方式)。
-
排序复杂度哪个不是[tex]O(n\lg n)[/tex](二分插入排序、快速排序、归并排序、堆排序)。
-
kmp算法填空(略微记得一点原理,忘差不多了……)。
-
有5道工序,其中有一道工序不能放在最后,问有多少种排列方法([tex]5!-4! = 96[/tex])。
-
内存分页算法的缺页次数(先进先出、最近最少、理想页面置换算法,完全不会……)。
-
tcp和udp的区别
-
递归函数:
int f(int n) { if (n == 0) return 3; else return f(n-2) + f(n-1); }
求f(10)(我的答案是没结果,应该是唬人的题目)
编程题
给定一个字符串,字符串中可能含有包含'(', ')', '[', ']',判定条件如下:
- '('和')'、'['和']'个数相等
- '('和')','['和']'完全配对,不能出现嵌套情况。
如符合以上两条,则返回True,否则返回False。
Example:
a(ab)[aa(ba)[aa]b]为True,而a((a)、ab(a[bbb)]c为False。
解决方案:
如果熟悉stack表达式求值算法,这道题目应该不在话下。设定两个计数器m和n,m记录'('和')'的个数的差值,'n'记录'['和']'个数的差值,再设定一个STL stack<char> par。
每当读到'('或'[',就执行push操作par.push('('),par.push('['),同时m++, n++;每当读到')'或']',就判断下栈顶元素和当前元素是否配对,如果配对,则par.pop(),否则直接返回False,同时m--,n--。
最后判断m和n是否为零即可。代码略去。
Tue, 12 Oct 2010 03:40:05 +0800
第10题强大~
Tue, 12 Oct 2010 06:20:24 +0800
怎么个强大法?
Tue, 12 Oct 2010 06:23:49 +0800
顺便,blog系统有bug,代码排列第一行会出现莫名缩进。
Tue, 12 Oct 2010 07:36:00 +0800
这是个编辑器的 bug,已经提交给编辑器作者了。目前的解决办法可以看: http://bugs.is-programmer.com/posts/21708.html#comment152970
:)
Tue, 12 Oct 2010 19:13:40 +0800
你运行下就知道了。没弄错的话会栈溢出。
Wed, 13 Oct 2010 04:37:29 +0800
printf("%d\n", a.i)少了个;
Wed, 13 Oct 2010 07:21:41 +0800
运行过,segmentation fault
Wed, 13 Oct 2010 07:22:00 +0800
已更正,多谢指正。
Thu, 14 Oct 2010 04:31:26 +0800
f(n - 2) + f(n - 1)后也少;
Thu, 14 Oct 2010 05:38:27 +0800
呃,太马虎了,是因为写blog的时候走捷径直接插入的代码,犯懒了。