附录A 程序员工作面试的秘密

对硬件知识一知半解是非常危险的。
硅谷程序员面试
尖端计算机行业最值得称道的事情之一就是选择新雇员加入队伍的不寻常方法。
技术能力是你寻求工作面试时唯一重要的特长。
程序员面试就形成了一种非常独特的风格。

怎样才能检测到链表中存在循环
通常第一种答案：
对访问过的每个元素进行标记，继续编译这个链表，如果遇到某个已经标记过的元素，说明链表存在循环。
第二个限制：
这个链表只位于只读内存区域，无法在元素上做标记。
通常第二种答案：
当访问每个元素时，把它存储在一个数组中。检查每一个后继的元素，看看它是否已经存在于数组中。有时候，一些可怜的程序员会纠缠于如何用散列表来优化数组访问的细节，结果在这一关卡了壳。
第三个限制：
奥！内存空间非常有限，无法创建一个足够长度的数组。然而，可以假定如果链表中存在循环，它出现在前N个元素之中。
通常第三种答案（如果程序员能够到达这一步）
设置一个指针，指向链表的头部。在接下来对直到第N个元素的访问中，把N-1个元素一次同指针指向的元素进行比较。然后指针移向第二个元素，把它与后面的N-2个元素进行比较。根据这个方法依次进行比较，如果出现比较相等就说明前N个元素中存在循环，否则如果所有N个元素两两之间进行比较都不相等，说明链表中不存在循环。
第四个限制：
奥！不！链表的长度是任意的，而且循环可能出现在任何位置（即使是优秀的候选者也会在这一关碰壁）
最后的答案：
首先，排除一种特殊的情况，就是3个元素的链表中第二个元素的后面是第一个元素。
设置两个指针p1和p2,使p1指向第一个元素，p2指向第3个元素，看它们是否相等。如果相等就属于上述这种特殊情况。如果不等，把p1向后移一个位置，p2向后移两个元素。检验两个指针的值，如果相等，说明两个链表中存在循环。如果不相等，继续按照上述方法进行。如果出现两个指针都为NULL的情况，说明链表中不存在循环。如果链表中存在循环，用这种方法可能能检验出来，因为其中一个指针肯定能够追上另一个（两个指针具有相同的值），不过这可能要对这个链表经过几次遍历才能检测出来。

/*
**编程挑战  
*/
/*
寻找循环
证明上面最后一种方法可以检测链表中可能存在的任何循环。在链表中设置一个循环，演练一下你的代码；把循环变得
长一些，继续演练你的代码。重复进行，知道初始条件不满足为止。通过，确定链表中不存在循环时，算法可以终止。
提示：编写一个程序，然后依次往外推演。
*/
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0 

typedef int ELEMENT_TYPE;
struct NODE{
    ELEMENT_TYPE value;
    struct NODE *link;
}; 
int loop_in_link_list( struct NODE *p1, struct NODE *p2 );
int main( void ){
    struct NODE node, node2, node3;
    struct NODE node4, node5, node6;
    node.value = 1;
    node.link = &node2;
    node2.value = 2;
    node2.link = &node3;
    node.value = 3;
    node.link = &node4;
    node4.value = 4;
    node4.link = &node5;
    node5.value = 5;
    node5.link = &node6;
    node6.value = 6;
    node6.link = &node;
    int result = loop_in_link_list( &node, node.link->link );
    printf( "result = %d\n", result );
    
    return EXIT_SUCCESS;
}
int loop_in_link_list( struct NODE *p1, struct NODE *p2 ){
    /*p1 is the first element, p2 is the third element*/ 
    if( p1 ){ 
        if( !p2 ){ /*p2 is a null pointer*/ 
            return FALSE; 
        } else{ /*p2 is not a null pointer*/ 
            if( p1 == p2 ){ /*p1 is equal to p2 indicates a loop is in link list*/
                return TRUE;
            } else{
                p1 = p1->link;
                p2 = p2->link->link; 
                while( p2 && p1 ){
                    if( p2 == p1 ){
                        return TRUE;
                    } else{
                        p1 = p1->link;
                        p2 = p2->link->link; 
                    }
                }
                return FALSE;
            }
        }    
    } else{
        return FALSE;
    }
}

/* 输出：

*/ 

C语言中不同增值语句的区别何在
考虑下面4条语句
x = x + 1; /*正规形式*/
++x;       /*前缀自增*/
x++;       /*后缀自增*/
x += 1;    /*复合赋值*/
这4条语句的功能是相等的，它们都是把x的值增加1。如果像现在这样不考虑前后的上下文，它们之间并没有什么区别。应试者需要（隐式或显式地）提供适当的上下文环境，以便回答这个问题并找出这4条语句之间的区别。注意，最后一条语句是一种在算法语言中表达“x等于x加上1”的便捷方法。因此，这条语句仅供参考，我们需要寻找的是其余3条语句的独特性质。
但自增和自减操作在所有的硬件系统中的应用之广令人难以置信。
有些程序员则在此处未做深入考虑，忽略了当x不是一个简单的变量而是一个涉及数组的表达式时，像x += 1这样的形式很有用的。
如果你有一个复杂的数组引用，并需要证明同一种下标形式在两种引用中都可以使用，那么
node[i>>31] += -(0x01 << (i & 0x7));
就是你应该采用的方法。优秀的应试者还能够指出左值（定位一个对象的表达式的编译器用语---通常具有一个地址，但它既可能是一个寄存器，也可能是地址或寄存器加上一个位段）只被计算了一次。这一点非常重要，因为下面的语句：
mango[i++] += y;
被当做
mango[i] = mango[i] + y; i++;
而不是
mango[i++] = mango[i++] + y;
最好的那位候选人（他最终获得了这个工作---嗨！Arindam）解释说这些区别与编译器的中间代码有关，例如“++x”表示取x的地址，增加它的内容，然后把值放在寄存器中；“x++”则表示取x的地址，把它的值装入寄存器中，然后增加内存中的x的值。

编译器应该有一个选项，可以产生一个汇编指令列表。你也可以把编译器设置为调试模式，这样也常常可以更容易检查对应的C语言和汇编指令。不要使用优化选项，因为这些语句有可能因为优化而被精简掉。

frotz[--j + i++] += --y;
扩展为功能相同但长度更长的：
--y;
--j;
frotz[j + i] = frotz[j+i] + y;
i++;
教训：不要在一行代码里实现太多的功能
Kernihan和Plauger所指出的那样，“人人都知道调试比第一次编写代码要难上一倍。所以如果在编写代码时把自己的聪明发挥到极致，那么在调试时又该怎么办呢？”

库函数调用和系统调用区别何在
简明的回答是函数库调用是语言或应用程序的一部分，而系统调用是操作系统的一部分。你要确保弄懂“trap”（自陷）这个关键字的含义。系统调用是在操作系统内核发现一个trap或中断后进行的。这个问题的完整答案如以下要点。

                            函数库调用vs系统调用
函数库调用                                                                     系统调用
在所有的ANSI C编译器版本中，C函数库是相同的        各个操作系统的系统调用是不同的
它调用函数库中的一个程序                                            它调用系统内核的服务
与用户程序相联系                                                          是操作系统的一个进入点
在用户地址空间执行                                                       在内核地址空间执行
它的运行时间属于“用户”时间                                         它的运行时间属于“系统”时间
属于过程调用，开销较小                                               需要切换到内核上下文环境然后切换回                                                                                              来，开销较大
在C程序库libc中有大约300个程序                                 在UNIX中有大约90个系统调用（MS-DOS                                                                                         中少一些）
记录于UNIX OS手册的第三节                                       记录于UNIX OS手册的第二节
典型的C函数库调用：system、fprintf、malloc             典型的系统调用：chdir、fork、write、brk

/*
**编程挑战 
*/ 
警告：这个编程挑战对于有些读者可能过于艰巨
为下列各个问题编写程序。
1.读取一个字符串，并输出它里面字符的所有组合。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARR_SIZE 20
/*不好的解答，有重复的组合*/ 
void recursion_combination(const char *source, int source_len );
/*好的解答，没有重复的组合*/ 
/* 
例如：abc，它的所有字符组合为a,b,c,ab,ac,bc,abc
对于这种类型的题，想到的第一思路就是采用递归进行求解。
首先我们申请一个与所求字符串一样大小的字符数组s，用于保存各个字符的组合。
对于abc这样字符串的进行递归实现：
a,ab,abc,ac,b,bc,c
*/
/* 参考链接：https://blog.csdn.net/sanmao0816/article/details/45011597 */ 
int Recursion( char *str, char *s, int len, int m, int n );

int main( void ){
    /*方案01 
    char str[ARR_SIZE] = { '\0' };
    int arr_len; 
    int i, j;
    int counter;

    fgets( str, 20, stdin );
    arr_len = strlen( str );
    char *pnew = strchr( str, '\n' );
    if( pnew ){
        str[arr_len - 1] = '\0';
        arr_len = arr_len - 1;
    }
    printf( "arr_len = %d\n", arr_len );
    recursion_combination( str, arr_len );
    */
    /*方案02*/ 
    int len, i, j, m;
    char s[6]={0};
    char str[] = "12345";
    len = strlen( str );
    Recursion( str, s, len, 0, 0 );
    
    return EXIT_SUCCESS;
}

void recursion_combination(const char *source, int source_len ){
    if( source_len < 2 ){
        if( source_len == 0 ){
            return;
        } else if( source_len == 1 ){
            printf("%c\n", *source );
        } 
    } else{
        printf( "%s\n", source );
        /*用来存放剩余的字符*/ 
        char *temp = (char *)malloc( sizeof(char) * (source_len + 1 - 1) );
        temp[source_len - 1] = '\0';
        char *temp2 = (char *)malloc( sizeof(char) * (1 + 1) );
        temp2[1] = '\0';
        char *temp3 = (char *)malloc( sizeof(char) * (source_len + 1 - 1) );
        temp3[source_len - 1] = '\0';
        strncpy( temp, source + 1, source_len - 1 ); 
        strncpy( temp2, source, 1 );
        strncpy( temp3, source, 1 );
        strncpy( temp3 + 1, source + 2, source_len - 2 );
        recursion_combination( temp, strlen( temp ) );
        recursion_combination( temp2, strlen( temp2 ) );
        recursion_combination( temp3, strlen( temp3 ) );
        free( temp );
        free( temp2 );
        free( temp3 );
    }     
}

int Recursion( char *str, char *s, int len, int m, int n ){    
    int i;
    for(i = n; i < len; i++){
        if(i > n){ //当i>n说明，递归结束
            m--;
        }
        s[m] = str[i];
        s[++m] = '\0';
        printf("%s ",s);
        if( i < len - 1 ){
            Recursion( str, s, len, m, i+1 );
            /*printf( "str = %s, s = %s, len = %d, m = %d, i + 1 = %d\n", str, s, len, m, i + 1 );*/
        }
    }
}
/*参考链接的答案都看不明白，不过答案是正确的。如果你有能力明白，能不能告知我，多谢呢*/

/*输出：

*/ 

2.“八皇后”问题（假设棋盘上有8个皇后，要求打印所有使8个皇后不会相互攻击的棋子配置）。

#include <stdio.h>
#include <stdlib.h>

int checkerboard[8][8];    
void queen( int i, int j ); /* recursion function, it will quit until j >= 8 */
int chess( int i, int j );  /* check the conflict of the location */ 
int cas = 0;  /* record the successful schemes of location of eight queens */ 
void print_location( void ); /* print the location of queen of successfule scheme */ 

int main( void ){
    queen( 0, 0 ); 
    printf( "cas = %d\n", cas );

    return EXIT_SUCCESS;
}

void queen( int i, int j ){
    if( j >= 8 ){  /* if the offside oversteps the boundary */ 
        return;
    }
    if( chess( i, j ) == 1 ){ /* check whether the location can put into a queen */
        /* the location can put into a queen */
        checkerboard[i][j] = 1; /* set the location of a queen to one, indicate the location is occupied */
        if( i == 7 ){ /* check whether a queen arrives to the last line, if so, cas increases 1 */ 
            cas++;
            print_location();
        } else{
            queen( i + 1, 0 ); /* if not, continue to analy next line */
        } 
    } 
    /* 
    ** most important thing is here 
    ** If the location can't put into a queen，and then set the location to zero，judge latter location.
    ** set checkerboard[i][j] to zero to aviod to influence latter comparsion. 
    */
    checkerboard[i][j] = 0; 
    queen( i , j + 1 ); 
}

int chess( int i, int j ){
    int l;
    
    /* the same row can't put into more than one queen */ 
    for( l = 0; l < 8; ++l ){
        if( checkerboard[i][l] == 1 ){
            return 0;
        }
    }
    /* the same column can't put into more than one queen */ 
    for( l = 0; l < 8; ++l ){
        if( checkerboard[l][j] == 1 ){
            return 0;
        }
    }
    /*
    ** two diagonal lines can't put into more than one queen  
    */ 
    for( l = -8; l <= 8; l++ ){
        if( i + l >= 0 && i + l < 8 && j + l >= 0 && j + l < 8 ){ 
            /* diagonal line from left top to right bottom */
            if( checkerboard[i + l][j + l] == 1 ){
                return 0;
            }
        }
        if( i - l >= 0 && i - l < 8 && j + l >= 0 && j + l < 8 ){ /*从左下到右上对角线*/ 
            /* diagonal line from left bottom to right top */
            if( checkerboard[i + l][j + l] == 1){
                return 0;
            }
        } 
    }
    return 1;
}

void print_location( void ){/* print the location of queen of successfule scheme */
    int i, j;
    for( i = 0; i < 8; ++i ){
        for( j = 0; j < 8; ++j ){
            if( checkerboard[i][j] == 1 ){
                printf( "i = %d, j = %d\n", i, j );
            }
        }
    }
}

/* 输出：

*/ 

3.给定一个数N，要求列出所有不大于N的素数。

#include <stdio.h>
#include <stdlib.h>

#define N 1000

int main( void ){
    int n;
    
    n = N;
    while( n >= 2 ){
        int i;
        for( i = 2; i * i <= n; ++i ){
            if( n % i == 0 ){
                break;
            }
        }
        if( i * i > n ){
            printf( "%d ", n );
        }
        --n;
    }
    return EXIT_SUCCESS;
}

/* 输出：

*/ 

4.编写一个子程序，进行两个任意大小的矩阵乘法运算。 

/*
**将两个矩阵相乘。
*/ 
#include <stdio.h>
#include <stdlib.h>

void matrix_multiply( int *m1, int *m2, int *r, int x, int y, int z );
void print_matrix( int *m, int row, int column );

int main( void ){
    int a[3][2] = { { 2, -6 }, { 3, 5 }, { 1, -1 } };
    int b[2][4] = { { 4, -2, -4, -5 }, { -7, -3, 6, 7 } };
    int c[3][4];
    
    matrix_multiply( &a[0][0], &b[0][0], &c[0][0], 3, 2, 4 );
    print_matrix( &a[0][0], 3, 2 );
    printf( "\n" );
    print_matrix( &b[0][0], 2, 4 );
    printf( "\n" );
    print_matrix( &c[0][0], 3, 4 );
    
    return EXIT_SUCCESS;
}

void matrix_multiply( int *m1, int *m2, int *r, int x, int y, int z ){
    register int *m1p;
    register int *m2p;
    register int k;
    int row;
    int column;
    
    /*
    **外层的两个循环逐个产生结果矩阵的元素。由于这是按照存在顺序进行的， 
    **因此可以通过对r进行间接访问来访问这些元素。 
    */
    for( row = 0; row < x; row += 1 ){
        for( column = 0; column < z; column += 1 ){
            /*
            **计算结果的一个值。这是通过获得指向m1和m2的合适元素的指针，
            **在进行循环时，使它们前进来实现的。
            */
            m1p = m1 + row * y;
            m2p = m2 + column;
            *r = 0;
            
            for( k = 0; k < y; k += 1 ){
                *r += *m1p * *m2p;
                m1p += 1;
                m2p += z;
            } 
            
            /*
            **r前进一步，指向下一个元素。
            */
            r++; 
        }
    } 
}

void print_matrix( int *m, int row, int column ){
    int i, j;
    
    for( i = 0; i < row; ++i ){
        for( j = 0; j < column; ++j ){
            printf( "%4d", *m++ );
        }
        printf( "\n" ); 
    }
}

/*输出：

*/ 

库函数调用通常比行内展开的代码慢，因为它需要付出函数调用的开销。但系统调用比库函数调用还要慢很多，因为它需要把上下文环境切换到内核模式。纯粹从性能上考虑，你应该尽可能地减少系统调用的数量。但是，你必须记住，许多C函数库中的程序通过系统调用来实现功能。最后，那些相信麦田怪圈的人会对“system()函数实际上是一个库函数”这个概念感到困惑。

文件描述符与文件指针有何不同
所有操纵文件的UNIX程序或者使用文件指针或者使用文件描述符来标识它们正在操作的文件。它们是什么？什么时候应该使用？事实上答案非常直截了当，它取决于你对UNIX I/O的熟悉程度以及对各种因素利弊的权衡。
所有操作文件的系统调用都接受一个文件描述符作为参数，或者把它作为返回值返回。“文件描述符”这个名字多少显得有点命名不当。
在SunOS的编译器中，文件描述符是一个小整数（通常为0~255），用于索引开放文件的每个进程表（per-process table-of-open-files）。系统I/O调用有creat(), open(), read(), write(), close(), ioctl()等，但它们不是ANSI C的一部分，不会存在于非UNIX环境中。如果使用了它们，那么你的程序将失去可移植性。因此，建立一组标准I/O库调用是非常有必要的，ANSI C现在规定所有的编译环境都必须支持它们。

为了确保程序的可移植性，应该使用标准I/O库调用，如fopen(), fclose()、putc()、fseek()等---它们中的绝大多数名字中带有一个f。这些调用都接受一个类型为指向FILE结构的指针（有时称为流指针）的参数。FILE指针指向一个流结构，它在<stdio.h>中定义。
结构的内容根据不同的编译器有所不同，在UNIX中通常是开放文件的每个进程表的一个条目。在典型情况下，它包含了流缓冲区、所有用于提示缓冲区有多少字节是实际文件数据的变量以及提示流状态的标志（如ERROR和EOF）等。
*所以，文件描述符就是开放文件的每个进程表的一个偏移量。它用于UNIX系统调用中，用于表示文件。
*FILE指针保存一个FILE结构的地址。FILE结构用于表示开放的I/O流（如hex20938）。它用于ANSI C标准I/O库调用中，用于标识文件。
C库函数fdopen()可以用于创建一个新的FILE结构，并把它与一个确定的文件描述符关联（可以有效地在文件描述符小整数和对应的流指针间进行转换，虽然它并不在开放文件表中产生一个额外的新条目）。

编写一些代码，确定一个变量是有符号数还是无符号数
编写一些代码，确定一个变量是有符号数还是无符号数。要回答这个问题，你必须在特定的编译器中确定一个给定的类型是有符号数还是无符号数。
在ANSI C中，char类型既可以是有符号数，也可以是无符号数，这是由编译器决定的。当你编写代码需要移植到多个平台时，知道类型是不是有符号数就非常有用了。如果该类型在所有的编译器上编译时都是恒定的，那就再理想不过了。
你无法用函数实现目的。函数形式参数的类型是在函数内部定义的，所以它无法穿越调用这一关。因此，必须编写一个宏，根据参数的声明对它进行处理。
接下来就是区别宏的参数到底是一个类型还是一个类型的值。假定参数是一个值，无符号的数的本质特征是它永远不会是负的，有符号数的本质特征是对最左边一个位取补将会改变它的符号（比如2的补码，它肯定是个负数）。由于作为参数的这个值的其他位与这个测试无关，因此对它们全部取补后结果是一样的。因此，可以像下面这样尝试：
#define ISUNSIGNED(a) (a >= 0 && ~a >= 0)
如果宏的参数是一个类型，其中一个方法是使用类型转换：
#define ISUNSIGNED(type) ((type)0 - 1 > 0)
面试的关键就在于正确理解问题。第一个代码只适用于K&R C，新的类型提升规则导致它无法适用于ANSI C。

打印一棵二叉树的值的时间复杂度是多少
现在，关于复杂度理论首先需要知道的是大O表示法。O(N)表示当N（通常是需要处理的对象数量）增长时，处理时间几乎是按照线性增长的。关于复杂度理论其次需要知道的是在一棵二叉树中，所有操作的时间复杂度都是O(log(n))。所以，很多程序员不假思索地作出了作出了这个回答。错误！
这个问题有点类似于Dan Rather著名的“频率是什么，Kenneth？”问题---这个问题用于干扰、混淆和激怒对方而不是真的向对方咨询信息。要打印一棵二叉树所有结点的值，必须对它们逐个访问，所以时间复杂度为O(N)。

从文件中随机提取一个字符串
解决这个问题的经典方法是读取文件，然字符串进行计数，并记录每个字符串的偏移位置。然后，在1和字符串总数之间取一个随机数，根据选中字符串的偏移位置取出该字符串。
主考官设置了一个条件。他要求只能按顺序遍历文件一次，并且不能使用表格来存储所有字符串的偏移位置。对于这个问题，主考官的主要兴趣在于你如何解决问题的过程。如果你提问，他会给你一些提示，所以大多数面试者最终都能获得答案。主考官对你的满意程度取决于你获得答案的速度。
基本的技巧是在幸存的字符串中挑选，并在过程中不断更新。从计算的角度看，这个方法是非常低效的，所以它很容易被忽略。你打开文件并保存第一个字符串，此时就有了一个备选字符串，并有可能100%的可能性选中它。保存这个字符串，继续读入下一个字符串，这样就有了两个备选字符串，选中每个的可能性都是50%。选中其一并保存，然后丢弃另一个。再读入下一个字符串，按照新字符串33%的概率原先幸存的字符串67%的概率（它代表前两个字符串的幸存者），在两者之间选择一个，然后保存新选中的字符串。根据这个方法，依次对整个文件进行处理。在其中每一步，读入字符串N，在它（按照1/N的概率）和前一个幸存的字符串（按照(N-1)/N的概率）之间进行选择。当到达文件末尾的时候，最后一个幸存的字符串就是从整个文件中随机提取的那个字符串！
这是一个非常艰难的问题，你要么依靠可能少的提示获得答案，要么就预先做好充分准备，提前阅读这本书。

更多阅读材料
如果你喜欢这本书，你可能也会喜欢Bartholomev and the Oobleck,作者是Seuss博士（纽约，Random Houese, 1973）。
软件工程师如果细心阅读Bartholomev and the Oobleck，肯定能从中获益。
如果每位程序员只是偶尔玩弄Oobleck,这个世界则会美好许多。
事实就是如此。人类的最高目标是奋斗、寻求、创造。每位程序员应该寻找并抓住每一次机会，使自己...哇！写的太多了。