程序员面试(附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结构，并把它与一个确定的文件描述符相关联。