程序員面試(附2)

問題一：確定一個變量是有符號數還是無符號數：
首先signed int類型是有符號的：如果是正數，最高位是0，如果是負數最高位是1,。對於32為的機器來說其表示的范圍為：-2^31到2^31-1。
但是unsigned無符號類型的整數就是所有位參與計數，所以無符號位肯定是一個正數。對於32位的機器來說其表示的范圍為：0到2^32-1。
判斷該變量是否為有無符號的數，還不能用函數來判斷，因為函數對接受的參數或作隱式的轉換。這裡尤其注意一點：int和nusigned int做if比較時，有時會做隱式的類型轉換，得出超過預期的結果。
參考代碼：

 unsigned int a = 0;
 if(a < a-1) {
      printf("/nunsiged");
 }else{
      printf("/nsigned");
 }

分析：如果a為有符號數：那麼0<-1不成立，則會打印signed；
如果a是無符號數：那麼-1會轉換為無符號的整數，是一個非常大的數，則a 問題二：打印一棵二叉樹的值的時間復雜度：
這個問題是面試者在申請Intel編譯小組問到的。現在關於時間復雜度的理論，首先需要知道的是大O表示法。O(N)表示當N（通常是需要處理的的對象）增長時，處理時間幾乎是按線性增長的。類似，O(N*N)表示當N增長時，處理時間的增長要快的多，大致是按照N的平方增長。關於復雜度理論，我們其次需要知道的是在一棵二叉樹中，所有的操作時間的復雜度為O(logN)。所以很多程序員不假思索的回答了這個答案。結果：game over，錯誤。
因為面試官問的與二叉樹的插入，刪除和查詢等操作有所不同，是打印二叉樹的值，所以我們必須逐個訪問，其時間復雜度為O(N)。就和查詢一棵無序二叉樹一樣，也得遍歷整個二叉樹，所以其時間復雜度我O(N)，而不是我們平時想象的O(logN)（感覺有點兒坑）。
問題三：從文件中隨機提取一個字符串
這是Microsoft喜歡使用的問題之一。主考官要求面試者編寫一些代碼，實現從一個文件（文件的內容是許多字符串）中隨機提取一個字符串。
方案一：解決這個問題的經典方法就是讀取文件，對字符串進行計數，並記錄每個字符串的偏移位置。然後在1和字符總數之間取一個隨機數，根據選中字符串的偏移位置去除該字符串。但是很不幸，面試官要求只能按順序遍歷字符串一次。
方案二：最基本的技巧就是：在幸存的字符串中挑選，並在過程中不斷更新。從計算的角度看這個方法是非常低效的。
具體過程是：我們打開一個文件，讀取第一個字符，這樣我們就獲得了第一個字符，並有100%的可能性選中它，因為只有一個，也別無選擇，保存選中的數字；
接著讀取下一個數據，這樣就有兩個備選數據，我們有50%的幾率選擇其中任何一個，保存；
接著再讀取下一個字符：這樣該字符串和前面的67%的兩個字符串加起來就有33%幾率被選中；
這樣不斷的循環，最後可以得到一個隨機的字符，並且值遍歷了文件一遍。

通過概率的計算，你會發現每個字符被選中的概率是一樣的，並且是隨機的，因為有可能選中的是第一個字符，也可能是最後一個，或者是其中任意一個。這和抽簽的原理是一樣的，想想是不是這樣！

問題四：文件描述符與文件指針的區別

在linux系統中把設備和普通文件都看做是文件，要對文件操作就必須先打開文件，打開文件後會得到一個文件描述符，它是一個很小的正整數，是一個索引值，是一個小整數，其值在（0-255）之間。每個進程PCB（Process Control Block）中保存著一份文件描述符表，文件描述符就是這個表的索引，每個表項都有一個指向已打開文件的指針。所以文件描述符就是開放文件每個進程表的一個偏移量（如"3"）,用於文件標示。
缺點：系統I/0調用有create(),open(),read(),write(),close()等。它們不是ANSI C的一部分，所以移植性差，不能存在於非UNIX環境。但是現在的ANSI C規定所有的編譯器環境都必須支持它們。
文件指針：C語言中使用文件指針做I/O的句柄。文件指針指向進程用戶區中的一個被稱為FILE結構的數據結構。FILE結構包括一個緩沖區和一個文件描述符。而文件描述符是文件描述符表的一個索引，因此某種意義上說文件指針就是句柄的句柄，在windows系統中文件描述符被稱作文件句柄。所以FILE指針保存了一個FILE結構的地址。
FILE結構中含有文件描述符，那麼可以使用fopen來獲得文件指針，然後從文件指針獲取文件描述符，文件描述符應該是唯一的，
而文件指針卻不是唯一的，但是指向的對象是唯一的。
FILE的結構

struct _iobuf {
        char *_ptr;          //緩沖區當前指針
        int   _cnt;
        char *_base;         //緩沖區基址
        int   _flag;         //文件讀寫模式
        int   _file;         //文件描述符
        int   _charbuf;      //緩沖區剩余自己個數
        int   _bufsiz;       //緩沖區大小
        char *_tmpfname;
        };

C語言文件指針與文件描述符之間可以相互轉換：

int fileno( FILE *stream );//fileno()用來取得參數stream指定的文件流所使用的文件描述符。
FILE *fdopen(int fd,const char *mode);//創建一個新的FILE結構，並把它與一個確定的文件描述符相關聯。