一次面试

上周六(12.24)去X公司面试, 打了趟酱油. 收获还是有的.

上午十点来到X公司. 先是笔试: 题目类型是Linux C++的, 120分钟. 题目还记得些.

前面几题是问答题: 1.Linux下malloc函数的实现. 只依稀记得 K&R 里大概提了下. 2. errno的作用及实现. 实现我还真不知道怎么答. 3. sync命令的作用. 简单的说: 同步缓冲区数据到设备. 4. 好象是问TCP连接中如何确定send的数据被接收方全部接受完. 不知道是不是通过接收方对数据包进行对齐检校后再回应发送方而实现的. TCP是可靠连接嘛. 5. Linux中线程和进程的异同. 这个问题每一本讲Linux编程的书应该都有详细解释. 然后是几道编程题: 前面3题都是简单的字符串操作之类的, 没什么好说的. 看到第4题的时候觉得有点意思了:

  某公园门票5角, 有5个游客手里有且仅有一张5角纸币,
  另外5个游客手里有且仅有一张1元纸币. 售票员手中
  没有任何纸币. 设计一个程序演示这10个游客可使售票员
  能顺利找零的所有排队方法.
  例如 "5 5 5 5 5 10 10 10 10 10" 这种方法就能顺利找零.

这题看起来眼熟了(后来回来才回忆起在Richard.A.Brualdi的那本组合数学里看的, 著名的Catalan数呀). 当时老是想去带吸收壁的随机行走问题去了, 其实就是同样问题的不同阐述而已, 不同阐述的Catalan问题还多着呢: 元素的进栈出栈具体有哪些方式, 列举n对括号的所有合法方式, 将凸多边形划分成三角形区域的方法等等, 举不胜举. 题目说演示, 那就把所有的可接受序列打印出来吧. 我想着想着就想到用递归实现, 不过当时根本没有划分清楚不同的状态: 比如售票员手中有几张5角的票, 还有几个五毛游客在排队等等. 因此没写明白. 回去捋了下, 果然用递归实现是很易理解的, 而且容易扩展: 比如~~再加几种类型的纸币也可以很容易修改程序使之继续可用~~(钱币类型多的话不是想象中的那么容易的). 不过缺点就是递归效率太低. 因为字符串 "10" 太长了, 所以就用 "T" 表示手持1元的游客购票, 用 "F" 表示持有5角的游客购票. 把 "F" 替换成 "(", 把 "T" 替换成 ")" 就是列出所有合法的括号配对方法了. 代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

static unsigned int COUNT = 0;

void sale_ticket(int num_of_push_fiftycents, int sum_of_fiftycents_instack, char *pstr, const int max_push)
{
    /*
     * 若钱箱内五角钱币为空， 且还有持有五角的游客排队时，则下次
     * 只能接受五角游客购票。
     */
    if (sum_of_fiftycents_instack == 0 && num_of_push_fiftycents < max_push) {
        strcat(pstr, "F");      /* 把F加到字符串尾部表示有五角进了售票员的钱箱 */
        sale_ticket(num_of_push_fiftycents + 1, 1, pstr, max_push);
    }

    /*
     * 若钱箱内五角钱币非空， 且还有持有五角的游客排队时， 则下次
     * 可以接受两种游客的购票要求。
     */
    if (sum_of_fiftycents_instack > 0 && num_of_push_fiftycents < max_push) {
        /* 情况1：下一个游客是1元党 */
        char *new_pstr;
        if ((new_pstr = malloc(2 * max_push + 1)) == NULL) {
            perror("sale_ticket: malloc");
            exit(1);
        }
        strcpy(new_pstr, pstr);
        strcat(new_pstr, "T");  /* 把T加到字符串尾部表示有五角出了钱箱， 即找零 */

        COUNT++;            /* 又多了一种可接受的排队方案 */
        sale_ticket(num_of_push_fiftycents, sum_of_fiftycents_instack - 1, new_pstr, max_push);

        /* 情况2：下一个购票的是五毛 */
        strcat(pstr, "F");
        sale_ticket(num_of_push_fiftycents + 1, sum_of_fiftycents_instack + 1, pstr, max_push);
    }

    /*
     * 当只剩下一元党在排队购票时，下一个购票的必然是一元的了
     */
    if (sum_of_fiftycents_instack > 0 && num_of_push_fiftycents == max_push) {
        strcat(pstr, "T");
        sale_ticket(num_of_push_fiftycents, sum_of_fiftycents_instack - 1, pstr, max_push);
    }

    /*
     * 当五毛入钱箱次数等于持有五毛游客的数量，
     * 且钱箱内五角钱币为空时， 表明到达了边界，
     * 则输出之前记录的买票顺序字符串. 并释放
     * 内存, 返回.
     */
    if (num_of_push_fiftycents == max_push && sum_of_fiftycents_instack == 0) {
        printf("%s\n", pstr);
        free(pstr);
        return;
    }
}

int main(int argc, char **argv)
{
    char *prt;
    int max_push;   /* 五毛游客数, 即五毛进钱箱的最大次数 */

    if (argc < 2) {
        fprintf(stderr, "usage: %s num\n", argv[0]);
        exit(0);
    }
    max_push = atoi(argv[1]);
    if (max_push > 0)
        COUNT++;
    if ((prt = malloc(2 * max_push + 1)) == NULL) {
        perror("main: malloc");
        exit(1);
    }
    memset(prt, 0, 2 * max_push + 1);

    sale_ticket(0, 0, prt, max_push);
    printf("The total number is: %d\n", COUNT);
    return 0;
}

输入程序名后加数字即运行. 设置的数字不要超过16, 根据卡特兰数的一般项公式: Cn = (2*n)!/((n+1)! n!) . 第16项为35357670, 把所有可接受的排队顺序字符串输出需要1.1G的空间! 在我机器上大概10秒才运行完. 输入5的情况见这里:http://codepad.org/VKu9Bbb8

最后一题问的是如何排查一个程序的瓶颈. 很惭愧我不知道.

下午项目面试: 走进X公司的内部, 里面环境出乎我意料: 像个饭馆, 看上去挺惬意的, 不过里面没有人逗留. 最后面试官问了如何用多路复用改进我目前接触的项目(面试官技术不错, 听我稍微介绍完项目后就看出用定时轮询的方式耗资源).只要和网络开发有关的一般都会问到多路复用: select和poll机制. 这次果然也是. 结果没答明白. 拿了盒冬瓜茶就被叫回去了.

后记: Erlang 大法好, 描述好问题就得出答案了:


-module(catalan).
-export([catalan/0]).

num_ele_list(X, L) ->
      num_ele_list1(X, L, 0).

num_ele_list1(_, [], N) ->
      N;

num_ele_list1(X, [X | T], N) ->
      num_ele_list1(X, T, N+1);

num_ele_list1(X, [_ | T], N) ->
      num_ele_list1(X, T, N).

catalan() ->
      [{X1, X2, X3, X4, X5, X6, X7, X8, X9, X10} ||
              X1 <- [5] ,
X2 <- [5, 10],
num_ele_list(5, [X1, X2]) >= num_ele_list(10, [X1, X2]),
X3 <- [5, 10],
num_ele_list(5, [X1, X2, X3]) >= num_ele_list(10, [X1, X2, X3]),
X4 <- [5, 10],
num_ele_list(5, [X1, X2, X3, X4]) >= num_ele_list(10, [X1, X2, X3, X4]),
X5 <- [5, 10],
num_ele_list(5, [X1, X2, X3, X4, X5]) >= num_ele_list(10, [X1, X2, X3, X4, X5]),
X6 <- [5, 10],
num_ele_list(5, [X1, X2, X3, X4, X5, X6]) >= num_ele_list(10, [X1, X2, X3, X4, X5, X6]),
X7 <- [5, 10],
num_ele_list(5, [X1, X2, X3, X4, X5, X6, X7]) >= num_ele_list(10, [X1, X2, X3, X4, X5, X6, X7]),
X8 <- [5, 10],
num_ele_list(5, [X1, X2, X3, X4, X5, X6, X7, X8]) >= num_ele_list(10, [X1, X2, X3, X4, X5, X6, X7, X8]),
X9 <- [5, 10],
num_ele_list(5, [X1, X2, X3, X4, X5, X6, X7, X8, X9]) >= num_ele_list(10, [X1, X2, X3, X4, X5, X6, X7, X8, X9]),
X10 <- [5, 10],
num_ele_list(5, [X1, X2, X3, X4, X5, X6, X7, X8, X9, X10]) =:= num_ele_list(10, [X1, X2, X3, X4, X5, X6, X7, X8, X9, X10])
].

hmgle's blog

一次面试