久久综合久久鬼色,色综合久久88色综合天天,亚洲香蕉网久久综合影视

2011扑ַ��ȝ��

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

扑ַ��Q�其实早�?1�q�十一月䆾��q��束了�Q�今天来补个�ȝ��?br />
11�q�九月下旬赶回去参加��势�U�技在南京的�W�试�Q��ƈ成功地在十一之前拿到offer�Q�记得从南京坐高铁回�Ӟ��怀里揣着��势的offer很是心安�Q�也�l�了自己很大的信心（因�ؓ�Q�一直觉得自�׃��q�州跑回南京上�v扑ַ�会处于劣势）�Q�至今对于趋势科技面试的轻松氛��_��包括最后的��面都印象深刻，是一家很nice的公司�?br />
休完十一假期��p��M��P��在上��复旦呆了个把月�Q�感谢舍友彭博帮我在复旦扑ֈ�落脚地�?br />在上��P��前前后后参加了很多的�W�试面试�Q�最�l�拿��C��满意的offer�Q�去了EMC�Q�尽量得�?000大洋的毁�U�费�?br />
推荐公司�Q�EMC�Q�TrendMicro�Q�Marvell

“�l�验”�Q?br />自信&微笑�Q�熟�l�掌握一门语�a�(如C)�Q�数据结构与��法(推荐《算法导论�?�Q�操作系�l?推荐《深入理解计��机�pȝ��?�Q�有个别“拿得出手”的小��目�Q�英�?br />
----------------------------------------------------------------------------------------------------------------
所有投递简历公叔R��镉K��的列�?排名按投递简历的旉��序)�Q?br />

1. ��q��?上�v
SH01 Software Design Engineer (上�v)

[已笔�? 通过��面, 攑ּ�]

2. ��势�U�技 Trend Micro (上�v)

软�g工程�?/div>

https://campus.trendmicro.com.cn

[已笔�? 已面�? OFFER]

3. Marvell (上�v)

[已笔试，已面试，OFFER]

4. 癑ֺ� (上�v)

[旉��冲突�Q�放弃]

5. 华�ؓ

软�g研发工程�?性能/��法工程�?/div>

[攑ּ�]

6. 飞利��?苏州 (上�v)

嵌入式��Y件开发工�E�师软�g应用开发工�E�师

[攑ּ�]

7. Google (上�v)

[攑ּ�]

8. nVidia �׃��?(上�v)

GPU Architect

[攑ּ�]

9. EMC (上�v)

Software Development Engineer 上�v

[已笔�? 已面�? OFFER]

10. AMD (上�v)

System Software Engineer

[木有�W�试��Z��]

11. 腾讯 (上�v)

后台开�?上�v

[已笔�? 已面�? OFFER]

12. 微��Y (上�v)

软�g开发工�E�师上�v

[旉��冲突�Q�放弃]

13 Samsung (南京)

手机开�?南京

[攑ּ�]

14 IBM CSTL (上�v)

storage software engineer

[没消息]

15. Intel (上�v)

zhaopin.com

[木有�W�试��Z��]

16. Cisco (上�v)

embedded software development engineer

[攑ּ�]

17. 大众点评�|?(上�v)

技术培训生 - 开�?/div>

[攑ּ�]

18. 阿尔卡特朗讯 (上�v)

[攑ּ�]

19. 支付�?(上�v)

[攑ּ�]

20. 中航无线�?(上�v)

[攑ּ�]

21. Oracle (上�v)

[已面试，��是�l�了OFFER]
22. 江苏�U�d��
[攑ּ�]

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

2011知识�?- 多态的C实现

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

�C�Z��代码:

/* 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 的矩�?其中每一行的数据都从左到��x��?每一列的数据都从上到下排�?Young 氏矩阵中可能会有一�?nbsp; ∞ 数据��?表示不存在的元素.所�?Young 氏矩阵可以用来存�?r<= mn 个有限的元素.
a).��M��个包含{9,16,3,2,4,8,5,14,12} �?*4 �?Young 氏矩�?

b).�l�出一个在非空 m*n �?Young 氏矩阵上实现 EXTRACT-MIN ��法,使其�q�行旉��为O(m+n).

c).说明如何在O(m+n)旉��?��一个新元素手入��C��个未满的 m*n Young 氏矩阵中.

d).�l�出一个时间复杂度�?O(n^3) 的对 n*n Young 氏矩阉|��序的��法.

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

�{?/p>

a). 2 3 4 5

8 9 12 14

16 ∞ ∞ ∞

∞ ∞ ∞ ∞

PS.该矩阵�ƈ不是唯一�?

b). (1)用递归的思想.�?Young 氏矩阵中�Q�通过递归的解�?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]; //�c�M��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)�c�M��堆的删除�Q�将Young[1][1]与最右下角元素交�? 然后�U�d��Young[1][1]处的元素臛_��适位�|�，��x��它与��x��或下方元素的比较,�q�与其中较小的一个交�?反复�q�行直到它不大于它右方和下方的元素�ؓ�?

c). �c�M��堆的插入�Q�先��待插入的元�?K 攑֜� Young[m][n], 然后比较 K 与它左方或上方元素的大小,�q�与其中较大的一个交�?反复�q�行直到 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 �q�程卛_��.

e). ��L��于最右上角的元素X比较�Q?br />1�Q�如�?=X,�l�束�Q?br />2�Q�如果比X��，那么元素只可能在前N-1列中�Q?br />3�Q�如果比X大，那么元素只可能在后M-1行中�Q?br />Young 氏矩阵去掉一行或一列还�?Young 氏矩阵；
所以每�ơ比较最��去掉一行或一列，�q�样复杂度就�?O(m+n);

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

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

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

思�\:
a. 比较自然的思�\是归�q�算法，不过旉��复杂度是O(n)�Q�无法满��题目要�?br />
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

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

有N个�h按照1到N�~�号围成一个圈做游�?br />从第一个�h开始从1报数,数到M的�h退出游�?他后面的人接着重新�?开�?em style="color: #d14836; font-style: normal; ">报数�Q�一直持�l�到所有�h都退�?/em>�Q?br />要求输出退出游戏的人的��序.

�q�题以前看过�Q�记得貌似有些数学规律的�Q�忘了，所以只能当场用模拟的方法来做�?br />当时用的是��@环数�l�来模拟�Q�结果花了半个小时才�~�译、测试搞定，面试我的�?挺Nice�?看了之后��_��{�案输出是对的，其实更自然的模拟是用链表�?br />刚才用链表试了下�Q�果然简单好多，大概五分钟就可以搞定�?br />

#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知识�?- 文�g描述�W?dup/dup2

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

文�g描述�W?font face="Arial Black" style="line-height: normal; ">----文�g�?/font>----v节点�l�构三者的联系

既然文�g描述�W�标识特定进�E�正在访问的文�g�Q�那�q�程跟文件是怎么联系��h��的呢�Q?/span>

首先我们得知道每�q�行一个进�E�，shell��׃��默认为其打开三个文�g描述�W?/font>(0,1,2)�Q�分别与标准输入(stdin)�Q�标准输�?/font>(stdout)和标准错�?/font>(stderr)对应�?/font>

接下来讲下内核所使用的三�U�数据结构，正是�q�三�U�数据结构才使进�E�最�l�跟文�g联系��h��?/span>��边看图一边看下面的文字描�q?/span>

a. 每个�q�程在进�E�表中都有一个记录项�Q�每个记录项中有一张打开文�g描述�W�表�Q�可��其视�ؓ一个矢量，每个描述�W�占用一��V�?br /> 与每个文件描�q�符相关联的是：(a) 文�g描述�W��?/span>(b) 指向一个文件表��的指针

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

c. 每个打开文�g�Q�或讑֤��Q�都有一�?/span>v节点�l�构�?/span>是文件的重要信息部分�?/span>

下图表示以上三个数据�l�构的关�p�：

fd1 = open(pathname, oflags);

fd2 = dup(fd1);

fd3 = open(pathname, oflags);

图一

dup/dup2
�怿�大部分在Unix/Linux下编�E�的�E�序员手头上都有《Unix环境高��~�程�?APUE)�q�本��l�典巨著。作者在该书中讲解dup/dup2之前曄��讲过“文�g�׃�n”�Q�这对理解dup/dup2�q�是很有帮助的。这里做��单摘录以备在后面的分析中使用�Q?br />Stevens said:
(1) 每个�q�程在进�E�表中都有一个记录项�Q�每个记录项中有一张打开文�g描述�W�表�Q�可��视��Z��个矢量，每个描述�W�占用一��V��与每个文�g描述�W�相兌��的是�Q?br />(a) 文�g描述�W�标志�?br />(b) 指向一个文件表��的指针�?br />(2) 内核为所有打开文�g�l�持一张文件表。每个文件表��包含：
(a) 文�g状态标�?诅R��写、增写、同步、非��d��{?�?br />(b) 当前文�g位移量�?br />(c) 指向该文件v节点表项的指针�?br />囄��Q?br />文�g描述�W�表
------------
fd0 0 | p0 -------------> 文�g�? ---------> vnode0
------------
fd1 1 | p1 -------------> 文�g�? ---------> vnode1
------------
fd2 2 | p2
------------
fd3 3 | p3
------------
... ...
... ...
------------

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

�l�下面调用：
n_fd = dup2(fd3, STDOUT_FILENO);后进�E�状态如下：

�q�程A的文件描�q�符�?after dup2)
------------
fd0 0 | p0
------------
n_fd 1 | p1 ------------
------------ \
fd2 2 | p2 \
------------ _\|
fd3 3 | p3 -------------> 文�g�? ---------> vnode2
------------
... ...
... ...
------------
解释如下�Q?br />n_fd = dup2(fd3, STDOUT_FILENO)表示n_fd与fd3�׃�n一个文件表��?它们的文件表指针指向同一个文件表��?�Q�n_fd在文件描�q�符表中的位�|��ؓ STDOUT_FILENO的位�|�，而原先的STDOUT_FILENO所指向的文件表��被关闭�Q�我觉得上图应该很清晰的反映��炏V��按照上面的解释我们 ��可以解释CU中提出的一些问题：
(1) "dup2的第一个参数是不是必须为已打开的合法filedes�Q? -- �{�案�Q�必��R�?br />(2) "dup2的第二个参数可以是�Q意合法范围的filedes��g��Q? -- �{�案�Q�可以，在Unix其取值区间�ؓ[0,255]�?br />
另外感觉理解dup2的一个好�Ҏ��是把fd看成一个结构体�c�d��Q�就如上面图形中�ȝ��那样�Q�我们不妨把之定义�ؓ�Q?br />struct fd_t {
int index;
filelistitem *ptr;
};
然后dup2匚w��index�Q�修改ptr�Q�完成dup2操作�?br />
在学习dup2时��L��到“重定�?#8221;一词，上图完成的就是一�?#8220;从标准输出到文�g的重定向”�Q�经�q�dup2后进�E�A的�Q何目标�ؓ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"�?br />
二、重定向后恢�?br />CU上有�q�样一个帖子，��是如何在重定向后再恢复原来的状态？首先大家都能惛_��要保存重定向前的文�g描述�W�。那么如何来保存呢，象下面这栯��么？
int s_fd = STDOUT_FILENO;
int n_fd = dup2(fd3, STDOUT_FILENO);
�q�是�q�样可以呢？
int s_fd = dup(STDOUT_FILENO);
int n_fd = dup2(fd3, STDOUT_FILENO);
�q�两�U�方法的区别到底在哪呢？�{�案是第二种�Ҏ��才是正确的，分析如下�Q�按照第一�U�方法，我们仅仅�?表面�?保存了相当于fd_t�Q�按照我前面说的理解�?法）中的index�Q�而在调用dup2之后�Q�ptr所指向的文件表��由于计数值已为零而被关闭了，我们如果再调用dup2(s_fd, fd3)��׃��出错(出错原因上面有解�?。而第二种�Ҏ��我们首先做一下复�Ӟ��复制后的状态如下图所�C?
�q�程A的文件描�q�符�?after dup)
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文�g�? ---------> vnode1
------------ /|
fd2 2 | p2 /
------------ /
fd3 3 | p3 -------------> 文�g�? ---------> vnode2
------------ /
s_fd 4 | p4 ------/
------------
... ...
... ...
------------

调用dup2后状态�ؓ�Q?br />�q�程A的文件描�q�符�?after dup2)
------------
fd0 0 | p0
------------
n_fd 1 | p1 ------------
------------ \
fd2 2 | p2 \
------------ _\|
fd3 3 | p3 -------------> 文�g�? ---------> vnode2
------------
s_fd 4 | p4 ------------->文�g�? ---------> vnode1
------------
... ...
... ...
------------
dup(fd)的语意是�q�回的新的文件描�q�符与fd�׃�n一个文件表��V��就如after dup图中的s_fd和fd1�׃�n文�g�?一栗��?br />
��定�W�二个方案后重定向后的恢复就很容易了�Q�只需调用dup2(s_fd, n_fd);卛_��。下面是一个完整的例子�E�序�Q?br />#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);
}

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

/* 重定向标准输出到文�g */
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); /* 输出到屏�q�上 */
return 0;
}
注意�q�里我在输出数据的时候我是用了不带缓冲的write库函敎ͼ�如果使用带缓冲区的printf�Q�则最�l�结果�ؓ屏幕上输��Z��?Hello dup2"�Q�而文件testdup2.dat中�ؓ�I�，原因��是�~�冲��Z��怪，�׃��最�l�的目标是屏�q�，所以程序最后将�~�冲区的内容都输出到屏幕�?br />

三、父子进�E�间的dup/dup2
由fork调用得到的子�q�程和父�q�程的相同文件描�q�符�׃�n同一文�g表项�Q�如下图所�C�：
父进�E�A的文件描�q�符�?br />------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文�g�? ---------> vnode1
------------ /|\
fd2 2 | p2 |
------------ |
|
子进�E�B的文件描�q�符�?|
------------ |
fd0 0 | p0 |
------------ |
fd1 1 | p1 ---------------------|
------------
fd2 2 | p2
------------
所以恰当的利用dup2和dup可以在父子进�E�之间徏立一�?#8220;沟通的桥梁”。这里不详述�?br />
四、小�l?br />灉|��的利用dup/dup2可以�l�你带来很多强大的功能，�׃��一些时间�ȝ��Z��面那么多�Q�不知道自己理解的是否透彻�Q�只能在以后的实践中慢慢探烦了�?br />

转蝲: 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: 覆盖、重�?br />overload: 重蝲

虚函数��L��在派生类中被改写�Q�这�U�改写被�U�Cؓ“override”。我�l�常��h��“overload”�?/span>“override”�q�两个单词。澄清一下：

override是指�z��c�重写基�cȝ��虚函敎ͼ��p��我们前面B�c�M��重写�?/span>A�c�M��?/span>foo()函数。重写的函数必须有一致的参数表和�q�回��|��C++标准允许�q�回��g��同的情况�Q�这个我会在“语法”部分��单介�l�，但是很少�~�译器支持这�?/span>feature�Q�。这个单词好象一直没有什么合适的中文词汇来对应，有�h译�ؓ“覆盖”�Q�还贴切一些�?/span>

overload�U�定成俗的被��译�?/span>“重蝲”。是指编写一个与已有函数同名但是参数表不同的函数。例如一个函数即可以接受整型��C��为参敎ͼ�也可以接受��Q�Ҏ��作�ؓ参数�?/span>

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

2011知识�?- 构造函数可以�ؓ虚函数吗

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

�{�案是：不可�?br />原因�Q?br />概念上，虚函数的意图是动态绑定，�E�序会根据对象的动态类型来选择要调用的�Ҏ��。然而在构造函数运行的时候，�q�个对象的动态类型还不完�?可以是基�c�，也可以是子类)�Q�没有办法确定它到底是什么类型，故构造函��C��能动态绑定�?br />
实现上，vptr是构造函数设�|�的。通过vptr才能扑ֈ�虚函数�?br />如果构造函��Cؓ虚函敎ͼ�通过构造函数设�|�的vptr才能扑ֈ�构造函敎ͼ�然后调用它设�|�vptr�Q�这是不可能实现的�?nbsp;

参�?

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

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

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

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

前两天Marvell面试�Q�被问到优先�U�反转是什么东东，无奈只能表示不会�Q�还好面试官非常地NICE�Q�很耐心地告诉我�q�是什么，�q�聊起NASA的火星探��器��因��Z��先��反�{的原因出现过BUG�Q?我就一直点��_��q�说回来会GOOGLE学习�?br />

Priority Inversion 优先�U�反转是嵌入式实时系�l�里面的一个经典的问题。简单描�q�C��下这个问题：有三个优先��不同的task,A,B,C; A的优先��最高，B�ơ之�Q�C最低。其中A和C有共享的临界区。如果C已进入��界区�Q�那么A在进入进入��界区之前�Q�就会被��d��。task B有可能打断C而进入运行状态，�q�样C什么时候从临界区退出，��是一个未知的旉��。A只有C从��界区退出后才能被调度，A被阻塞的旉��也是未知的。这��P��低优先��的B先于高优先��的A被调度，优先�U�发生了逆�{�?br />�q�个问题在一般的操作�pȝ��里面不是一个严重的问题�Q�最多A被多��d��了一�D�|��间。但是，在实时系�l�里面，如果一个�Q务在规定的时间里面没有被调度�q�行�Q�系�l�就相当于失败了�Q�可能引发系�l�崩溃�?br />解决�q�个问题有两�U�手�D�：
1�Q�Priority inheritance(优先�U��?�Q�如果一个高优先�U�的task被阻塞，与它�׃�n临界区的低优先��的task在进入��界区后，优先�U�就会��扉K��优先�U�task的优先��Q�保证它不会被其他优先��ơ高的�Q务打断。从临界区退出后�Q�C的优先��恢复正常�?br />2�Q�A priority ceiling�Q�最高优先��Q�，�l��界区分配最高优先��Q�如果一个task�q�入临界区，��把临界区的优先�U�赋�l�它�Q�已保证它不会被打断。从临界区退出后�Q�task的优先��恢复正常�?/p>

实时操作�pȝ��的一个特点就是，一个实时�Q务，会在规定的时间内得到响应�Q��ƈ且在规定的时间内完成��d��。所以，一切不可预知的动作都是有害的�?/p>

有兴��可以看看下面两个链接：
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

�l�箋我们的推理问题之旅，今天我们要对付的是一个Google的面试题�Q�Two Egg Problem.

我们开始吧�Q?nbsp;

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的方案�?/span>

�Ҏ��1�Q�从�W�一层开始扔鸡蛋�Q�如果鸡蛋不��，则上一层再扔。这��P��如果鸡蛋在某一层碎的话�Q�该层就是��界的层。这�U�方案的优点在于省鸡蛋，只会摔破一个鸡蛋。还有一个鸡蛋可以带回家�Q�做个鸡蛋羹�Q�补充营��M��! :) �~�点��是�Q�如果鸡蛋在100层才��的话，那就要试100�ơ啦。那你等甉|��要等��d��Q�而且�q�要接受别�h的打量的目光�Q�心说这怪咖��Z��么每�ơ都只坐一层楼�?#8230;

�Ҏ��2�Q?/span> 惛_��很多人都会想到这个方案。我只能��_��q�是中国计算机教育的成功啊。这��是“二分查找�?#8221;。首先在�W?/span>50层楼扔鸡蛋，如果鸡蛋不碎的话�Q�就�?/span>75楹{��如果碎了的话，那么对不��P��同志。由于你只剩一个鸡蛋了�Q�所以你得小心地从第一层开始，�q�样才能保证你在鸡蛋��完的时候能扑ֈ�临界楼层。这�U�方法的优势在于�Q�如果你知道你的鸡蛋比较��的话，你就采用�q�个�Ҏ��吧。��界楼层越高，�q�个�Ҏ��试的次数越��。但�q�种优势是用临界楼层比较��时比较大的��试�ơ数��Z��仯��得的。我们看刎ͼ�如果临界层数�?/span>49层的话，我们要尝�?/span>50�ơ，而��界层��Cؓ100层的时候，��试�ơ数只有7�ơ。但是，现在的问题是�Q�全部情况下的最大尝试次数最��。这��P��虽然在某些情况下�Q�这�U�方法的性能很好。但是就最差情况而言�Q�还是要��试50�ơ，好像�q�是有点大。这边，我们惌��v来，“二分查找�?#8221;的目标是�q�_��性能最佻I��q�不是最差性能最佟뀂我们似乎走错了路！�Q�！不过�Q�方案二相比�Ҏ��一来讲�q�是有进步的�?/span>

�Ҏ��2��g��陷入�?#8220;短板效应”的惔��|��׃��最坏情况下的坏性能制约了��M��性能的提高。解册��个问题的�ȝ��原则应是�Q?#8220;一��水端��^”�Q�尽量做到各�U�情况下的尝试次数尽量差不多。这正应�?/span>GOOGLE的信�?/span>Don't be evil�Q�不以别的情况�ؓ代�h换取另一些情�늚�指标的提高。做�?#8220;不伤�?#8221;.(呵呵�Q�这是我瞎联想的)。那么，��q��着�q�条路走吧，我假设每�U�情况下最大的��试�ơ数�?/span>x.

则第一�ơ扔蛋的楼层应�ؓx;

�W�二�ơ扔蛋的楼层应�ؓ x+(x-1);

…

依次�c�L��?/span>

从上面看刎ͼ�每次我们增加的楼层都是前一�ơ减1.我们所要保证的��是应该在增加的层数变成0之前到顶��|��所以有�Q?/span>

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

�q�是一个等差数列，整理后有�Q?/span>

x²+x-200≥0

发现x≥14�?/span>

我们�ȝ��一下：

�W�一�ơ在14楼扔�Q�如果碎了的话从一楼再开始扔�Q?/span>

否则�?/span>14+13=27层扔�Q�如果碎了的话从15层开始扔�Q?/span>

否则�?/span>27+12=39层扔�Q�如果碎了的话从28层开始扔�Q?/span>

……

�q�样�Q�最大尝试次��Cؓ14�ơ就行了。不信你试试�?/span>

最后，��Z��体现严�}性，�l�出本题的模型：

转移方程�Q?/span>

minNum[n ] = min(1 + max(i – 1, minNum[n-i])) �Q?/span>for 1≤i ≤n

边界条�g:

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

�q�里�Q?/span>n为楼层数�Q?/span>i��v始楼层数�?/span>

据说�q�是一个动态规划问题，我还没来得及仔细研究。其实，我的感觉是，很多理论最初的来源都是很朴素的真理�Q�只是我们没学懂�Q�所以把它们惛_��杂了。所以，很好的理论就�q�样不被大多��C�h所理解了�?/span>

参考文献：

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 发表评论