C++博客-A Za, A Za, Fighting...

2011找工总结

simplyzhao — Mon, 27 Feb 2012 05:19:00 GMT

找工，其实早在11年十一月份就结束了，今天来补个总结。

11年九月下旬赶回去参加趋势科技在南京的笔试，并成功地在十一之前拿到offer，记得从南京坐高铁回家，怀里揣着趋势的offer很是心安，也给了自己很大的信心（因为，一直觉得自己从广州跑回南京上海找工会处于劣势），至今对于趋势科技面试的轻松氛围，包括最后的群面都印象深刻，是一家很nice的公司。

休完十一假期就赶去上海，在上海复旦呆了个把月，感谢舍友彭博帮我在复旦找到落脚地。
在上海，前前后后参加了很多的笔试面试，最终拿到了满意的offer，去了EMC，尽量得花5000大洋的毁约费。

推荐公司：EMC，TrendMicro，Marvell

“经验”：
自信&微笑，熟练掌握一门语言(如C)，数据结构与算法(推荐《算法导论》)，操作系统(推荐《深入理解计算机系统》)，有个别“拿得出手”的小项目，英语

----------------------------------------------------------------------------------------------------------------
所有投递简历公司那长长的列表(排名按投递简历的时间顺序)：

1. 爱立信上海
SH01 Software Design Engineer (上海)

[已笔试, 通过群面, 放弃]

2. 趋势科技 Trend Micro (上海)

软件工程师

https://campus.trendmicro.com.cn

[已笔试, 已面试, OFFER]

3. Marvell (上海)

[已笔试，已面试，OFFER]

4. 百度 (上海)

[时间冲突，放弃]

5. 华为

软件研发工程师性能/算法工程师

[放弃]

6. 飞利浦苏州 (上海)

嵌入式软件开发工程师软件应用开发工程师

[放弃]

7. Google (上海)

[放弃]

8. nVidia 英伟达 (上海)

GPU Architect

[放弃]

9. EMC (上海)

Software Development Engineer 上海

[已笔试, 已面试, OFFER]

10. AMD (上海)

System Software Engineer

[木有笔试机会]

11. 腾讯 (上海)

后台开发上海

[已笔试, 已面试, OFFER]

12. 微软 (上海)

软件开发工程师上海

[时间冲突，放弃]

13 Samsung (南京)

手机开发南京

[放弃]

14 IBM CSTL (上海)

storage software engineer

[没消息]

15. Intel (上海)

zhaopin.com

[木有笔试机会]

16. Cisco (上海)

embedded software development engineer

[放弃]

17. 大众点评网 (上海)

技术培训生 - 开发

[放弃]

18. 阿尔卡特朗讯 (上海)

[放弃]

19. 支付宝 (上海)

[放弃]

20. 中航无线电 (上海)

[放弃]

21. Oracle (上海)

[已面试，算是给了OFFER]
22. 江苏移动
[放弃]

simplyzhao 2012-02-27 13:19 发表评论

2011知识点 - 多态的C实现

simplyzhao — Thu, 20 Oct 2011 09:22:00 GMT

示例代码:

/* how to simulate C++'s polymorphism with C */
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/* declaration of virtual method */
typedef void (*Func1)(void);
typedef void (*Func2)(int);
typedef void (*Func3)(char *);

/* ------------------- Base Class begin ------------------*/
void func1_base(void)
{
    printf("func1_base(void) called\n");
}

void func2_base(int item)
{
    printf("func2_base(%d) called\n", item);
}

struct Vtbl_Base {
    Func1 f1;
    Func2 f2;
};
struct Vtbl_Base bvtbl = {&func1_base, &func2_base};

struct Base {
    void *vptr; /* pointer to VTABLE */
    int field_base;
};

void Base_Init(struct Base *base, int value)
{
    base->vptr = &bvtbl;
    base->field_base = value;
}

/* ------------------- Base Class end ------------------*/

/* ------------------- Derived Class begin ------------------*/
void func1_derived(void)
{
    printf("func1_derived(void) called\n");
}

void func3_derived(char *item)
{
    printf("func3_derived(%s) called\n", item);
}

struct Vtbl_Derived {
    struct Vtbl_Base vtbl_base;
    Func3 f3;
};
struct Vtbl_Derived dvtbl = {{&func1_derived, &func2_base}, &func3_derived};

struct Derived {
    struct Base base;
    int field_derived;
};

void Derived_Init(struct Derived *derived, int b, int d)
{
    Base_Init((struct Base *)derived, b);
    derived->base.vptr = &dvtbl;
    derived->field_derived = d;
}

/* ------------------- Derived Class end ------------------*/

void
test_polymorphism(struct Base *obj)
{
    ((struct Vtbl_Base *)(obj->vptr))->f1();
    ((struct Vtbl_Base *)(obj->vptr))->f2(obj->field_base);
}

int
main(int argc, char **argv)
{
    struct Base base;
    Base_Init(&base, 128);
    test_polymorphism(&base);

    struct Derived derived;
    Derived_Init(&derived, 128, 256);
    test_polymorphism((struct Base *)&derived);

    ((struct Vtbl_Derived *)(*(int *)&derived))->f3("polymorphism");
}

simplyzhao 2011-10-20 17:22 发表评论

2011好题 - Young氏矩阵[zz]

simplyzhao — Sun, 16 Oct 2011 11:11:00 GMT

转:

http://www.binghe.org/2011/05/young-tableau/

一个 m*n 的 Young 氏矩阵(Young tableau) 是一个 m*n 的矩阵,其中每一行的数据都从左到右排序,每一列的数据都从上到下排序.Young 氏矩阵中可能会有一些 ∞ 数据项,表示不存在的元素.所以,Young 氏矩阵可以用来存放 r<= mn 个有限的元素.
a).画一个包含{9,16,3,2,4,8,5,14,12} 的4*4 的 Young 氏矩阵.

b).给出一个在非空 m*n 的 Young 氏矩阵上实现 EXTRACT-MIN 算法,使其运行时间为O(m+n).

c).说明如何在O(m+n)时间内,将一个新元素手入到一个未满的 m*n Young 氏矩阵中.

d).给出一个时间复杂度为 O(n^3) 的对 n*n Young 氏矩阵排序的算法.

e).给出一个运行时间为O(m+n) 的算法,来决定一个给定的数是否存在于一个给定的 m*n 的 Young 氏矩阵当中.

答

a). 2 3 4 5

8 9 12 14

16 ∞ ∞ ∞

∞ ∞ ∞ ∞

PS.该矩阵并不是唯一的.

b). (1)用递归的思想.在 Young 氏矩阵中，通过递归的解决(m-1)*n,或m*(n-1) 的子问题来求解.则有 T(m,n)=T(m-1,n) or T(m,n-1)+ O(1),显然,T=O(m+n).伪代码如下:

EXTRACT_MIN(Young[1...m] [1...n])
EXTRACT_MIN=Young[1][1]; //类似FORTRAN的写法.函数名即是返回值.
Young[1][1]= INFINITY;
ADJUST_TO_YOUNG(Young[1...m] [1...n]);
END

ADJUST_TO_YOUNG(Young[x...m] [y...n])
if(Young[x][y]==∞)
return;
if(Young[x+1][y]>Young[x][y+1])
swap(Young[x][y], Young[x][y+1]);
ADJUST_TO_YOUNG(Young[x...m][y+1...n]);
else
swap(Young[x][y], Young[x+1][y]);
ADJUST_TO_YOUNG(Young[x+1...m][y...n]);
END

(2)类似堆的删除：将Young[1][1]与最右下角元素交换, 然后移动Young[1][1]处的元素至合适位置，即把它与右方或下方元素的比较,并与其中较小的一个交换.反复进行直到它不大于它右方和下方的元素为止.

c). 类似堆的插入：先将待插入的元素 K 放在 Young[m][n], 然后比较 K 与它左方或上方元素的大小,并与其中较大的一个交换.反复进行直到 K 不小于它左方和上方的元素为止. 在这里,同样有,T(m,n)=T(m-1,n) or T(m,n-1)+ O(1),T=O(m+n).伪代码如下:

INSERT(k,Young[m][n])
if(Young[m][n] < INFINITY) alert: 矩阵已满,无法插入!!
while(kif(Young[m-1][n] >Young[m][n-1])
swap(k,Young[m-1][n]);
m=m-1;
else
swap(k,Young[m][n-1]);
n=n-1;
END

d). 调用 n*n 次 EXTRACT_MIN 过程即可.

e). 总是于最右上角的元素X比较；
1）如果==X,结束；
2）如果比X小，那么元素只可能在前N-1列中；
3）如果比X大，那么元素只可能在后M-1行中；
Young 氏矩阵去掉一行或一列还是 Young 氏矩阵；
所以每次比较最少去掉一行或一列，这样复杂度就是 O(m+n);

simplyzhao 2011-10-16 19:11 发表评论

2011好题 - 寻找俩已排好序数组的中位数

simplyzhao — Sun, 16 Oct 2011 10:38:00 GMT

问题:
有两个已排好序的数组A和B，长度均为n，找出这两个数组的中间元素。要求时间代价为O(logn)

思路:
a. 比较自然的思路是归并算法，不过时间复杂度是O(n)，无法满足题目要求

b.
( http://www.binghe.org/2011/05/find-median/ )

Say the two arrays are sorted and increasing, namely A and B.
It is easy to find the median of each array in O(1) time.
Assume the median of array A is m and the median of array B is n.
Then,
1′ If m=n, then clearly the median after merging is also m, the algorithm holds.
2′ If mm, also reserve the half of sequence B in which all numbers are smaller than n.
Run the algorithm on the two new arrays.
3′ If m>n, then reserve the half of sequence A in which all numbers are smaller than
m, also reserve the half of sequence B in which all numbers are larger than n.

Run the algorithm on the two new arrays.

Time complexity: O(logn)

simplyzhao 2011-10-16 18:38 发表评论

2011面试题 - 循环报数

simplyzhao — Tue, 11 Oct 2011 15:08:00 GMT

昨天去面试，结果中间还插了一个小时的上机(给个laptop，Windows+VC环境，用惯Vim结果好不习惯^_^)，其中一题如下：

有N个人按照1到N编号围成一个圈做游戏
从第一个人开始从1报数,数到M的人退出游戏,他后面的人接着重新从1开始报数，一直持续到所有人都退出．
要求输出退出游戏的人的顺序.

这题以前看过，记得貌似有些数学规律的，忘了，所以只能当场用模拟的方法来做。
当时用的是循环数组来模拟，结果花了半个小时才编译、测试搞定，面试我的人(挺Nice的)看了之后说，答案输出是对的，其实更自然的模拟是用链表。
刚才用链表试了下，果然简单好多，大概五分钟就可以搞定。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
int n, m;
struct Item {
    int number;
    struct Item *next;
};

void
solve(int n, int m)
{
    int i, j;
    assert(n>0 && m<=n);
    struct Item *items = (struct Item *)malloc(sizeof(struct Item) * n);
    assert(items != NULL);
    /* init */
    for(i=0; i<n-1; ++i) {
        items[i].number = i+1;
        items[i].next = items+i+1;
    }
    items[n-1].number = n;
    items[n-1].next = items;
    /* simulate */
    struct Item *cur, *prev = NULL;
    cur = items;
    while(n--) {
        j = m;
        while(--j) {
            prev = cur;
            cur = cur->next;
        }
        printf("%d\n", cur->number);
        prev->next = cur->next;
        cur = cur->next;
    }
    free(items);
}

int
main(int argc, char **argv)
{
    while(scanf("%d %d", &n, &m) != EOF) {
        printf("Result of (N=%d, M=%d)\n", n, m);
        solve(n, m);
    }

    return 0;
}

simplyzhao 2011-10-11 23:08 发表评论

2011知识点 - 文件描述符 dup/dup2

simplyzhao — Sat, 08 Oct 2011 07:57:00 GMT

文件描述符----文件表----v节点结构三者的联系

既然文件描述符标识特定进程正在访问的文件，那进程跟文件是怎么联系起来的呢？

首先我们得知道每运行一个进程，shell就会默认为其打开三个文件描述符(0,1,2)，分别与标准输入(stdin)，标准输出(stdout)和标准错误(stderr)对应。

接下来讲下内核所使用的三种数据结构，正是这三种数据结构才使进程最终跟文件联系起来。建议边看图一边看下面的文字描述

a. 每个进程在进程表中都有一个记录项，每个记录项中有一张打开文件描述符表，可将其视为一个矢量，每个描述符占用一项。
与每个文件描述符相关联的是：(a) 文件描述符。(b) 指向一个文件表项的指针

b. 内核为所有打开文件维持一张文件表。每个文件表项包含：(a) 文件状态标志。(b) 当前文件位移量。(c) 指向该文件v节点表项的指针。

c. 每个打开文件（或设备）都有一个v节点结构。是文件的重要信息部分。

下图表示以上三个数据结构的关系：

fd1 = open(pathname, oflags);

fd2 = dup(fd1);

fd3 = open(pathname, oflags);

图一

dup/dup2
相信大部分在Unix/Linux下编程的程序员手头上都有《Unix环境高级编程》(APUE)这本超级经典巨著。作者在该书中讲解dup/dup2之前曾经讲过“文件共享”，这对理解dup/dup2还是很有帮助的。这里做简单摘录以备在后面的分析中使用：
Stevens said:
(1) 每个进程在进程表中都有一个记录项，每个记录项中有一张打开文件描述符表，可将视为一个矢量，每个描述符占用一项。与每个文件描述符相关联的是：
(a) 文件描述符标志。
(b) 指向一个文件表项的指针。
(2) 内核为所有打开文件维持一张文件表。每个文件表项包含：
(a) 文件状态标志(读、写、增写、同步、非阻塞等)。
(b) 当前文件位移量。
(c) 指向该文件v节点表项的指针。
图示：
文件描述符表
------------
fd0 0 | p0 -------------> 文件表0 ---------> vnode0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------
fd2 2 | p2
------------
fd3 3 | p3
------------
... ...
... ...
------------

一、单个进程内的dup和dup2
假设进程A拥有一个已打开的文件描述符fd3，它的状态如下：
进程A的文件描述符表(before dup2)
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------
fd2 2 | p2
------------
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------
... ...
... ...
------------

经下面调用：
n_fd = dup2(fd3, STDOUT_FILENO);后进程状态如下：

进程A的文件描述符表(after dup2)
------------
fd0 0 | p0
------------
n_fd 1 | p1 ------------
------------ \
fd2 2 | p2 \
------------ _\|
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------
... ...
... ...
------------
解释如下：
n_fd = dup2(fd3, STDOUT_FILENO)表示n_fd与fd3共享一个文件表项(它们的文件表指针指向同一个文件表项)，n_fd在文件描述符表中的位置为 STDOUT_FILENO的位置，而原先的STDOUT_FILENO所指向的文件表项被关闭，我觉得上图应该很清晰的反映出这点。按照上面的解释我们就可以解释CU中提出的一些问题：
(1) "dup2的第一个参数是不是必须为已打开的合法filedes？" -- 答案：必须。
(2) "dup2的第二个参数可以是任意合法范围的filedes值么？" -- 答案：可以，在Unix其取值区间为[0,255]。

另外感觉理解dup2的一个好方法就是把fd看成一个结构体类型，就如上面图形中画的那样，我们不妨把之定义为：
struct fd_t {
int index;
filelistitem *ptr;
};
然后dup2匹配index，修改ptr，完成dup2操作。

在学习dup2时总是碰到“重定向”一词，上图完成的就是一个“从标准输出到文件的重定向”，经过dup2后进程A的任何目标为STDOUT_FILENO的I/O操作如printf等，其数据都将流入fd3所对应的文件中。下面是一个例子程序：
#define TESTSTR "Hello dup2\n"
int main() {
int fd3;

fd3 = open("testdup2.dat", 0666);
if (fd < 0) {
printf("open error\n");
exit(-1);
}

if (dup2(fd3, STDOUT_FILENO) < 0) {
printf("err in dup2\n");
}
printf(TESTSTR);
return 0;
}
其结果就是你在testdup2.dat中看到"Hello dup2"。

二、重定向后恢复
CU上有这样一个帖子，就是如何在重定向后再恢复原来的状态？首先大家都能想到要保存重定向前的文件描述符。那么如何来保存呢，象下面这样行么？
int s_fd = STDOUT_FILENO;
int n_fd = dup2(fd3, STDOUT_FILENO);
还是这样可以呢？
int s_fd = dup(STDOUT_FILENO);
int n_fd = dup2(fd3, STDOUT_FILENO);
这两种方法的区别到底在哪呢？答案是第二种方案才是正确的，分析如下：按照第一种方法，我们仅仅在"表面上"保存了相当于fd_t（按照我前面说的理解方法）中的index，而在调用dup2之后，ptr所指向的文件表项由于计数值已为零而被关闭了，我们如果再调用dup2(s_fd, fd3)就会出错(出错原因上面有解释)。而第二种方法我们首先做一下复制，复制后的状态如下图所示:
进程A的文件描述符表(after dup)
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------ /|
fd2 2 | p2 /
------------ /
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------ /
s_fd 4 | p4 ------/
------------
... ...
... ...
------------

调用dup2后状态为：
进程A的文件描述符表(after dup2)
------------
fd0 0 | p0
------------
n_fd 1 | p1 ------------
------------ \
fd2 2 | p2 \
------------ _\|
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------
s_fd 4 | p4 ------------->文件表1 ---------> vnode1
------------
... ...
... ...
------------
dup(fd)的语意是返回的新的文件描述符与fd共享一个文件表项。就如after dup图中的s_fd和fd1共享文件表1一样。

确定第二个方案后重定向后的恢复就很容易了，只需调用dup2(s_fd, n_fd);即可。下面是一个完整的例子程序：
#define TESTSTR "Hello dup2\n"
#define SIZEOFTESTSTR 11

int main() {
int fd3;
int s_fd;
int n_fd;

fd3 = open("testdup2.dat", 0666);
if (fd3 < 0) {
printf("open error\n");
exit(-1);
}

/* 复制标准输出描述符 */
s_fd = dup(STDOUT_FILENO);
if (s_fd < 0) {
printf("err in dup\n");
}

/* 重定向标准输出到文件 */
n_fd = dup2(fd3, STDOUT_FILENO);
if (n_fd < 0) {
printf("err in dup2\n");
}
write(STDOUT_FILENO, TESTSTR, SIZEOFTESTSTR); /* 写入testdup2.dat中 */

/* 重定向恢复标准输出 */
if (dup2(s_fd, n_fd) < 0) {
printf("err in dup2\n");
}
write(STDOUT_FILENO, TESTSTR, SIZEOFTESTSTR); /* 输出到屏幕上 */
return 0;
}
注意这里我在输出数据的时候我是用了不带缓冲的write库函数，如果使用带缓冲区的printf，则最终结果为屏幕上输出两行"Hello dup2"，而文件testdup2.dat中为空，原因就是缓冲区作怪，由于最终的目标是屏幕，所以程序最后将缓冲区的内容都输出到屏幕。

三、父子进程间的dup/dup2
由fork调用得到的子进程和父进程的相同文件描述符共享同一文件表项，如下图所示：
父进程A的文件描述符表
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------ /|\
fd2 2 | p2 |
------------ |
|
子进程B的文件描述符表 |
------------ |
fd0 0 | p0 |
------------ |
fd1 1 | p1 ---------------------|
------------
fd2 2 | p2
------------
所以恰当的利用dup2和dup可以在父子进程之间建立一条“沟通的桥梁”。这里不详述。

四、小结
灵活的利用dup/dup2可以给你带来很多强大的功能，花了一些时间总结出上面那么多，不知道自己理解的是否透彻，只能在以后的实践中慢慢探索了。

转载: http://blog.21ic.com/user1/6406/archives/2011/81684.html

simplyzhao 2011-10-08 15:57 发表评论

2011知识点 - overload与override

simplyzhao — Fri, 07 Oct 2011 11:11:00 GMT

override: 覆盖、重写
overload: 重载

虚函数总是在派生类中被改写，这种改写被称为“override”。我经常混淆“overload”和“override”这两个单词。澄清一下：

override是指派生类重写基类的虚函数，就象我们前面B类中重写了A类中的foo()函数。重写的函数必须有一致的参数表和返回值（C++标准允许返回值不同的情况，这个我会在“语法”部分简单介绍，但是很少编译器支持这个feature）。这个单词好象一直没有什么合适的中文词汇来对应，有人译为“覆盖”，还贴切一些。

overload约定成俗的被翻译为“重载”。是指编写一个与已有函数同名但是参数表不同的函数。例如一个函数即可以接受整型数作为参数，也可以接受浮点数作为参数。

simplyzhao 2011-10-07 19:11 发表评论

2011知识点 - 构造函数可以为虚函数吗

simplyzhao — Fri, 07 Oct 2011 11:06:00 GMT

答案是：不可以
原因：
概念上，虚函数的意图是动态绑定，程序会根据对象的动态类型来选择要调用的方法。然而在构造函数运行的时候，这个对象的动态类型还不完整(可以是基类，也可以是子类)，没有办法确定它到底是什么类型，故构造函数不能动态绑定。

实现上，vptr是构造函数设置的。通过vptr才能找到虚函数。
如果构造函数为虚函数，通过构造函数设置的vptr才能找到构造函数，然后调用它设置vptr，这是不可能实现的。

参考:

http://bbs.seu.edu.cn/wForum/disparticle.php?boardName=C_CPlusPlus&ID=17648

http://www.cppblog.com/guevara/articles/77360.html

simplyzhao 2011-10-07 19:06 发表评论

2011知识点 - 优先级反转

simplyzhao — Sat, 24 Sep 2011 16:33:00 GMT

前两天Marvell面试，被问到优先级反转是什么东东，无奈只能表示不会，还好面试官非常地NICE，很耐心地告诉我这是什么，还聊起NASA的火星探测器就因为优先级反转的原因出现过BUG，我就一直点头，还说回来会GOOGLE学习下

Priority Inversion 优先级反转是嵌入式实时系统里面的一个经典的问题。简单描述一下这个问题：有三个优先级不同的task,A,B,C; A的优先级最高，B次之，C最低。其中A和C有共享的临界区。如果C已进入临界区，那么A在进入进入临界区之前，就会被阻塞。task B有可能打断C而进入运行状态，这样C什么时候从临界区退出，就是一个未知的时间。A只有C从临界区退出后才能被调度，A被阻塞的时间也是未知的。这样，低优先级的B先于高优先级的A被调度，优先级发生了逆转。
这个问题在一般的操作系统里面不是一个严重的问题，最多A被多阻塞了一段时间。但是，在实时系统里面，如果一个任务在规定的时间里面没有被调度运行，系统就相当于失败了，可能引发系统崩溃。
解决这个问题有两种手段：
1：Priority inheritance(优先级继承)，如果一个高优先级的task被阻塞，与它共享临界区的低优先级的task在进入临界区后，优先级就会继承高优先级task的优先级，保证它不会被其他优先级次高的任务打断。从临界区退出后，C的优先级恢复正常。
2：A priority ceiling（最高优先级），给临界区分配最高优先级，如果一个task进入临界区，就把临界区的优先级赋给它，已保证它不会被打断。从临界区退出后，task的优先级恢复正常。

实时操作系统的一个特点就是，一个实时任务，会在规定的时间内得到响应，并且在规定的时间内完成任务。所以，一切不可预知的动作都是有害的。

有兴趣可以看看下面两个链接：
http://en.wikipedia.org/wiki/Priority_inversion
http://www.embedded.com/story/OEG20020321S0023

来源: http://www.kernelchina.org/node/210

simplyzhao 2011-09-25 00:33 发表评论

2011推理题 - 两个鸡蛋[zz]

simplyzhao — Sat, 24 Sep 2011 16:13:00 GMT

2 Egg Problem

继续我们的推理问题之旅，今天我们要对付的是一个Google的面试题：Two Egg Problem.

我们开始吧！

No.2 Google Interview Puzzle : 2 Egg Problem

* You are given 2 eggs.

* You have access to a 100-storey building.

* Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100^th floor. Both eggs are identical.

* You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process

分析与解答：

题目要求试的最大次数最小。首先，讨论两个比较trivial的方案。

方案1：从第一层开始扔鸡蛋，如果鸡蛋不碎，则上一层再扔。这样，如果鸡蛋在某一层碎的话，该层就是临界的层。这种方案的优点在于省鸡蛋，只会摔破一个鸡蛋。还有一个鸡蛋可以带回家，做个鸡蛋羹，补充营养个! :) 缺点就是，如果鸡蛋在100层才碎的话，那就要试100次啦。那你等电梯要等死啦，而且还要接受别人的打量的目光，心说这怪咖为什么每次都只坐一层楼啊…

方案2：想必很多人都会想到这个方案。我只能说，这是中国计算机教育的成功啊。这就是“二分查找法”。首先在第50层楼扔鸡蛋，如果鸡蛋不碎的话，就去75楼。如果碎了的话，那么对不起，同志。由于你只剩一个鸡蛋了，所以你得小心地从第一层开始，这样才能保证你在鸡蛋碎完的时候能找到临界楼层。这种方法的优势在于，如果你知道你的鸡蛋比较硬的话，你就采用这个方法吧。临界楼层越高，这个方法尝试的次数越小。但这种优势是用临界楼层比较小时比较大的尝试次数为代价获得的。我们看到，如果临界层数在49层的话，我们要尝试50次，而临界层数为100层的时候，尝试次数只有7次。但是，现在的问题是，全部情况下的最大尝试次数最小。这样，虽然在某些情况下，这种方法的性能很好。但是就最差情况而言，还是要尝试50次，好像还是有点大。这边，我们想起来，“二分查找法”的目标是平均性能最佳，并不是最差性能最佳。我们似乎走错了路！！！不过，方案二相比方案一来讲还是有进步的。

方案2似乎陷入了“短板效应”的泥沼，由于最坏情况下的坏性能制约了总体性能的提高。解决这个问题的总的原则应是：“一碗水端平”，尽量做到各种情况下的尝试次数尽量差不多。这正应合GOOGLE的信条Don't be evil，不以别的情况为代价换取另一些情况的指标的提高。做到“不伤害”.(呵呵，这是我瞎联想的)。那么，就照着这条路走吧，我假设每种情况下最大的尝试次数为x.

则第一次扔蛋的楼层应为x;

第二次扔蛋的楼层应为 x+(x-1);

…

依次类推。

从上面看到，每次我们增加的楼层都是前一次减1.我们所要保证的就是应该在增加的层数变成0之前到顶楼，所以有：

x+(x-1)+…+1≥100

这是一个等差数列，整理后有：

x²+x-200≥0

发现x≥14。

我们总结一下：

第一次在14楼扔，如果碎了的话从一楼再开始扔；

否则在14+13=27层扔，如果碎了的话从15层开始扔；

否则在27+12=39层扔，如果碎了的话从28层开始扔；

……

这样，最大尝试次数为14次就行了。不信你试试。

最后，为了体现严谨性，给出本题的模型：

转移方程：

minNum[n ] = min(1 + max(i – 1, minNum[n-i])) ，for 1≤i ≤n

边界条件:

minNum[0] = 0; minNum[1] = 1

这里，n为楼层数，i为起始楼层数。

据说这是一个动态规划问题，我还没来得及仔细研究。其实，我的感觉是，很多理论最初的来源都是很朴素的真理，只是我们没学懂，所以把它们想复杂了。所以，很好的理论就这样不被大多数人所理解了。

参考文献：

1. http://blog.csdn.net/TravelInHistory/archive/2006/12/07/1434098.aspx

2. http://classic-puzzles.blogspot.com/2006/12/google-interview-puzzle-2-egg-problem.html

simplyzhao 2011-09-25 00:13 发表评论