首先说明，这些面试题是我自己看书和面试的经历和在网上找的，我自己感觉可能会对找工作的同学有意义就记录下来了，同时，我不能保证答案的正确性和最优性，只是做一个参考。
一：
当在浏览器中输入一个 url 后回车，后台发生了什么？
比如输入 后，你看到了人人网登陆登陆首页
那么这一切是如何发生的呢？
答：简单来说有以下步骤：
1. 查找域名对应的IP地址。这一步会依次查找浏览器缓存，系统缓存，路由器缓存，ISP DNS缓存，根域名服务器。
2. 向IP对应的服务器发送请求。
3. 服务器响应请求，发回网页内容。
4. 浏览器解析网页内容。
当然，由于网页可能有重定向，或者嵌入了图片，AJAX，其它子网页等等，这4个步骤可能反复进行多次才能将最终页面展示给用户。
二：
要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。（题目还给出了一系列的数据，比如：站点数总共为5000万，IP地址有1000万，等等）
答：DNS服务器实现域名到IP地址的转换。
每个域名的平均长度为25个字节（估计值），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。总共50M个条目，所以需要1.5G个字节的空间。可以放置在内存中。（考虑到每秒5000次操作的限制，也只能放在内存中。）
可以考虑的数据结构包括hash_map，字典树，红黑树等等。
三：给定字符串，从中提取出单词。
比如：“I love you， meng ever！ ” 提取出的单词为I love you meng ever
答：这个题其实不难，就是C标准库里面的strtok函数所能完成的功能。
如下代码：
char *strtok_r(char *string, const char *control, char **lasts)
{
unsigned char *str;
const unsigned char *ctrl = control;
unsigned char map[32];
int count;
// Clear control map
for (count = 0; count < 32; count++) map[count] = 0;
// Set bits in delimiter table
do { map[*ctrl >> 3] |= (1 << (*ctrl & 7)); } while (*ctrl++);
// Initialize str. If string is NULL, set str to the saved
// pointer (i.e., continue breaking tokens out of the string
// from the last strtok call)
if (string)
str = string;
else
str = *lasts;
// Find beginning of token (skip over leading delimiters). Note that
// there is no token iff this loop sets str to point to the terminal
// null (*str == '\0')
while ((map[*str >> 3] & (1 << (*str & 7))) && *str) str++;
string = str;
// Find the end of the token. If it is not the end of the string,
// put a null there
for ( ; *str ; str++)
{
if (map[*str >> 3] & (1 << (*str & 7)))
{
*str++ = '\0';
break;
}
}
// Update nexttoken
*lasts = str;
// Determine if a token has been found.
if (string == str)
return NULL;
else
return string;
}
char *strtok(char *string, const char *control)
{
return strtok_r(string, control, &gettib()->nexttoken);
}
四：1024! 末尾有多少个0？以及1024！结果从右往左看第一个非0数字数
什么？
答：这个题我暑期实习的时候出过，不难，1024！末尾就是计算5个个数。
代码如下：
int count_zero_numbers(int N)
int ret = 0;
while(N) {
ret += N / 5;
N /= 5;
}
return ret;
}
计算第一个非零数字就是利用2将5消掉，需要扫描一遍。
五：给定能随机生成整数1到5的函数，写出能随机生成整数1到7的函数。
答：此题的关键是让生成的 1 到 7 的数出现概率相同。
产生K个数(k>1) 假定产生的数分别为n1,n2,n3,n4...
那么定义产生的数为n1-1+（n2-2）*5+（n3-1）*5^2+（n4-1）*5^3........
于是产生的数位于区间（0，5^k-1)然后把5^k分成k等分，产生的数位于哪个等分就是那个产生的随机数（0~6），然后+1即可如果位于k等分的余数范围，则重新执行一次上述过程
不用担心余数问题，当k取3时落到余数范围的概率就已经降低为6/125
代码如下：
int rand7() {
int a;
while((a = rand5() * 5 + rand5()) > 26);
return (a - 3) / 3;
}
大概解释一下：
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等
2. 只需要前面 3*7 个数，所以舍弃后面的4个数
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3
特别提示：随机生成7个1~5之间的数，相加后再模7加1这种方法是错误的，因为他们生成的概率不是随机的
六：
编程实现两个正整数的除法，当然不能用除法操作符。
// return x/y.
int div(const int x, const int y) {
....
}
答：代码如下：
int div(const int x, const int y) {
int left_num = x;
int result = 0;
while (left_num >= y) {
int multi = 1;
while (y * multi <= (left_num >> 1)) {
multi = multi << 1;
}
result += multi;
left_num -= y * multi;
}
return result;
}
PS：可以用二分法对加速，提高效率。同时大家还可以思考一下
如何求出a%b的值，要求不能使用除法和求模运算！
七：
写程序找出二叉树的深度。
一个树的深度等于max（左子树深度，右子树深度）+1。可以使用递归实现。
假设节点为定义为
struct Node {
Node* left;
Node* right;
};
int GetDepth(Node* root) {
if (NULL == root)
return 0;
int left_depth = GetDepth(root->left);
int right_depth = GetDepth(root->right);
return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}
八：
站在地球上的某一点，向南走一公里，然后向东走一公里，最后向北走一公里，回到了原点。地球上有多少个满足这样条件的点?
答：北极点满足这个条件。
距离南极点很近的一个圈上也满足这个条件。在这个圆圈上，向南走一公里，然后向东走一公里恰好绕南极点一圈，向北走一公里回到原点。所以地球上总共有无数点满足这个件。
九：
给定一个数据流，其中包含无穷尽的搜索关键字（比如，人们在谷歌搜索时不断输入的关键字）。如何才能从这个无穷尽的流中随机的选取1000个关键字？
答：TAOCP第二册第三章上的经典算法，"随机取样和洗牌算法"
定义长度为1000的数组。
对于数据流中的前1000个关键字，显然都要放到数组中。
对于数据流中的的第n（n>1000）个关键字，我们知道这个关键字被随机选中的概率为 1000/n。所以我们以 1000/n 的概率用这个关键字去替换数组中的随机一个。这样就可以保证所有关键字都以 1000/n的概率被选中。对于后面的关键字都进行这样的处理，这样我们就可以保证数组中总是保存着1000个随机关键字。
十：
将一个句子按单词反序，比如 “I love meng”，反序后变为 “meng love I”。
答案：关于本题解答，programing pearls 上面有仔细讲解
具体额实现为可以分两步走：
第一步按找字母反序，I love meng” 变为 “gnem evol I”。
第二部将每个单词中的字母反序，“gnem evol I” 变成 "meng love I”。
这个方法可以在原字符串上进行，只需要几个整数变量来保持指针即可，空间复杂度低。