程序員面試經典題精講：符號判斷、二叉樹複雜度、水庫採樣、文件描述符

題目一：判斷變量是否為無符號類型

核心：利用無符號數減 1 會下溢變成極大正數的特性。

unsigned int a = 0;
if (a < a - 1)  // 無符號：a-1 變 UINT_MAX，條件成立
    puts("unsigned");
else
    puts("signed");

陷阱：不能寫成函數，因參數傳遞會發生隱式類型轉換；int 與 unsigned 混合比較時 int 會隱式轉無符號，導致邏輯錯誤。

題目二：打印二叉樹所有節點值的時間複雜度

錯誤直覺：O(log n) —— 混淆了「查找/插入/刪除」的平均複雜度。

正確答案：O(n)。必須訪問每個節點恰好一次，無論樹是否平衡。同理，無序二叉樹查找也是 O(n)。

題目三：單次掃描從文件隨機抽取一行（水庫採樣）

演算法：第 i 行以 1/i 概率替換當前保留行。

char *reservoir_sampling(FILE *fp) {
    char *selected = NULL, buf[1024];
    size_t count = 0;
    while (fgets(buf, sizeof(buf), fp)) {
        ++count;
        if (rand() % count == 0) {  // 1/count 概率
            free(selected);
            selected = strdup(buf);
        }
    }
    return selected;  // 調用者負責 free
}

數學證明：第 k 行最終被選中概率 = 1/k * k/(k+1) * ... * (n-1)/n = 1/n，均勻隨機。

題目四：文件描述符 vs 文件指針

FILE 結構簡化版

struct _iobuf {
    char *_ptr;   // 緩衝區當前指針
    int _cnt;     // 緩衝區剩餘字節
    char *_base;  // 緩衝區基址
    int _flag;    // 標志位
    int _file;    // 文件描述符 fd
    int _charbuf;
    int _bufsiz;  // 緩衝區大小
    char *_tmpfname;
};

面試加分點

• 能說出 fd 0/1/2 對應 stdin/stdout/stderr。
• 理解 fork 後父子進程共享 fd 表項（引用計數+1），exec 會關閉 FD_CLOEXEC 標志的 fd。
• 知道 stdio 緩衝策略：終端行緩衝、文件塊緩衝、stderr 無緩衝。
• 能手寫 setvbuf 切換緩衝模式。