创新工厂笔试 - 行者无疆 始于足下 - 行走,思考,在路上

创新工厂笔试

xiaohanyu posted @ Mon, 11 Oct 2010 19:12:03 +0800 in Work with tags work , 3611 readers

慕开复之名,一个小时的笔试,十一道题目,不算多,时间还算充裕。

选择题/填空题

  1. 关于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;
    }
    
  2. 关于什么叫数据库主键。

  3. 关于路由器和交换机的区别,哪个用来连接不同网段、分隔子网或者是分隔不同网段、连接子网。

  4. 进程和线程的区别(调度、控制、共享内存、通讯方式)。

  5. 排序复杂度哪个不是[tex]O(n\lg n)[/tex](二分插入排序、快速排序、归并排序、堆排序)。

  6. kmp算法填空(略微记得一点原理,忘差不多了……)。

  7. 有5道工序,其中有一道工序不能放在最后,问有多少种排列方法([tex]5!-4! = 96[/tex])。

  8. 内存分页算法的缺页次数(先进先出、最近最少、理想页面置换算法,完全不会……)。

  9. tcp和udp的区别

  10. 递归函数:

    		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是否为零即可。代码略去。

Avatar_small
Lox said:
Tue, 12 Oct 2010 06:23:49 +0800

顺便,blog系统有bug,代码排列第一行会出现莫名缩进。

Avatar_small
galeki said:
Tue, 12 Oct 2010 07:36:00 +0800

这是个编辑器的 bug,已经提交给编辑器作者了。目前的解决办法可以看: http://bugs.is-programmer.com/posts/21708.html#comment152970

:)

Avatar_small
依云 said:
Tue, 12 Oct 2010 19:13:40 +0800

你运行下就知道了。没弄错的话会栈溢出。

baoyibao said:
Wed, 13 Oct 2010 04:37:29 +0800

printf("%d\n", a.i)少了个;

Avatar_small
Lox said:
Wed, 13 Oct 2010 07:21:41 +0800

运行过,segmentation fault

Avatar_small
Lox said:
Wed, 13 Oct 2010 07:22:00 +0800

已更正,多谢指正。

Avatar_small
treblih said:
Thu, 14 Oct 2010 04:31:26 +0800

f(n - 2) + f(n - 1)后也少;

Avatar_small
Lox said:
Thu, 14 Oct 2010 05:38:27 +0800

呃,太马虎了,是因为写blog的时候走捷径直接插入的代码,犯懒了。


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee