Leetcode 编程训练
Leetcode这个网站上的题都是一些经典的公司用来面试应聘者的面试题，很多人通过刷这些题来应聘一些喜欢面试算法的公司，比如：Google、微软、Facebook、Amazon之类的这些公司，基本上是应试教育的功利主义。
我做这些题目的不是为了要去应聘这些公司，而是为了锻炼一下自己的算法和编程能力。因为我开始工作的时候基本没有这样的训练算法和编程的网站，除了大学里的“算法和数据结构”里的好些最基础最基础的知识，基本上没有什么训练。所以，当我看到有人在做这些题的时候，我也蠢蠢欲动地想去刷一下。
于是，我花了3-4个月的业余时间，我把Leetcode的154道题全部做完了。（这也是最近我没有太多的时间来写博客的原因，你可以看到我之前做的那个活动中有几个算法题来自于Leetcode）有人说我时间太多了，这里声明一下，我基本上都是利用了晚上10点以后的时间来做这些题的。
LeetCode的题大致分成两类：
1）基础算法的知识。这些题里面有大量的算法题，解这些题都是有套路的，不是用递归（深度优先DFS，广度优先BFS），就是要用动态规划（Dynamic Programming），或是拆半查找（ ...
C++面试中string类的一种正确写法
（感谢网友 @bnu_chenshuo 投稿）
C++ 的一个常见面试题是让你实现一个 String 类，限于时间，不可能要求具备 std::string 的功能，但至少要求能正确管理资源。具体来说：
能像 int 类型那样定义变量，并且支持赋值、复制。
能用作函数的参数类型及返回类型。
能用作标准库容器的元素类型，即 vector/list/deque 的 value_type。（用作 std::map 的 key_type 是更进一步的要求，本文从略）。
换言之，你的 String 能让以下代码编译运行通过，并且没有内存方面的错误。
void foo(String x)
{
}
void bar(const String& x)
{
}
String baz()
{
String ret("world");
return ret;
}
int main()
{
String s0;
String s1("hello");
String s2(s0);
String s3 = s1;
s2 = s1;
foo(s1);
...
为什么我反对纯算法面试题
算法面试可能是微软搞出来的面试方法，现在很多公司都在效仿，而且我们的程序员也乐于解算法题，我个人以为，这是应试教育的毒瘤！我在《再谈“我是怎么招程序员”》中比较保守地说过，“问难的算法题并没有错，错的很多面试官只是在肤浅甚至错误地理解着面试算法题的目的。”，今天，我想加强一下这个观点——我反对纯算法题面试！（注意，我说的是纯算法题）
图片源Wikipedia（点击图片查看词条）
我再次引用我以前的一个观点——
能解算法题并不意味着这个人就有能力就能在工作中解决问题，你可以想想，小学奥数题可能比这些题更难，但并不意味着那些奥数能手就能解决实际问题。
好了，让我们来看一个示例（这个示例是昨天在微博上的一个讨论），这个题是——“找出无序数组中第2大的数”，几乎所有的人都用了O(n)的算法，我相信对于我们这些应试教育出来的人来说，不用排序用O(n)算法是很正常的事，连我都不由自主地认为O(n)算法是这个题的标准答案。我们太习惯于标准答案了，这是我国教育最悲哀的地方。（广义的洗脑就是让你的意识依赖于某个标准答案，然后通过给你标准答案让你不会思考而控制你）
目录
...
一个fork的面试题
前两天有人问了个关于Unix的fork()系统调用的面试题，这个题正好是我大约十年前找工作时某公司问我的一个题，我觉得比较有趣，写篇文章与大家分享一下。这个题是这样的：
题目：请问下面的程序一共输出多少个“-”？
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
int main(void)
{
int i;
for(i=0; i<2; i++){
fork();
printf("-");
}
wait(NULL);
wait(NULL);
return 0;
}
如果你对fork()的机制比较熟悉的话，这个题并不难，输出应该是6个“-”，但是，实际上这个程序会很tricky地输出8个“-”。
要讲清这个题，我们首先需要知道fork()系统调用的特性，
fork()系统调用是Unix下以自身进程创建子进程的系统调用，一次调用，两次返回，如果返回是0，则是子进程，如果返回值>0，则是父进程（ ...
给程序员新手的一些建议
前段时间因为实习生计划花了很多时间做了实习生招聘的工作，产生的一些想法，写在这里。
这次招聘过程中，我发现我们在校的学生有下面的这些特点：
1）NB的项目。当说到自己做过的项目时， 我发现他们做的事都是很NB。要么是研究Linux的底层内核，要么是图像识别处理，要么是推荐算法，要么做高性能计算，要么做数据挖掘，要么是移动方面的协议，还有一些很高深的课题我听不太懂的项目。这让我想起当年我在学校里的实习，对比起我用Java Applet 和 HTML做操作系统的教学课件，或是在公司里用Delphi/PowerBuilder做的那些MIS系统。让我觉得有些汗颜。
2）OK的解决问题能力。当问到算法题时，我发现他们的问题解决能力还OK。我一般问1到2个中低难度的算法题和1个基本的面向对象设计的题，都不难。我相信只要在学校里好好学习的人都应该答得出来。无非就是一些基本的算法和基本数据结构操作的问题，和比较基础的面向对象设计的题，说白了就是作业题。可惜的是，只有5%不到的同学能够在不给提示的情况下答出来，70%的人可以在给一定的提示下答出来，15%左右的同学需要提示到几乎给出答案才能答出来，还有 ...
再谈“我是怎么招聘程序员的”（上）
我以前写过一篇“我是怎么招聘程序员的”的文章（在CSDN那里有很多人进行了回复）。今天，我想再谈谈关于招聘和面试这方面的东西，主要是以下这些原因：
近半年来我在进行了大量的招聘工作，对面试有一些新的体会。
酷壳最近发布了几篇趣味面试题（面试题一，面试题二，面试题三），从回复中让我有一些思考。
我有一个同事最近面试了一家公司，他和我分享了一个博士专家对他的面试，也让我思考了一些。
在豆瓣上看到“知乎上某人写面试豆瓣产品经理的经历，很欢乐”(亮点是面试官现身知乎亲自作答)
所以，我很想把自己的这些新的想法再次写下来的。还是和以前一样，这篇文章同样是献给面试官的。我认为，面试的好坏完全在面试官而不是面试的人。下面是我对“我是怎么招聘程序员的”一文中的一些加强性的观点。（关于一些点评，请参看本文下篇）
为了让我的文章有连续性，请允许我重申一下前文的几个重要观点。
只有应聘者真实和自然的表现，才能了解到最真实的东西
重要的不是知识，重要的是其查找知识的能力
重要的不是那个解题的答案，而是解题的思路和方法
操作，知识，经验，能力
我们有很多的面试官似乎分不清，什么是操作能力 ...
再谈“我是怎么招聘程序员的”（下）
<<<再谈“我是怎么招聘程序员的”（上）
在上篇中，我们说到了一些认识人的方法（操作，知识，经验，能力），还有一些面试的方法（算法题，实际生产活动中的挑战），下面我们来说说，面试的风格，还有一些点评。
把应聘者当成你的同事
有些公司的面试官，在面试过程中问你一个算法题，然后等着你解答了，如果你给出一个答案，然后就会问你有没有更好的答案，如果你给出了正确的答案，他们就会问你一个更难的问题，如此循环下去。他们基本上很少给你提示，甚至不停地质问你，挑战你，搞得应聘者很紧张。
另外，有很多问题是没有标准答案的，或者说是，同一个答案的描述方法有多种，很多面试官会觉得你没有回答到他想要的答案，因此表现得有对你不屑，并表现出你不行的样子，并觉得你的能力有问题。真是可笑了。比如我一个朋友在回答什么是异步的问题时，举例说明了异步调用就是不能处理完就返回，并且需要传递一个回调函数给调用方以便完成后回调通知结果。这样的回答并没有错，但是这并不符合面试官心里想要的答案，面试官对此并不满意，进而认为我这个朋友还需要去多读读书。
我相信大多数面试官都会这样干的。我想问问这样的面试官，你们有没有 ...
面试题：火车运煤问题
这个可能是一个比较经典的智力题了，和以前的那个《赛马问题》很相似，其题目如下：
你是山西的一个煤老板，你在矿区开采了有3000吨煤需要运送到市场上去卖，从你的矿区到市场有1000公里，你手里有一列烧煤的火车，这个火车最多只能装1000吨煤，且其能耗比较大——每一公里需要耗一吨煤。请问，作为一个懂编程的煤老板的你，你会怎么运送才能运最多的煤到集市？
这道题一开始看上去好像是无解的，因为你的火车每一公里就要消耗一吨煤，而到目的地有1000公里，而火车最多只能装1000吨媒。如果你的火车可以全部装下，到目的地也会被全部烧光，一丁点也不剩。所以，很多人的第一反应都是觉得这个不太可能。
如果你一开始就觉得不太可能的话，这是很正常的。不过我不知道你还会不会继续思考下去，如果你不想思考下去了，那么我很为你担忧，因为你可能并不是一个不善于思考的人，而是一个畏难的人，还有可能是一个容易放弃的人。这对于你做好 一个需要大量思考的工作的程序员来说可能并不适合。
我一开始也觉得不可能，后来想了一想，想到一个解法可以最多运送500吨煤到市场，方法如下：（希望你先自己想一想再查看这个答案）
//
又一个有趣的面试题
大家还记得前些天的那个火柴棍式的面试题吗？很有趣吧。下面是我今天在StackExchange上看到的一个有趣的面试题。大家不妨一起来思考一下。问题如下——
有两个相同功能代码如下，请在在A，B，C是什么的情况下，请给出三个原因case 1比case 2快，还有三个原因case 2会比case 1要执行的快。（不考虑编译器优化）
for (i=0; i<N; ++i){
A;
B;
C;
}
for (i=0; i<N; ++i){
A;
}
for (i=0; i<N; ++i){
B;
}
for (i=0; i<N; ++i){
C;
}
我的第一个反应是——
case1 要快一些，因为只有一个i++的i<N的操作，而case 2却有三个，这在点上，case 1就比case 2要快。
case2如果要快的话，有一个原因是，A, B, C其中一个需要去先获得一个资源（比如一个锁），在case1下，每次都要去拿这个资源，而case2下，只需要拿一次然后。但这个可能是不对的，因为我无法想出一个相同 ...
“火柴棍式”程序员面试题
有时候，有些面试题是很是无厘头，这不，又有一个，还记得小时候玩的的“火柴棍游戏”吗，就是移动一根火柴棍改变一个图或字的游戏。程序面试居然也可以这么玩，看看下面这个火柴棍式的程序面试题吧。
下面是一个C程序，其想要输出20个减号，不过，粗心的程序员把代码写错了，你需要把下面的代码修改正确，不过，你只能增加或是修改其中的一个字符，请你给出三种答案。
int n = 20;
for(int i = 0; i < n; i--){
printf("-");
}
不要以为这题不是很难，我相信你并不那么容易能找到3种方法。我觉得，如果你能在10分钟内找出这三种方法，说明你真的很聪明，而且反应很快。当然，15分钟内也不赖。不过，你要是30分钟内找不到三种方法，当然，不说明你笨了，最多就是你的反应还不够快。嘿嘿。就当是玩玩吧。
下面是我的答案：
//第一种解法：在for循环中给n加一个负号
for(int i = 0; i < -n; i--)
//第二种解法：把 n 初始化成 -20
int n = -20;
//第三种解法：把for循环中的 i 初始化成40
for( ...
打印质数的各种算法
打印质数的算法应该是学习计算机编程的一个经典的问题，在这里想给大家展示一些方法，相信这些方法会对你的编程有一定的启发作用。请你注意几点，
实际应用和教学应用有很大的差别。
最后的那个使用编译时而不是运行时的方法大家可以重点看看。
目录
教科书的示例
较好的算法
实际应用的算法
使用编译时而不是运行时
教科书的示例
首先，先给一个教科书的示例。下面这个示例应该是教科书（至少是我上大学时的教科学）中算法复杂度最好的例子了。其想法很简单，先写一个判断是否是质数的函数isPrime()，然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心，其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n))，看上去不错，但其实很不经济。
#include <iostream>
using namespace std;
bool isPrime(int nr)
{
for (int d = 2; (d * d) < (nr + 1); ++d){
...
输出从1到1000的数
有这样一个面试题——请把从1到1000的数打印出来，但你不能使用任何的循环语句或是条件语句。更不能写1000个printf或是cout。用C/C++语言。
我相信，大多数人一开始你可能想到的是递归算法：
void f(int n){
printf("%d\n",n);
(1000-n) ? f(n+1) : exit(0) ;
}
int main(){
f(1);
}
当然，题目中说了不能使用条件语句，所以，上面那种解法的不符合题意的，因为还是变向地使用了条件表达式。不过，我们可以用别的方法来让这个递归终止，比如：
除以零，当程序crash，呵呵。
void f(int n){
printf("%d\n",n);
n/(1000-n);
f(n+1);
}
还有这样退出递归的：
void yesprint(int i);
void noprint(int i);
typedef void(*fnPtr)(int);
fnPtr dispatch[] = { yesprint, noprint };
void yesprin ...
140个Google的面试题
来源：http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html（墙）
某猎头收集了140多个Google的面试题，都张到他的Blog中了，主要是下面这些职位的，因为被墙，且无任何敏感信息，所以，我原文搬过来了。
Product Marketing Manager
Product Manager
Software Engineer
Software Engineer in Test
Quantitative Compensation Analyst
Engineering Manager
AdWords Associate
这篇Blog例举了Google用来面试下面这几个职位的面试题。很多不是很容易回答，不过都比较经典与变态，是Google，Microsoft，Amazon之类的公司的风格。对于本文，我没有翻译，因为我相信，英文问题是最好的。不过对于有些问题，我做了一些注释，不一定对，但希望对你有帮助启发。对于一些问题，如果你百思不得其 ...
面试题：布尔变量
下面这篇文章是从StackOverflow来的。LZ面试的时候遇到了一道面试题：“如果有三个Bool型变量，请写出一程序得知其中有2个以上变量的值是true”，于是LZ做了下面的这样的程序：
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
} else {
return false;
}
}
面试官接着问到，请对你的这个程序改进一下，但LZ不知道怎么改进，于是上StackOverflow上问了一下，下面是StackOverflow上的众网友的回答。再往下看的时候，希望你自己能先想一想怎么改进。
有人说，如果你有下面这样的代码？
if (someExpression) {
return true;
} els ...
我是怎么招聘程序员的
很早以前就想写一篇和面试相关的文章了，今天在网络上看到一篇关于如何去面试程序员的英文文章，发现其中有很多和我共鸣的东西，所以仿照其标题通过自己的经历写下了这篇文章。
工作这么多年来，即被面试过，也面试过他人，对于程序员的面试，经历过很不错的面试，很专业的面试，也经历过一些BT和令人不爽的面试，我个人觉得一个好的面试，面试官是很重要的，所以，本文想从“面试官”的角度来阐述一下。于是，有了下面这样一篇的文章，希望本文对你的职场经历有用，特别是那些正在招聘和面试程序员的朋友，我觉得这篇文章会对大家有很多启示。此外，做为被面试的人，你可以看看本站的《别的程序员是怎么读你的简历的》《程序员需要具备的基本技能》《优秀程序员的十个习惯》其它一些和程序员相关的文章。
对于招聘方来说，在招聘程序员的时候，我估计面试应聘者时，最主要想知道的是下面三件事：
这个程序员的是否够聪明？
这个程序员能否把事情搞定？
这个程序员能和我的团队在一起工作吗？
我相信，这是所有团队经理招人要考虑的三个问题，所有的问题也基本上围绕着这三个问题。有些时候，你也许觉得程序员的技术技能可以同时解决这三个问题，一个技术 ...
面试题：赛马问题
据说，这是Google的面试题。面试题目如下：
一共有25匹马，有一个赛场，赛场有5个赛道，就是说最多同时可以有5匹马一起比赛。假设每匹马都跑的很稳定，不用任何其他工具，只通过马与马之间的比赛，试问，最少得比多少场才能知道跑得最快的5匹马？（不能使用撞大运的算法）
很明显这是一个算法题，网上有很多贴子在讨论这个问题，不过都没有给出一个明确的答案。我想了想，想到下面的一个算法：
1）分成5组A，B，C，D，E，比五场。然后根据每场结果分别给这五组内的五匹马排序（从快到慢）。
2）每组的头名再赛一场，取走第一名，然后该组第二名顶上。
3）重复第二步，直到选出前5名。
这个算法是比较笨的算法，总计需要赛10次，这个算法应该是万无一失的。现在的问题的就，如何优化这个算法，想了想，的确是有优化的空间的。也就是说，是可以少于10次的。
想了一想，上面的那个算法自从第6次开始就使用5个排序数组的头名做“冒泡法”，总是挑一个最优秀的出来，其实，在第6次以后除了挑出最优秀的，我们还可以在每次比赛后淘汰一些速度不行的，淘汰的马匹数自然会比选出的更多，所以，一方面在找，另一方面在淘汰，找出前5名 ...
