置頂隨筆
找工，其實(shí)早在11年十一月份就結(jié)束了，今天來(lái)補(bǔ)個(gè)總結(jié)。
11年九月下旬趕回去參加趨勢(shì)科技在南京的筆試，并成功地在十一之前拿到offer，記得從南京坐高鐵回家，懷里揣著趨勢(shì)的offer很是心安，也給了自己很大的信心（因?yàn)椋恢庇X(jué)得自己從廣州跑回南京上海找工會(huì)處于劣勢(shì)），至今對(duì)于趨勢(shì)科技面試的輕松氛圍，包括最后的群面都印象深刻，是一家很nice的公司。
休完十一假期就趕去上海，在上海復(fù)旦呆了個(gè)把月，感謝舍友彭博幫我在復(fù)旦找到落腳地。
在上海，前前后后參加了很多的筆試面試，最終拿到了滿意的offer，去了EMC，盡量得花5000大洋的毀約費(fèi)。
推薦公司：EMC，TrendMicro，Marvell
“經(jīng)驗(yàn)”：
自信&微笑，熟練掌握一門語(yǔ)言(如C)，數(shù)據(jù)結(jié)構(gòu)與算法(推薦《算法導(dǎo)論》)，操作系統(tǒng)(推薦《深入理解計(jì)算機(jī)系統(tǒng)》)，有個(gè)別“拿得出手”的小項(xiàng)目，英語(yǔ)
----------------------------------------------------------------------------------------------------------------
所有投遞簡(jiǎn)歷公司那長(zhǎng)長(zhǎng)的列表(排名按投遞簡(jiǎn)歷的時(shí)間順序)：
1. 愛(ài)立信 上海
SH01 Software Design Engineer (上海)
[已筆試, 通過(guò)群面, 放棄]
2. 趨勢(shì)科技 Trend Micro (上海)
軟件工程師
https://campus.trendmicro.com.cn
[已筆試, 已面試, OFFER]
3. Marvell (上海)
[已筆試，已面試，OFFER]
4. 百度 (上海)
[時(shí)間沖突，放棄]
5. 華為
軟件研發(fā)工程師 性能/算法工程師
[放棄]
6. 飛利浦 蘇州 (上海)
嵌入式軟件開(kāi)發(fā)工程師 軟件應(yīng)用開(kāi)發(fā)工程師
[放棄]
7. Google (上海)
[放棄]
8. nVidia 英偉達(dá) (上海)
GPU Architect
[放棄]
9. EMC (上海)
Software Development Engineer 上海
[已筆試, 已面試, OFFER]
10. AMD (上海)
System Software Engineer
[木有筆試機(jī)會(huì)]
11. 騰訊 (上海)
后臺(tái)開(kāi)發(fā) 上海
[已筆試, 已面試, OFFER]
12. 微軟 (上海)
軟件開(kāi)發(fā)工程師 上海
[時(shí)間沖突，放棄]
13 Samsung (南京)
手機(jī)開(kāi)發(fā) 南京
[放棄]
14 IBM CSTL (上海)
storage software engineer
[沒(méi)消息]
15. Intel (上海)
zhaopin.com
[木有筆試機(jī)會(huì)]
16. Cisco (上海)
embedded software development engineer
[放棄]
17. 大眾點(diǎn)評(píng)網(wǎng) (上海)
技術(shù)培訓(xùn)生 - 開(kāi)發(fā)
[放棄]
18. 阿爾卡特朗訊 (上海)
[放棄]
19. 支付寶 (上海)
[放棄]
20. 中航無(wú)線電 (上海)
[放棄]
21. Oracle (上海)
[已面試，算是給了OFFER]
22. 江蘇移動(dòng)
[放棄]
下半年就要正式找工了，淘寶的實(shí)習(xí)因?yàn)闋敔斎ナ捞崆案嬉欢温洹?br />
書籍
編程語(yǔ)言： 《C和指針》，《C專家編程》，《C++ Primer》，《Effective C++》
數(shù)據(jù)結(jié)構(gòu)與算法： 《算法導(dǎo)論》，《編程珠璣》，《編程之美》
操作系統(tǒng): 《操作系統(tǒng)》，《深入理解計(jì)算機(jī)系統(tǒng)》，《Linux內(nèi)核設(shè)計(jì)與實(shí)現(xiàn)》
計(jì)算機(jī)網(wǎng)絡(luò): 《TCP/IP詳解 卷一》
編程實(shí)踐
常用數(shù)據(jù)結(jié)構(gòu)，排序，搜索，圖算法，動(dòng)態(tài)規(guī)劃，字符串等
參考： PKU已做題目，何海濤的面試100題，IT面試題
2012年2月27日
找工，其實(shí)早在11年十一月份就結(jié)束了，今天來(lái)補(bǔ)個(gè)總結(jié)。
11年九月下旬趕回去參加趨勢(shì)科技在南京的筆試，并成功地在十一之前拿到offer，記得從南京坐高鐵回家，懷里揣著趨勢(shì)的offer很是心安，也給了自己很大的信心（因?yàn)椋恢庇X(jué)得自己從廣州跑回南京上海找工會(huì)處于劣勢(shì)），至今對(duì)于趨勢(shì)科技面試的輕松氛圍，包括最后的群面都印象深刻，是一家很nice的公司。
休完十一假期就趕去上海，在上海復(fù)旦呆了個(gè)把月，感謝舍友彭博幫我在復(fù)旦找到落腳地。
在上海，前前后后參加了很多的筆試面試，最終拿到了滿意的offer，去了EMC，盡量得花5000大洋的毀約費(fèi)。
推薦公司：EMC，TrendMicro，Marvell
“經(jīng)驗(yàn)”：
自信&微笑，熟練掌握一門語(yǔ)言(如C)，數(shù)據(jù)結(jié)構(gòu)與算法(推薦《算法導(dǎo)論》)，操作系統(tǒng)(推薦《深入理解計(jì)算機(jī)系統(tǒng)》)，有個(gè)別“拿得出手”的小項(xiàng)目，英語(yǔ)
----------------------------------------------------------------------------------------------------------------
所有投遞簡(jiǎn)歷公司那長(zhǎng)長(zhǎng)的列表(排名按投遞簡(jiǎn)歷的時(shí)間順序)：
1. 愛(ài)立信 上海
SH01 Software Design Engineer (上海)
[已筆試, 通過(guò)群面, 放棄]
2. 趨勢(shì)科技 Trend Micro (上海)
軟件工程師
https://campus.trendmicro.com.cn
[已筆試, 已面試, OFFER]
3. Marvell (上海)
[已筆試，已面試，OFFER]
4. 百度 (上海)
[時(shí)間沖突，放棄]
5. 華為
軟件研發(fā)工程師 性能/算法工程師
[放棄]
6. 飛利浦 蘇州 (上海)
嵌入式軟件開(kāi)發(fā)工程師 軟件應(yīng)用開(kāi)發(fā)工程師
[放棄]
7. Google (上海)
[放棄]
8. nVidia 英偉達(dá) (上海)
GPU Architect
[放棄]
9. EMC (上海)
Software Development Engineer 上海
[已筆試, 已面試, OFFER]
10. AMD (上海)
System Software Engineer
[木有筆試機(jī)會(huì)]
11. 騰訊 (上海)
后臺(tái)開(kāi)發(fā) 上海
[已筆試, 已面試, OFFER]
12. 微軟 (上海)
軟件開(kāi)發(fā)工程師 上海
[時(shí)間沖突，放棄]
13 Samsung (南京)
手機(jī)開(kāi)發(fā) 南京
[放棄]
14 IBM CSTL (上海)
storage software engineer
[沒(méi)消息]
15. Intel (上海)
zhaopin.com
[木有筆試機(jī)會(huì)]
16. Cisco (上海)
embedded software development engineer
[放棄]
17. 大眾點(diǎn)評(píng)網(wǎng) (上海)
技術(shù)培訓(xùn)生 - 開(kāi)發(fā)
[放棄]
18. 阿爾卡特朗訊 (上海)
[放棄]
19. 支付寶 (上海)
[放棄]
20. 中航無(wú)線電 (上海)
[放棄]
21. Oracle (上海)
[已面試，算是給了OFFER]
22. 江蘇移動(dòng)
[放棄]
2011年10月20日
示例代碼:
/* 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");
}
2011年10月16日
轉(zhuǎn):
一個(gè) m*n 的 Young 氏矩陣(Young tableau) 是一個(gè) m*n 的矩陣,其中每一行的數(shù)據(jù)都從左到右排序,每一列的數(shù)據(jù)都從上到下排序.Young 氏矩陣中可能會(huì)有一些 ∞ 數(shù)據(jù)項(xiàng),表示不存在的元素.所以,Young 氏矩陣可以用來(lái)存放 r<= mn 個(gè)有限的元素.
a).畫一個(gè)包含{9,16,3,2,4,8,5,14,12} 的4*4 的 Young 氏矩陣.b).給出一個(gè)在非空 m*n 的 Young 氏矩陣上實(shí)現(xiàn) EXTRACT-MIN 算法,使其運(yùn)行時(shí)間為O(m+n).
c).說(shuō)明如何在O(m+n)時(shí)間內(nèi),將一個(gè)新元素手入到一個(gè)未滿的 m*n Young 氏矩陣中.
d).給出一個(gè)時(shí)間復(fù)雜度為 O(n^3) 的對(duì) n*n Young 氏矩陣排序的算法.
e).給出一個(gè)運(yùn)行時(shí)間為O(m+n) 的算法,來(lái)決定一個(gè)給定的數(shù)是否存在于一個(gè)給定的 m*n 的 Young 氏矩陣當(dāng)中.
答
a). 2 3 4 5
8 9 12 14
16 ∞ ∞ ∞
∞ ∞ ∞ ∞
PS.該矩陣并不是唯一的.
b). (1)用遞歸的思想.在 Young 氏矩陣中，通過(guò)遞歸的解決(m-1)*n,或m*(n-1) 的子問(wèn)題來(lái)求解.則有 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的寫法.函數(shù)名即是返回值.
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]與最右下角元素交換, 然后移動(dòng)Young[1][1]處的元素至合適位置，即把它與右方或下方元素的比較,并與其中較小的一個(gè)交換.反復(fù)進(jìn)行直到它不大于它右方和下方的元素為止.
c). 類似堆的插入：先將待插入的元素 K 放在 Young[m][n], 然后比較 K 與它左方或上方元素的大小,并與其中較大的一個(gè)交換.反復(fù)進(jìn)行直到 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: 矩陣已滿,無(wú)法插入!!
while(k<Young[m-1][n] or k<Young[m][n-1])
if(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). 調(diào)用 n*n 次 EXTRACT_MIN 過(guò)程即可.
e). 總是于最右上角的元素X比較；
1）如果==X,結(jié)束；
2）如果比X小，那么元素只可能在前N-1列中；
3）如果比X大，那么元素只可能在后M-1行中；
Young 氏矩陣去掉一行或一列還是 Young 氏矩陣；
所以每次比較最少去掉一行或一列，這樣復(fù)雜度就是 O(m+n);
問(wèn)題:
有兩個(gè)已排好序的數(shù)組A和B，長(zhǎng)度均為n，找出這兩個(gè)數(shù)組的中間元素。要求時(shí)間代價(jià)為O(logn)
思路:
a. 比較自然的思路是歸并算法，不過(guò)時(shí)間復(fù)雜度是O(n)，無(wú)法滿足題目要求
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 m<n, then reserve the half of sequence A in which all numbers are greater than
m, 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)
2011年10月11日
昨天去面試，結(jié)果中間還插了一個(gè)小時(shí)的上機(jī)(給個(gè)laptop，Windows+VC環(huán)境，用慣Vim結(jié)果好不習(xí)慣^_^)，其中一題如下：
有N個(gè)人按照1到N編號(hào)圍成一個(gè)圈做游戲
從第一個(gè)人開(kāi)始從1報(bào)數(shù),數(shù)到M的人退出游戲,他后面的人接著重新從1開(kāi)始報(bào)數(shù)，一直持續(xù)到所有人都退出．
要求輸出退出游戲的人的順序.
這題以前看過(guò)，記得貌似有些數(shù)學(xué)規(guī)律的，忘了，所以只能當(dāng)場(chǎng)用模擬的方法來(lái)做。
當(dāng)時(shí)用的是循環(huán)數(shù)組來(lái)模擬，結(jié)果花了半個(gè)小時(shí)才編譯、測(cè)試搞定，面試我的人(挺Nice的)看了之后說(shuō)，答案輸出是對(duì)的，其實(shí)更自然的模擬是用鏈表。
剛才用鏈表試了下，果然簡(jiǎn)單好多，大概五分鐘就可以搞定。
#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;
}
2011年10月8日
文件描述符----文件表----v節(jié)點(diǎn)結(jié)構(gòu)三者的聯(lián)系
既然文件描述符標(biāo)識(shí)特定進(jìn)程正在訪問(wèn)的文件，那進(jìn)程跟文件是怎么聯(lián)系起來(lái)的呢？
首先我們得知道每運(yùn)行一個(gè)進(jìn)程，shell就會(huì)默認(rèn)為其打開(kāi)三個(gè)文件描述符(0,1,2)，分別與標(biāo)準(zhǔn)輸入(stdin)，標(biāo)準(zhǔn)輸出(stdout)和標(biāo)準(zhǔn)錯(cuò)誤(stderr)對(duì)應(yīng)。
接下來(lái)講下內(nèi)核所使用的三種數(shù)據(jù)結(jié)構(gòu)，正是這三種數(shù)據(jù)結(jié)構(gòu)才使進(jìn)程最終跟文件聯(lián)系起來(lái)。建議邊看圖一邊看下面的文字描述
a. 每個(gè)進(jìn)程在進(jìn)程表中都有一個(gè)記錄項(xiàng)，每個(gè)記錄項(xiàng)中有一張打開(kāi)文件描述符表，可將其視為一個(gè)矢量，每個(gè)描述符占用一項(xiàng)。
與每個(gè)文件描述符相關(guān)聯(lián)的是：(a) 文件描述符。(b) 指向一個(gè)文件表項(xiàng)的指針
b. 內(nèi)核為所有打開(kāi)文件維持一張文件表。每個(gè)文件表項(xiàng)包含：(a) 文件狀態(tài)標(biāo)志。(b) 當(dāng)前文件位移量。(c) 指向該文件v節(jié)點(diǎn)表項(xiàng)的指針。
c. 每個(gè)打開(kāi)文件（或設(shè)備）都有一個(gè)v節(jié)點(diǎn)結(jié)構(gòu)。是文件的重要信息部分。
下圖表示以上三個(gè)數(shù)據(jù)結(jié)構(gòu)的關(guān)系：
fd1 = open(pathname, oflags);
fd2 = dup(fd1);
fd3 = open(pathname, oflags);
圖一
dup/dup2
相信大部分在Unix/Linux下編程的程序員手頭上都有《Unix環(huán)境高級(jí)編程》(APUE)這本超級(jí)經(jīng)典巨著。作者在該書中講解dup/dup2之前曾經(jīng)講過(guò)“文件共享”，這對(duì)理解dup/dup2還是很有幫助的。這里做簡(jiǎn)單摘錄以備在后面的分析中使用：
Stevens said:
(1) 每個(gè)進(jìn)程在進(jìn)程表中都有一個(gè)記錄項(xiàng)，每個(gè)記錄項(xiàng)中有一張打開(kāi)文件描述符表，可將視為一個(gè)矢量，每個(gè)描述符占用一項(xiàng)。與每個(gè)文件描述符相關(guān)聯(lián)的是：
(a) 文件描述符標(biāo)志。
(b) 指向一個(gè)文件表項(xiàng)的指針。
(2) 內(nèi)核為所有打開(kāi)文件維持一張文件表。每個(gè)文件表項(xiàng)包含：
(a) 文件狀態(tài)標(biāo)志(讀、寫、增寫、同步、非阻塞等)。
(b) 當(dāng)前文件位移量。
(c) 指向該文件v節(jié)點(diǎn)表項(xiàng)的指針。
圖示：
文件描述符表
------------
fd0 0 | p0 -------------> 文件表0 ---------> vnode0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------
fd2 2 | p2
------------
fd3 3 | p3
------------
... ...
... ...
------------
一、單個(gè)進(jìn)程內(nèi)的dup和dup2
假設(shè)進(jìn)程A擁有一個(gè)已打開(kāi)的文件描述符fd3，它的狀態(tài)如下：
進(jìn)程A的文件描述符表(before dup2)
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------
fd2 2 | p2
------------
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------
... ...
... ...
------------
經(jīng)下面調(diào)用：
n_fd = dup2(fd3, STDOUT_FILENO);后進(jìn)程狀態(tài)如下：
進(jìn)程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共享一個(gè)文件表項(xiàng)(它們的文件表指針指向同一個(gè)文件表項(xiàng))，n_fd在文件描述符表中的位置為 STDOUT_FILENO的位置，而原先的STDOUT_FILENO所指向的文件表項(xiàng)被關(guān)閉，我覺(jué)得上圖應(yīng)該很清晰的反映出這點(diǎn)。按照上面的解釋我們 就可以解釋CU中提出的一些問(wèn)題：
(1) "dup2的第一個(gè)參數(shù)是不是必須為已打開(kāi)的合法filedes？" -- 答案：必須。
(2) "dup2的第二個(gè)參數(shù)可以是任意合法范圍的filedes值么？" -- 答案：可以，在Unix其取值區(qū)間為[0,255]。
另外感覺(jué)理解dup2的一個(gè)好方法就是把fd看成一個(gè)結(jié)構(gòu)體類型，就如上面圖形中畫的那樣，我們不妨把之定義為：
struct fd_t {
int index;
filelistitem *ptr;
};
然后dup2匹配index，修改ptr，完成dup2操作。
在學(xué)習(xí)dup2時(shí)總是碰到“重定向”一詞，上圖完成的就是一個(gè)“從標(biāo)準(zhǔn)輸出到文件的重定向”，經(jīng)過(guò)dup2后進(jìn)程A的任何目標(biāo)為STDOUT_FILENO的I/O操作如printf等，其數(shù)據(jù)都將流入fd3所對(duì)應(yīng)的文件中。下面是一個(gè)例子程序：
#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;
}
其結(jié)果就是你在testdup2.dat中看到"Hello dup2"。
二、重定向后恢復(fù)
CU上有這樣一個(gè)帖子，就是如何在重定向后再恢復(fù)原來(lái)的狀態(tài)？首先大家都能想到要保存重定向前的文件描述符。那么如何來(lái)保存呢，象下面這樣行么？
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);
這兩種方法的區(qū)別到底在哪呢？答案是第二種方案才是正確的，分析如下：按照第一種方法，我們僅僅在"表面上"保存了相當(dāng)于fd_t（按照我前面說(shuō)的理解方 法）中的index，而在調(diào)用dup2之后，ptr所指向的文件表項(xiàng)由于計(jì)數(shù)值已為零而被關(guān)閉了，我們?nèi)绻僬{(diào)用dup2(s_fd, fd3)就會(huì)出錯(cuò)(出錯(cuò)原因上面有解釋)。而第二種方法我們首先做一下復(fù)制，復(fù)制后的狀態(tài)如下圖所示:
進(jìn)程A的文件描述符表(after dup)
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------ /|
fd2 2 | p2 /
------------ /
fd3 3 | p3 -------------> 文件表2 ---------> vnode2
------------ /
s_fd 4 | p4 ------/
------------
... ...
... ...
------------
調(diào)用dup2后狀態(tài)為：
進(jìn)程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)的語(yǔ)意是返回的新的文件描述符與fd共享一個(gè)文件表項(xiàng)。就如after dup圖中的s_fd和fd1共享文件表1一樣。
確定第二個(gè)方案后重定向后的恢復(fù)就很容易了，只需調(diào)用dup2(s_fd, n_fd);即可。下面是一個(gè)完整的例子程序：
#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);
}
/* 復(fù)制標(biāo)準(zhǔn)輸出描述符 */
s_fd = dup(STDOUT_FILENO);
if (s_fd < 0) {
printf("err in dup\n");
}
/* 重定向標(biāo)準(zhǔn)輸出到文件 */
n_fd = dup2(fd3, STDOUT_FILENO);
if (n_fd < 0) {
printf("err in dup2\n");
}
write(STDOUT_FILENO, TESTSTR, SIZEOFTESTSTR); /* 寫入testdup2.dat中 */
/* 重定向恢復(fù)標(biāo)準(zhǔn)輸出 */
if (dup2(s_fd, n_fd) < 0) {
printf("err in dup2\n");
}
write(STDOUT_FILENO, TESTSTR, SIZEOFTESTSTR); /* 輸出到屏幕上 */
return 0;
}
注意這里我在輸出數(shù)據(jù)的時(shí)候我是用了不帶緩沖的write庫(kù)函數(shù)，如果使用帶緩沖區(qū)的printf，則最終結(jié)果為屏幕上輸出兩行"Hello dup2"，而文件testdup2.dat中為空，原因就是緩沖區(qū)作怪，由于最終的目標(biāo)是屏幕，所以程序最后將緩沖區(qū)的內(nèi)容都輸出到屏幕。
三、父子進(jìn)程間的dup/dup2
由fork調(diào)用得到的子進(jìn)程和父進(jìn)程的相同文件描述符共享同一文件表項(xiàng)，如下圖所示：
父進(jìn)程A的文件描述符表
------------
fd0 0 | p0
------------
fd1 1 | p1 -------------> 文件表1 ---------> vnode1
------------ /|\
fd2 2 | p2 |
------------ |
|
子進(jìn)程B的文件描述符表 |
------------ |
fd0 0 | p0 |
------------ |
fd1 1 | p1 ---------------------|
------------
fd2 2 | p2
------------
所以恰當(dāng)?shù)睦胐up2和dup可以在父子進(jìn)程之間建立一條“溝通的橋梁”。這里不詳述。
四、小結(jié)
靈活的利用dup/dup2可以給你帶來(lái)很多強(qiáng)大的功能，花了一些時(shí)間總結(jié)出上面那么多，不知道自己理解的是否透徹，只能在以后的實(shí)踐中慢慢探索了。
轉(zhuǎn)載:
http://blog.21ic.com/user1/6406/archives/2011/81684.html
2011年10月7日
override: 覆蓋、重寫
overload: 重載
虛函數(shù)總是在派生類中被改寫，這種改寫被稱為“override”。我經(jīng)常混淆“overload”和“override”這兩個(gè)單詞。澄清一下：
override是指派生類重寫基類的虛函數(shù)，就象我們前面B類中重寫了A類中的foo()函數(shù)。重寫的函數(shù)必須有一致的參數(shù)表和返回值（C++標(biāo)準(zhǔn)允許返回值不同的情況，這個(gè)我會(huì)在“語(yǔ)法”部分簡(jiǎn)單介紹，但是很少編譯器支持這個(gè)feature）。這個(gè)單詞好象一直沒(méi)有什么合適的中文詞匯來(lái)對(duì)應(yīng)，有人譯為“覆蓋”，還貼切一些。
overload約定成俗的被翻譯為“重載”。是指編寫一個(gè)與已有函數(shù)同名但是參數(shù)表不同的函數(shù)。例如一個(gè)函數(shù)即可以接受整型數(shù)作為參數(shù)，也可以接受浮點(diǎn)數(shù)作為參數(shù)。
答案是：不可以
原因：
概念上，
虛函數(shù)的意圖是動(dòng)態(tài)綁定，程序會(huì)根據(jù)對(duì)象的動(dòng)態(tài)類型來(lái)選擇要調(diào)用的方法。然而在構(gòu)造函數(shù)運(yùn)行的時(shí)候，這個(gè)對(duì)象的動(dòng)態(tài)類型還不完整(可以是基類，也可以是子類)，沒(méi)有辦法確定它到底是什么類型，故構(gòu)造函數(shù)不能動(dòng)態(tài)綁定。
實(shí)現(xiàn)上，vptr是構(gòu)造函數(shù)設(shè)置的。通過(guò)vptr才能找到虛函數(shù)。
如果構(gòu)造函數(shù)為虛函數(shù)，通過(guò)構(gòu)造函數(shù)設(shè)置的vptr才能找到構(gòu)造函數(shù)，然后調(diào)用它設(shè)置vptr，這是不可能實(shí)現(xiàn)的。
參考:
2011年9月25日
前兩天Marvell面試，被問(wèn)到優(yōu)先級(jí)反轉(zhuǎn)是什么東東，無(wú)奈只能表示不會(huì)，還好面試官非常地NICE，很耐心地告訴我這是什么，還聊起NASA的火星探測(cè)器就因?yàn)閮?yōu)先級(jí)反轉(zhuǎn)的原因出現(xiàn)過(guò)BUG， 我就一直點(diǎn)頭，還說(shuō)回來(lái)會(huì)GOOGLE學(xué)習(xí)下
Priority Inversion 優(yōu)先級(jí)反轉(zhuǎn)是嵌入式實(shí)時(shí)系統(tǒng)里面的一個(gè)經(jīng)典的問(wèn)題。簡(jiǎn)單描述一下這個(gè)問(wèn)題：有三個(gè)優(yōu)先級(jí)不同的task,A,B,C; A的優(yōu)先級(jí)最高，B次之，C最低。其中A和C有共享的臨界區(qū)。如果C已進(jìn)入臨界區(qū)，那么A在進(jìn)入進(jìn)入臨界區(qū)之前，就會(huì)被阻塞。task B有可能打斷C而進(jìn)入運(yùn)行狀態(tài)，這樣C什么時(shí)候從臨界區(qū)退出，就是一個(gè)未知的時(shí)間。A只有C從臨界區(qū)退出后才能被調(diào)度，A被阻塞的時(shí)間也是未知的。這樣，低優(yōu)先級(jí)的B先于高優(yōu)先級(jí)的A被調(diào)度，優(yōu)先級(jí)發(fā)生了逆轉(zhuǎn)。
這個(gè)問(wèn)題在一般的操作系統(tǒng)里面不是一個(gè)嚴(yán)重的問(wèn)題，最多A被多阻塞了一段時(shí)間。但是，在實(shí)時(shí)系統(tǒng)里面，如果一個(gè)任務(wù)在規(guī)定的時(shí)間里面沒(méi)有被調(diào)度運(yùn)行，系統(tǒng)就相當(dāng)于失敗了，可能引發(fā)系統(tǒng)崩潰。
解決這個(gè)問(wèn)題有兩種手段：
1：Priority inheritance(優(yōu)先級(jí)繼承)，如果一個(gè)高優(yōu)先級(jí)的task被阻塞，與它共享臨界區(qū)的低優(yōu)先級(jí)的task在進(jìn)入臨界區(qū)后，優(yōu)先級(jí)就會(huì)繼承高優(yōu)先級(jí)task的優(yōu)先級(jí)，保證它不會(huì)被其他優(yōu)先級(jí)次高的任務(wù)打斷。從臨界區(qū)退出后，C的優(yōu)先級(jí)恢復(fù)正常。
2：A priority ceiling（最高優(yōu)先級(jí)），給臨界區(qū)分配最高優(yōu)先級(jí)，如果一個(gè)task進(jìn)入臨界區(qū)，就把臨界區(qū)的優(yōu)先級(jí)賦給它，已保證它不會(huì)被打斷。從臨界區(qū)退出后，task的優(yōu)先級(jí)恢復(fù)正常。
實(shí)時(shí)操作系統(tǒng)的一個(gè)特點(diǎn)就是，一個(gè)實(shí)時(shí)任務(wù)，會(huì)在規(guī)定的時(shí)間內(nèi)得到響應(yīng)，并且在規(guī)定的時(shí)間內(nèi)完成任務(wù)。所以，一切不可預(yù)知的動(dòng)作都是有害的。
有興趣可以看看下面兩個(gè)鏈接：
http://en.wikipedia.org/wiki/Priority_inversion
http://www.embedded.com/story/OEG20020321S0023
來(lái)源:
http://www.kernelchina.org/node/210
繼續(xù)我們的推理問(wèn)題之旅，今天我們要對(duì)付的是一個(gè)Google的面試題：Two Egg Problem.
我們開(kāi)始吧！
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 100th 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
分析與解答：
題目要求試的最大次數(shù)最小。首先，討論兩個(gè)比較trivial的方案。
方案1：從第一層開(kāi)始扔雞蛋，如果雞蛋不碎，則上一層再扔。這樣，如果雞蛋在某一層碎的話，該層就是臨界的層。這種方案的優(yōu)點(diǎn)在于省雞蛋，只會(huì)摔破一個(gè)雞蛋。還有一個(gè)雞蛋可以帶回家，做個(gè)雞蛋羹，補(bǔ)充營(yíng)養(yǎng)個(gè)! :) 缺點(diǎn)就是，如果雞蛋在100層才碎的話，那就要試100次啦。那你等電梯要等死啦，而且還要接受別人的打量的目光，心說(shuō)這怪咖為什么每次都只坐一層樓啊…
方案2： 想必很多人都會(huì)想到這個(gè)方案。我只能說(shuō)，這是中國(guó)計(jì)算機(jī)教育的成功啊。這就是“二分查找法”。首先在第50層樓扔雞蛋，如果雞蛋不碎的話，就去75樓。如果碎了的話，那么對(duì)不起，同志。由于你只剩一個(gè)雞蛋了，所以你得小心地從第一層開(kāi)始，這樣才能保證你在雞蛋碎完的時(shí)候能找到臨界樓層。這種方法的優(yōu)勢(shì)在于，如果你知道你的雞蛋比較硬的話，你就采用這個(gè)方法吧。臨界樓層越高，這個(gè)方法嘗試的次數(shù)越小。但這種優(yōu)勢(shì)是用臨界樓層比較小時(shí)比較大的嘗試次數(shù)為代價(jià)獲得的。我們看到，如果臨界層數(shù)在49層的話，我們要嘗試50次，而臨界層數(shù)為100層的時(shí)候，嘗試次數(shù)只有7次。但是，現(xiàn)在的問(wèn)題是，全部情況下的最大嘗試次數(shù)最小。這樣，雖然在某些情況下，這種方法的性能很好。但是就最差情況而言，還是要嘗試50次，好像還是有點(diǎn)大。這邊，我們想起來(lái)，“二分查找法”的目標(biāo)是平均性能最佳，并不是最差性能最佳。我們似乎走錯(cuò)了路！！！不過(guò)，方案二相比方案一來(lái)講還是有進(jìn)步的。
方案2似乎陷入了“短板效應(yīng)”的泥沼，由于最壞情況下的壞性能制約了總體性能的提高。解決這個(gè)問(wèn)題的總的原則應(yīng)是：“一碗水端平”，盡量做到各種情況下的嘗試次數(shù)盡量差不多。這正應(yīng)合GOOGLE的信條Don't be evil，不以別的情況為代價(jià)換取另一些情況的指標(biāo)的提高。做到“不傷害”.(呵呵，這是我瞎聯(lián)想的)。那么，就照著這條路走吧，我假設(shè)每種情況下最大的嘗試次數(shù)為x.
則第一次扔蛋的樓層應(yīng)為x;
第二次扔蛋的樓層應(yīng)為 x+(x-1);
…
依次類推。
從上面看到，每次我們?cè)黾拥臉菍佣际乔耙淮螠p1.我們所要保證的就是應(yīng)該在增加的層數(shù)變成0之前到頂樓，所以有：
x+(x-1)+…+1≥100
這是一個(gè)等差數(shù)列，整理后有：
x2+x-200≥0
發(fā)現(xiàn)x≥14。
我們總結(jié)一下：
第一次在14樓扔，如果碎了的話從一樓再開(kāi)始扔；
否則在14+13=27層扔，如果碎了的話從15層開(kāi)始扔；
否則在27+12=39層扔，如果碎了的話從28層開(kāi)始扔；
……
這樣，最大嘗試次數(shù)為14次就行了。不信你試試。
最后，為了體現(xiàn)嚴(yán)謹(jǐn)性，給出本題的模型：
轉(zhuǎn)移方程：
minNum[n ] = min(1 + max(i – 1, minNum[n-i])) ，for 1≤i ≤n
邊界條件:
minNum[0] = 0; minNum[1] = 1
這里，n為樓層數(shù)，i為起始樓層數(shù)。
據(jù)說(shuō)這是一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，我還沒(méi)來(lái)得及仔細(xì)研究。其實(shí)，我的感覺(jué)是，很多理論最初的來(lái)源都是很樸素的真理，只是我們沒(méi)學(xué)懂，所以把它們想復(fù)雜了。所以，很好的理論就這樣不被大多數(shù)人所理解了。
參考文獻(xiàn)：
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