上周面试了一家公司，题目挺好玩，跟大家share一下：
1、如何检查一个链表中有没有回路：
方法一：遍历链表，并用一个数组记录每个节点的指针，如果指针出现重复那么证明有环路存在。
方法二：快慢指针。快指针每次step为2，慢指针step为1，不停的遍历链表，如果快慢指针出现碰撞，就代表有回路了。这个算法很好玩，好比两个选手赛跑，一个快一个慢，如果在直线赛道上跑，那么两个选手肯定相距越来越远，但是在环形赛道上跑，慢的选手早晚要被快的套圈，这就是碰撞。
关于效率：假设一个链表是首尾相连的，有n个节点，那么方法一将需要n+1次循环才能查出回路，而方法二只需要n次循环，而且不需要借助数组。
2、一个文件中有n条记录，如何找出重复次数最多的前m条记录：
面试官说可以用shell命令来做，但是当时我比较紧张，sort、uniq的参数在脑子里一片空白，索性直接就用一个php的方法应付了事了，现在把命令补上来：
uniq -c filename | sort | head -n m(m是前多少条记录)
中断和陷阱：
中断信号是来自CPU外部的，陷阱信号来自CPU内部。中断和陷阱都会终止当前指令的继续执行，把控制权转移给“中断处理程序”或“陷阱处理程序”。
操作系统通过中断和陷阱机制达到对资源进行管理的目的（主要应用于进程管理和设备管理）。
指令执行模式：
指令分为特权指令和非特权指令，要执行一个特权指令，CPU必须处于特权模式，特权模式由CPU内部的一个标志位表示；若没有设置这一位，试图执行特权指令就会引起一个“陷阱”，并调用操作系统的“陷阱处理程序”解决这一冲突。
操作系统的三种基本视图
抽象、虚拟和资源管理。扩展机、虚拟机和资源管理者是操作系统的三个基本角色。
操作系统的组织结构
应用程序–>系统库–>系统内核。应用程序既可以做系统调用也可以做内核调用。内核调用并不直接执行，而是调用SVC，实际的内核程序运行于特权模式。
操作系统的种类
批处理操作系统、多道程序设计系统、交互式操作系统、个人计算机和工作站操作系统、分时操作系统、实时操作系统、分布式操作系统
从科尼汗老先生的书里面抠出来的：
1. Write clearly– don’t be too clever.
2. Say what you mean, simply and directly.
3. Use library functions whenever feasible.
4. Avoid too many temporary variables.
5. Write clearly – don’t sacrifice clarity for “efficiency.”
6. Let the machine do the dirty work.
7. Replace repetitive expressions by cal ls to common functions.
8. Parenthesize to avoid ambiguity.
9. Choose variable names that won’t be confused.
10. Avoid unnecessary branches.
11. If a logical expression is hard to understand, try transforming it.
12. Choose a data representation that makes the program simple.
13. Write first in easy-to-understand pseudo language; then translate into whatever language you have to use.
14. Modularize. Use procedures and functions.
15. Avoid gotos completely if you can keep the program readable.
16. Don’t patch bad code – rewrite it.
17. Write and test a big program in smal l pieces.
18. Use recursive procedures for recursively-defined data structures.
19. Test input for plausibility and validity.
20. Make sure input doesn’t violate the limits of the program.
21. Terminate input by end-of-file marker, not by count.
22. Identify bad input; recover if possible.
23. Make input easy to prepare and output self-explanatory.
24. Use uniform input formats.
25. Make input easy to proofread.
26. Use self-identifying input. Al low defaults. Echo both on output.
27. Make sure al l variable are initialized before use.
28. Don’t stop at one bug.
29. Use debugging compilers.
30. watch out for off-by-one errors.
31. Take care to branch the right way on equality.
32. Be careful if a loop exits to the same place from the midd le and the bottom.
33. Make sure your code does “nothing” graceful ly.
34. Test programs at their boundary values.
35. Check some answers by hand.
36. 10.0 times 0.1 is hard ly ever 1.0.
37. 7/8 is zero while 7.0/8.0 is not zero.
38. Don’t compare floating point numbers solely for equality.
39. Make it right before you make it faster.
40. Make it fail-safe before you make it faster.
41. Make it clear before you make it faster.
42. Don’t sacrifice clarity for smal l gains in “efficiency.”
43. Let your compiler do the simple optimizations.
44. Don’t strain to re-use code; reorganize instead.
45. Make sure special cases are truly special.
46. Keep it simple to make it faster.
47. Don’t didd le code to make it faster — find a better algorithm.
48. Instrument your programs. Measure before making “efficiency” changes.
49. Make sure comments and code agree.
50. Don’t just echo the code with comments — make every comment count.
51. Don’t comment bad code — rewrite it.
52. Use variable names that mean something.
53. Use statement labels that mean something.
54. Format a program to help the reader understand it.
55. Document your data layouts.
56. Don’t over-comment.
嗯，活见鬼了。但是事实摆在眼前，并且不止一次。实事求是地说，谁也不可能保证项目100%没有bug，但是，在项目发布前后的这一当口发现bug绝对是不正常的，这说明之前的测试环节有严重的问题。在我为时并不算长的几年项目经验中，这种现象时常出现，并且频率有变高的趋势。为什么？这里我想总结一个典型但不完整的原因列表和大家共勉：
1、开发环境、测试环境和生产环境的不一致。
在《程序员修炼之道》中，作者特别就这一条做了详尽的讨论，字字都是血的教训，而我在比较了供职过的两个team的经验之后对此也有深刻的体会。之前供职的A公司是一家日企（我反感日企的工作氛围，但是佩服日企对工作的态度），有专门的系统团队负责建设和维护项目的测试环境和生产环境，对他们的要求是：在这两种环境中，从操作系统的内核到服务器上安装的应用软件，其版本和配置都必须保持严格的一致，并且有详尽的文档记录服务器上软件版本的每一次更新。所以开发人员和测试人员都对通过测试的项目很放心，因为不管在哪种环境下，程序的行为表现都是高度一致的。至于开发环境，程序员完全主动的向测试环境靠拢并保持一致，因为大家都明白环境差异的最小化会使项目质量变高，继而他们自己的日子也好过得多。而现在供职的项目在这一点上做得较差，生产环境用的是CentOS4，测试环境用的是一个老版本的Fedora，PHP和Mysql的版本也不一样，我清楚的记得有一次项目发布到生产服务器上后马上就地瘫痪，在线苦苦调试了一个多小时没能找到原因，无奈被迫下线，事后又经过两个小时的排查，发现是因为PHP版本差异造成Json函数的行为不同。事后我在邮件中总结了问题原因并提请系统管理员注意，管理员先生很诚恳的跟我解释说他早就意识到了这个风险并且也有同步两个环境的打算，但是经过和高层的沟通后他们决定半年后再动手（还记得那个关于把箱子从IBM一楼搬到六楼的故事么，那是真事儿），现在，一年半过去了，毛都没同步过…… 而就在几个小时前，最新的一次release再次因为配置差异造成了30分钟停顿。
2、开发环境、测试环境的代码被污染。
之前（大概也就两个月之前吧），项目的所有成员还都是在主干上进行开发的，想象一下，5个程序员同时在主干上开发10个功能，代码互相缠绕在一起，在开发过程中就开始互相污染了，其中更不乏有的developer有意无意的将未测试的代码提交进cvs，继而影响其他人的开发工作。而如果其中一个功能因为某种原因被从release列表中拿掉的话，剩余的九个功能也因为频繁的交错commit而与之错骨连筋、无法划清界限。后来经过讨论，我们使用了每个task一个分支的做法。这种方法保证了程序员各自工作在干净的working copy上，提交的代码也不会受其他程序员的影响——至少在代码合并、集成测试之前不受别人的影响，而且发布时的可选择性也变大了，没通过测试或者有问题的task可以不合并到主干上，主干上保存的永远是稳定的、生产用的代码。
测试环境的代码污染问题稍微复杂一点。当使用cvs update -j对代码进行合并的时候，出现冲突是很常见的一件事。这个时候程序员会手工解决冲突，这里就隐藏着潜在的污染威胁——如果不了解其他人的代码逻辑，合并就可能出错，更要命的是，有些程序员直接就会在集成测试环境上进行调试！各种echo、printr、var_dump、die，最后调试虽然可能成功了，但是代码已经面目全非！根本没法指望他们能把集成测试的代码恢复原样，因为根本记不清debug过多少个地方，也不知道当前测试的代码是从哪些个branch上merge进来的。退一步讲，就算他们什么都知道，人多手杂，你敢保证一点错误都没有么？很少有程序员真正了解别人的代码逻辑，也没道理要求他们去这样做。所以合并代码不应该是程序员做的事儿，集成测试环境更不应该让程序员染指。要像保护生产环境一样保护测试环境！那么如果有的程序员就是怀疑集成测试的代码出现了“灵异现象”，需要调试以检查错误怎么办？很简单，把集成测试的代码copy给他们一份，或者干脆为每个程序员在测试服务器上建立一个集成调试环境，让他们在里面爱怎么折腾怎么折腾吧，绝对不会影响其他人，更不会干扰正常测试。
同样的问题也会出现在测试用的数据上。如果测试所用的数据库是被各个instance共享的，同样会造成“灵异事件”，有的程序员会抱怨说“数据不知被谁改了，乱七八糟的根本没法调试！”那么好，给每个人制作一个干净的数据拷贝，让他们自己维护，防止别人染指。
3、不完善的分工和不严格的实践。
还是那句话，测试能保证100%的覆盖率么？或许unit test可以，但是即使单元测试全部通过，没不能说明程序是完全按照客户的需求在工作。很可能代码逻辑没问题，但是客户要的是A，程序却在干着B，也就是说业务逻辑上有问题。这就需要test case的制作要既详细又严格，当然，对需求的正确理解也是一个前提。你没办法完全保证程序员完全理解了需求，但是你可以保证test case跟solution文档的一致！不然要solution干嘛？好，现在权责分明了：
1、正确的理解需求是BA或者PM的责任
2、正确的提供solution是Tech leader或者架构师的责任
3、正确的实现solution是Developer的责任
4、正确的编写和测试test case的是测试人员的责任
如果每个角色都能严格的履行职责，那么项目的可靠性就会很高，不要以人手不够或时间有限做借口来干扰分工，一个人身兼数职也不是问题，问题是，每一项工作都要认真的分配、可靠的完成，如果dead line确实很紧，那么，宁可牺牲功能，也不要牺牲质量。“不要允许破窗户的出现”，这一原则不仅适用于程序代码，也适用于项目管理，“破窗户”是会传染的，一个步骤的疏忽或者不负责任，带来的可能是整个team的心烦意乱、步调不统一，对项目的影响也可能像蝴蝶效应一样难以估量。
对工作的严格不等于对人的严厉。我就不喜欢别人对我很严厉，在A公司供职的时候那个PM就很严厉，尽管我非常敬佩他对工作的严格要求，但仍不免反感。不要用教官对待新兵蛋子的态度对待同事或者下属。把解决问题的方法上升到制度层面，而不要降低到员工的自身修养或者素质层面，这是区分好Manager和差Manager的一个标准，（插播一下，我觉得我党之所以把国家治理成这个鸟样，就是因为法制不足，人治有余）你怎么知道下一个招进来是什么样的员工？你打算把每个员工都修理成你觉得满意的样子？对team成员的个性和习惯宽容，对制度的执行认真并严格。当然，我也不想因为对制度的严格遵守而被别人误解为对人的严厉。没人喜欢矛盾，但是矛盾不会因为大家讨厌就不出现，任何时候，开放的讨论是最好的解决方式，抱怨和责备解决不了问题。但是如果你不小心触犯了“天条”，给别人造成了麻烦，眼睁睁看着人家给你擦屁股的时候，适当的表现一下愧疚吧，毕竟大家都是成年人，是吧……
父表是指“被引用的表”
子表指的是“引用其他表的表”
$_dependentTables只能定义在父表中，用于对数据完整性的检查，定义诸如”on_update”或者”on_delete”之类的操作，原因是通常父表中的记录被删除或更新后，会给子表的关联记录造成断链。如果你用的是InnoDB之类的存储引擎，并且表中已经定义了”on_update”或者”on_delete”之类的操作，那么就不要再在程序里定义$_dependentTables了那么就无需再在$_dependentTables中定义关联操作了。数据库本身的完整性检查要优于程序中的完整性检查。如果你用的是MyISAM之类的存储引擎，那么使用$_dependentTables的关联操作定义才会对你有帮助。
$_referenceMap要定义在子表中。它描述了该表的哪个字段“引用了”父表中的哪个字段，并且给这种关联关系起了个名字：
class BugsProducts extends Zend_Db_Table_Abstract
{
protected $_name = ‘bugs_products’;protected $_referenceMap = array(
‘Bug’ => array(
‘columns’ => array(’bug_id’),
‘refTableClass’ => ‘Bugs’,
‘refColumns’ => array(’bug_id’)
),
‘Product’ => array(
‘columns’ => array(’product_id’),
‘refTableClass’ => ‘Products’,
‘refColumns’ => array(’product_id’)
)
);
}
用这个工具就可以：
http://www.softplatz.com/Soft/Network-Internet/Remote-Computing/Remote-Clipboard.html
不过这个工具只能对clipboard里面的东西进行保存，呵呵，高科技生产傻子，只要做的足够handy，针对文件的remote copy工具也是会有市场的。
——-补记——–
刚才看到了一句有意思的格言：
Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning.
- Rich Cook
——再补——–
另外几条搞笑的格言：
我曾经在Arnold同学（这家伙号称一个周末搞定了Perl，并写出了我们项目的requirement management工具）面前说Perl很ugly，后来觉得自己有点莽撞，现在看来比我莽撞的大有人在…
PHP被一些不合格的业余人员造就成了一个小恶魔；而Perl则是被一些熟练但不正经的专业人员造就成了一个超级大恶魔。PHP is a minor evil perpetrated and created by incompetent amateurs, whereas Perl is a great and insidious evil, perpetrated by skilled but perverted professionals.
- Jon Ribbens
Perl是唯一一种在经过RSA加密后看起来却和加密前没什么两样的语言。Perl – The only language that looks the same before and after RSA encryption.
- Keith Bostic
又见Java。
说“Java好是因为它跨平台”就好像说“肛交好是因为其可以适用于一切性别”。Saying that Java is good because it works on all platforms is like saying anal sex is good because it works on all genders
- Unknown
每次碰到XML我都会二话不说扭头就跑，而且我总能找到其他办法代替XML解决问题，很佩服这句格言的作者，妈的我怎么就想不出这么简洁有力的句子。
XML和暴力其实是一样的——如果它不能解决你的问题，那只能说明你用的还不够。XML is like violence – if it doesn’t solve your problems, you are not using enough of it.
- Unknown
最后一条看着最爽，一起来诅咒我们的stakeholders吧 
Einstein argued that there must be simplified explanations of nature, because God is not capricious or arbitrary. No such faith comforts the software engineer.
