Facebook唯一华人总监魏小亮教你如何选择硅谷的IT公司

这里是作者的博客


如何选择硅谷的IT公司？Facebook 移动技术总监、Facebook“新兵营”的领队之一、
负责新员工培训的魏小亮（作者简介请见文章末尾）从四个方面写了四篇博文，给出了
他的详细建议。在获得作者许可后，伯乐在线把四篇博文合成一篇发布，以下是全文。


经过激烈的面试，恭喜你拿到一个硅谷IT公司的Offer了，更可喜的是，有几个公司同
时给你Offer。下一个头疼的事情：如何选择一个最适合自己的公司。

这两年跟不少拿到多个硅谷公司Offer的国内朋友打过电话聊天，觉得不少朋友的决定
因素比较随机——往往几个公司都没有具体了解，觉得差不多也都挺好的，大多数朋友
去工资最高的地方；也有一些去了HR比较主动的公司。最后到了那个公司发现并不是最
适合自己的…… 所以，我想在这里谈谈怎样选择公司。

最关键的一点： 获得每个公司尽量多的信息，根据各个公司的情况和自己的目标，做
理性的决策。HR给你Offer或者还价的时候，千万不要立即接受或者拒绝，可以礼貌地
说 “非常感谢。我非常珍惜这个机会。请让我认真思考一下，再给您答复。” 然后马
上开始你的决策过程：
（一）：如何收集公司的信息
（二）：决策过程的考虑因素
（三）：薪酬和待遇
（四）：关于HR

一、如何收集公司的信息
这里介绍一下收集信息的渠道。一个关键点是在收集信息的时候要尽量做到理性而没有
偏见：如果你带有很重的偏见去收集，这个过程本身就变成了收集证据去证明自己的观
点，而不是收集所有的信息去帮助自己决策了。

我想大家可以考虑以下几个信息源：
1、公司的产品和网页 ：如果对方是一个产品型的公司（最终客户是普罗大众而不是
Fortune 500公司），一定去看看他们的产品和网页，看看自己对这些东西是不是感兴
趣。每天做自己感兴趣的产品，幸福感会很高，工作的压力会变成动力，绩效奖金也高
，升职也快 —— 硅谷的游戏类公司基本工资往往比其他IT公司相对低一些，原因是有
不少工程师喜欢玩游戏，他们愿意少拿一点薪水去做自己喜欢的游戏产品。其实长远来
看，自己开开心心的工作生活的确很重要，“有钱难买爷高兴”嘛。

2、公司的开源项目和技术会议讨论：不少的科技公司是有自己的开源项目代码库的，
也有不少公司参加一些技术会议。可以看看他们的项目和会议的录像或者幻灯片。从中
可以了解到这个公司的技术水平大概是怎样的，自己能从未来的同事学到什么东西。这
里要注意的是最好找工程师的幻灯片（而不是销售或者HR的幻灯片，那些信息量低而且
更多是广告成分）。

3、找公司里跟自己背景相似的员工：如果有朋友在那个公司工作，一定要找他问问情
况。如果没有，可以跟HR回信说 “在我决定之前，我能不能跟公司里的一个中国工程
师聊一下？我想了解他们来美国的过程和工作生活的情况。” 一般HR是很乐意为你找
这样的工程师的。跟背景相似的员工聊天会让你看到更真实的一面——因为在加入公司
之前，HR往往是主要的沟通渠道；但一个公司的工程师队伍的文化有可能跟HR的文化类
似，更可能截然不同（我自己面试过的几家IT公司，工程师文化最差的公司HR最好，工
程师文化最好的公司HR最差）。加入公司之后，你主要跟工程师合作，所以关键是要看
自己跟工程师是不是合得来。

4、如果有两个公司选择，最好能找到一个在这两个公司都工作过的未来同事，让他们
谈谈两个公司的区别和感想；一般这样的同事能给你一些比较。但要注意的是这样的同
事往往偏向现在的公司（否则HR也不太可能让他跟你谈:），所以有机会的话最好两家
公司都找一个类似情况的同事。

5、找你的未来经理或者部门主管：有些公司是预先已经给你安排了团队和经理的，如
果是在考虑这些公司，最好能跟未来的经理聊一下，看看是不是合得来。HR一般也会支
持这样的安排。

6、找一个你希望成为的人或者你信任的人给建议：如果你身边有一个你希望成为的人
（比如比较成功的师兄师姐，或者公司里面你特别尊重和信任的同事，或者你认为有远
见的长辈），可以请他跟你聊一下，把你收集到信息和你自己的情况和目标做一个分析
，让他给一些建议。”三人行必有我师”，有一个参谋往往能让自己避免低级错误。

（3、4、5 一般需要HR引荐，可能只能选其中的一到两个。我建议至少找一个中国工程
师聊一聊。）
最后我想要强调的是：这个信息收集过程也是你建立新的社交圈的过程。在其中交到的
朋友，无论你如何决定， 都要给他们说一声，感谢他们在这个过程给你的帮助；到了
硅谷安顿下来了可以找他们吃个饭，保持联系……硅谷本身就是一个很小的圈子（或者
说整个硅谷是一个很大的公司），在这个过程里面建立的联系，好好珍惜，以后再换工
作或者有其他机会，你还能继续得到帮助。对于你决定去的公司，帮过忙的同事更要主
动感谢，参加工作之后主动联系，他们往往会是你在新的公司里面的第一批良师益友。

二、决策过程的考虑因素
薪酬待遇是大部分朋友最关心的一点，我在下一篇将详细讲。在考虑薪酬的同时，我认
为最好能全面考虑各方面的因素：
1、个人的目标
你5年以后想做什么？想开一个自己的公司？还是想加入一个创业公司？还是想在某一
个领域做世界一流的技术专家？还是想在一个大公司里面做管理？还是想做一个普通的
工程师，有比较多的个人时间？

如果5年太远还没想，那在下面一两年你想学到什么东西？学到比较全面的Web2.0的技
术运作（但不一定精通）， 还是想在一个方向学得很精通，还是想学产品的开发管理？

回答这个问题很重要，因为无论薪水多少加薪多快，我们都会觉得太少；最终的成就感
和幸福感往往来自于自己个人的成长和个人目标的实现。

不同的公司有不同的长处，最好能找到一个公司能给自己的成长提供相应的机会，有可
能达到自己的个人目标。

2、公司的规模、目标和文化
一般来说，公司越小，资源越有限，学到的东西越广泛，但不容易精，容易培养通才；
公司规模大，任何一个子领域的一点点改进就可以带来比较大的回报，更愿意投入资源
让人钻研一个子领域， 容易培养专才。

快速增长的公司会有更多的学习和晋升机会，但淘汰率可能也高；已经成型的大公司不
容易因为业绩问题淘汰，但更有可能整个部门解散。

在专注产品的公司工作，更容易学到产品开发概念，更重视能把握整个开发流程的人才
，只希望在一个领域钻研的人才则不一定很开心；专注技术的公司则相反。

工程师文化很强的公司把工程师看成创造机会的原动力，聚集了很多顶尖人才，工资高
，同时对个人创造力和主动性要求也高；销售文化很强的公司则往往把工程师看作成本
，工资能压则压，但工程师往往只需要跟进销售团队的反馈意见，不要求很强的主动性。

3、等级、业绩评估和晋升过程
如果公司有分工程师等级，可以问Recruiter你的等级是多少，整个公司的工程师等级
是怎样定义和划分的？不同公司的等级在数字上不一样，如果你有多个offers，可以问
HR不同公司的等级是怎样换算的。

如果你有朋友在对应的公司，或者Recruiter为你找到公司的工程师或者经理来讨论，
可以问一下他们公司的文化，工程团队如何做业绩评估，晋升的过程是怎么样的，谁（
peer还是manager）决定业绩和晋升？ 他们对公平性的看法如何。

4、职业道路
跟工程师或者经理讨论的时候可以问一下公司为员工提供的职业路线：如果做得好，
两年之后或者五年之后在公司里面会有什么样的职业道路可选择？ 公司会为你的职业
规划提供什么样的培训和支持？是否支持员工到大学里面在职学习？ 是否可以在公司
内改变职业路线？跨部门调动是否有很高的门槛？

5、 文化环境
如果能跟一个中国工程师或者经理讨论，可以讨论一下中国文化背景的员工在公司的状
态如何（比如在工程师里的比例是多少，在经理的比例又是多少）；普遍遇到的问题和
瓶颈是什么？公司有没有一个氛围能帮助刚从中国来到的新员工适应语言、工作、生活
和文化的改变？

如果希望以后在美国长久生活，可以问公司对绿卡的申请是不是很支持？一般要多长时
间才能开始（有些公司需要工作一两年才开始申请绿卡，有些工作开始之后几周就可以
申请）；一般从开始申请到140的批准需要多长时间——有些大公司可能经常有部门解
散的情况（美国移民法律是一旦有部门解散，绿卡申请就会暂停，整个过程会拖得很长
）。

不同的公司对这些问题的回答都不一样。很难绝对地说哪个公司更好，关键是哪个公司
更适合你的目标。

三、薪酬和待遇
美国公司的薪酬和福利五花八门，每个公司都别出心裁地想一些与众不同的福利。 HR
会强调自己公司的特别福利，让你觉得比其他公司好，轻易接受了。我的建议是在跟HR
谈offer的时候着重收集信息，不要当场做决定。回家把所有的薪酬和福利都列出来，
然后综合其他更重要的因素（见上一篇），跟自己信任的人讨论一下，最后做一个理性
的决定，再回复HR。

下面把一些常见的薪酬和福利介绍一下：
1、基本工资。基本工资是给雇员的稳定可预测收入。

工程师的基本工资一般按每年收入多少来算。如果公司到了一定规模（一般一百人以上
），内部都有工程师等级——能力越强（或者有的公司是资历越深）的工程师等级越高
。基本工资往往与工程师等级挂钩。

大部分的新型公司工资只与等级挂钩，同一个级别的工资相差不会太大（比如+/- 15%
的浮动）。在这样的公司里面，如果你觉得你是一个非常上进的人，起薪多一点少一点
并不是很重要——因为如果很快能被升级，那你的工资就会跟新的一级挂钩，跟起薪没
有关系；另一方面，有些公司为了提高竞争力，可能开出一个比较高的起薪（高于相应
级别的最高工资），但当你升了一级的时候，你的工资还是会按照公司平均水平跟新的
一级挂钩， 升级所得到的实际加薪很少。总之，起薪的差异只影响第一次升级之前的
收入。

另外一些公司（我听到的都是非硅谷的传统大公司） ，工资是按照每年比去年涨一定
的百分比来算的，这样的公司起薪很重要——因为起薪低了每年按去年的百分比涨，都
要吃亏。

最好能跟HR讨论一下公司对薪酬的政策是哪一种。

2、奖金。奖金是短期激励手段——一般每年或者每半年做一次业绩评估，决定奖金数
目，业绩越好的雇员奖金越多。

具体的奖金计算方式可以跟HR讨论一下奖金的计算方式。一种比较常见的方式是由三个
系数决定：
A、基本目标系数  (Target Bonus Rate)：往往根据工程师级别来定。级别越高，这个
系数可能越高，与当年业绩无关；
B、公司业绩系数 (Company multiplier)：每半年或者每年由公司领导层或者董事会决
定整个公司的业绩，如果业绩正常，就是100%；如果业绩高于预期，系数就高于100%；
反之亦然；
C、个人业绩系数（Individual multiplier）：每半年或者每年由经理、或者同事互评
和自评对自己的业绩进行评估，如果你的业绩跟你的级别预期一致，就是100%，高了或
者低了系数对应变化。

最后的奖金由三个系数和基本工资相乘，比如如果基本目标系数是10%，公司业绩和个
人业绩系数均为100%，那奖金就是基本工资的10%。从这里可以看出，在考虑Offer的时
候，奖金的基本目标系数影响最大。一个10%的目标系数和一个5%的目标系数意味着实
际上很可能有5%的基本工资差异。

3、 期权或者股票。期权或者股票是长期激励手段——一般是四到五年的授予时间 (
Vest Period)，每年有20~25%的股票或者期权能到员工手上。有几个常见参数：
A、 Initial Vesting Period：拿到第一笔期权或者股票的时间，一般是加入公司之后
一年，也有加入公司之后半年的（不过很少）；
B、Vesting Period：拿到所有期权、股票的总时间，一般是四年或者五年，每年平均
拿到1/4或者1/5；
C、Vesting Cliff：第一笔期权拿到之后，以后平均多长时间得到一笔，往往是三个月
，也有半年或者一个月的。

假设你拿到128股股票，Initial Vesting Period是1年，Vesting Period是四年，而
Vesting Cliff是3个月，那你实际拿到的股票是：加入公司一年后一次拿到32股；之后
每三个月会拿到8股，直到第四年底为止。

对于还没上市的公司，建议不要对股票、期权有多大期望（无论HR如何跟你说“这个公
司马上就要准备上市了”）。把它们当成一个彩票就好——这并不意味着你绝对不能去
这个公司，只是说你去这个公司的目的不是为了股票上可能挣到的钱，可能是学习过程
，可能是工作兴趣……

对于上市了的公司，或者你对这个公司极其有信心，可以算一下你预期的股票或者期权
价值，然后除以Vesting Period（比如说四年），算出每年的预期收益——因为不同公
司的Vesting Period可能不一样，所以每年的预期收益才是真正可比的。

4、股票或者期权增发。不少公司（尤其已经成立了几年的公司），会有股票或者期权
的增发措施，让员工每年都能拿到更多的股票，不至于员工在四年之后原始股票全部到
手，发现之后的每年收入骤降而直接离开。

股票或者期权增发的过程往往跟业绩挂钩（公司当然希望越好的员工留下来的机会越大
）。但不同的公司股票或者期权增发的力度很不一样。有的公司非常慷慨，有的公司就
只是形式上的给一些。可以跟HR讨论一下公司对股票增发的政策：比如说“每年给老员
工增发的股票和给新员工的原始股票大概比例是多少？ ”

有的上市公司还提供员工股票购买计划（ESPP）。让员工有机会在一定时间以一定优惠
价格（比如九折）购买一定限额的公司股票，然后在一定时间之后（比如三个月）卖出
。如果公司股票在这三个月不掉10%，那你就能够获得一些收入。

这些股票或者期权政策五花八门，在考虑的时候也最好转换成每年的期望收益，以方便
比较。

5、入职奖金（Sign-On Bonus）。入职奖金是对新员工加入公司的一次性激励。
如果你在公司工作不到一年就离开，往往需要把入职奖金退还。一般可以大概估算一下
你打算在这个公司呆的时间（比如4年），然后把入职奖金平均分配到每年去，算出 平
均每年的收入。

==== 我觉得1～5是可以在Offer上跟HR讨价还价的重点；以下的一些基本不会太影响具
体的收入，公司往往是为了给员工提供方便而设立  ====

6、搬迁帮助（Moving Bonus）。很多公司提供搬迁的帮助，但形式很不一样：有的公
司直接给一定金额的Bonus，这种Bonus跟Sign on Bonus性质一样；有的公司则提供报
销上限，实报实销；还有的公司给你提供搬家公司服务。

同时，还有不少公司愿意为新员工提供短期（几个星期）的临时住宿。

这些问题都可以跟HR讨论，找到让你比较方便的形式。

7、法定假日和带薪假期
几乎所有公司都有法定假日和带薪假期。但每个公司的法定假日列表不一样，有些每年
只有四五天的法定假日（新年、国庆、感恩、圣诞），有的可能会有十天甚至以上。

带薪假期是员工自行决定的休假日，每个公司也有很大差异。我见过的最少是5天，最
多有21天，甚至不设上限——对于不设上限的公司，要搞清楚实际的情况，有的公司号
称不设上限，但实际上没有人敢休假。

一年大概有260天工作日（365 / 7 * 5），如果一个公司的假日和带薪假期是31天而另
一个公司是18天，里面也有5%的实际工资差别。

8、退休金计划（401K）。很多公司提供401K退休金计划；有些公司提供match——你给
自己存一定的退休金，公司会给你相应比例的存更多。这样的match往往有个上限；有
的甚至有Vest Period（比如你在公司工作了两年，才能拿到match的部分）。

如果HR向你推销一个公司有401K计划的match的话，要搞清楚他们的上限是多少；算出
每年的实际收益。另外要考虑的是放到401K的钱是要到六七十多岁退休的时候才能拿出
来的，所以实际效用不如同样数目的Bonus或者工资。

9、医疗保险。绝大部分公司为员工个人提供医疗保险；而如果员工的家人也需要医疗
保险的话，大部分公司需要员工分担一部分的费用。如果你需要为家人买保险的话，可
以把每个月的额外保险费转换成每年的费用。

10、早中午饭。很多公司也提供早中晚饭。这对单身的员工来说就省了5天的伙食费，
一年大概是5000左右吧。

11、学费补贴。有些公司为上夜校的员工提供学费补贴，往往每年几千美金。但要注意
可能会有不少约束条件，比如业绩要达到一定的要求，或者多少年才能去一次，或者上
学之后多少年需要留在公司，否则要求退还学费，等等。

12、其他。公司还可能有不少其他的补贴、福利。比起基本工资、奖金、股票来说，其
他大部分的福利都是很少的比例，更多的是公司为了方便员工，而不是作为吸引员工的
条件——但有时候HR会把它们作为公司竞争力来强调。如果有某些福利听起来真的很诱
人，最好搞清楚具体的约束条件，换算成每年的收入，再做比较。

四、关于HR
最后这一篇博文解释一下我对HR的一些理解。希望大家跟HR交流的时候更自信更有效。

大部分的朋友把跟他们在面试中联系的非工程师统称HR (Human Resource)，实际上在
整个招聘的流程中，HR的职能有几种不同的专业分工（有些小公司比较简洁，也很可能
由同一个人做这些分工的几项甚至全部）：

1、Sourcer：Sourcer的工作是为找到合适的面试候选人。Sourcer每天看很多的简历、
去各大论坛发帖子、去LinkedIn等网站搜索候选人……一旦找到ta觉得合适的人选，就
会通过Email或者电话联系。一般情况下Sourcer是第一个跟候选人联系的HR，她会问一
些基本的问题看看候选人是不是有可能通过面试，然后推荐给Recruiter。

2、Recruiter：一个应聘者进入了面试流程，就会有一个Recruiter跟ta联系。
Recruiter负责这位应聘者的面试、Offer、讨价还价、签约，直到应聘者加入公司。对
应聘者来说，Recruiter 是与其接触最多的人。（当然，最终Offer的等级、是否招聘
的决定还是由技术团队和管理团队做出的）。

3、Coordinator：Coordinator主要是帮助应聘者安排面试过程，比如说安排机票、酒
店、面试当天的接待等等。

4、Compensation Team：这个团队应聘者基本上不会接触到， 它的主要任务是考察业
界其他公司的待遇，总结待遇变化的趋势和本公司的薪酬竞争力，决定本公司每一个级
别员工的待遇标准：同一个级别的员工薪酬有一定的范围，除非极其个别情况，薪酬不
会超出这个范围。

从应聘者的角度上看，整个流程是：Sourcer跟你联系，coordinator为你安排面试，
Recruiter跟你联系，讨论你的具体情况（目前的薪酬、期望值等等），coordinator为
你安排下一步面试……工程师把面试结果提交，Recruiter把面试结果汇总，管理团队
讨论并且确定应聘者的是否合适，对应的级别是多少，Recruiter根据结果和
Compensation Team的薪酬范围跟应聘者讨论具体的薪酬；如果有非常特殊的情况，需
要跟技术总监或者副总裁进一步讨论（比如特殊人才的薪酬，或者由总监或者副总裁直
接联系应聘者）。最后Recruiter跟你一起在Offer上签字。

绝大部分的Recruiter都是谈判高手——他们每周要跟好几个应聘者讨价还价， 一个应
聘的工程师就算每年换工作，也很难有Recruiter的谈判经验丰富。另一方面，硅谷科
技公司里面Recruiter的工作流动性比较大，不少公司Recruiter是第一年合同，只有业
绩很好的第二年才会变成正式员工，所以Recruiter会想尽各种办法让拿到Offer的应聘
者加入。

大方向上，这样的Recruiter激励机制是好的，鼓励了Recruiter努力工作；但在具体操
作上，有些Recruiter会为了自己的短期目标而做出一些对应聘者不负责任的行为，比
如在电话里面给出一些有意无意的误导信息甚至恐吓。我听说的一个典型例子是某跨国
大公司在国内的Recruiter跟一个应聘者说 “你口头已经跟我说过你想来我们公司了，
如果你再去跟别的公司面试，你到了美国之后的信用记录就会很差！” 真是哭笑不得
——美国的信用记录只跟你的借贷还贷历史有关，而且在硅谷的科技公司全部是At-
will employment，法律上公司和员工互相可以随时终止雇佣关系，不要说口头答应了
，就算签字了你也可以自由地去别的公司面试或者换公司。但这样的误导信息对一个从
来没在美国工作过的朋友来说，还是很有影响的。另一方面，被误导而进入公司的员工
也很可能不会很开心，这样的事情也不符合公司的长远利益。

我写这一系列博文的起初动机就是希望能把整个招聘的过程解释清楚，让更多的朋友不
会吃亏。我想强调的是“不吃亏”就好 —— 大体来说，正如我在第一篇（如何收集公
司信息）和第二篇（决策过程的考虑因素）强调的，薪酬并不是最重要的，在哪个公司
工作更开心、更能学到自己想学的东西，才是最重要的。如果有朋友希望进一步把跟
Recruiter斗智斗勇作为一个爱好的话，有两本书建议看一下：“影响力”[1] 主要讲
的是黑武术——别人怎样利用人性的弱点去说服你；“寸土必争”[2] 主要讲的是白武
术——如何跟对方进行公平的讨价还价。

下面讨论一下几个关于Offer的常见问题：
1、Offer的时效限制：
一般公司在给出Offer的时候，都会给一个时效（比如说希望应聘者一个月之内答复，
否则Offer就不再有效）。这个时效限制可以保证公司避免一些风险，比如说：公司很
小的时候，只招一两个人，所以不能让多个Offer长期有效，否则几个人同时答应了，
公司就需要取消一些Offer，对应聘者影响很大；另外Offer里面薪酬的具体数字是跟据
市场变化而变化的，如果就业市场在几个月之后变差，新招员工的薪酬会降低，Offer
时效性太长会引起不公平（同一时间决定加入的员工，因为Offer发出的时间不一样而
差异很大）；类似的因素也包括公司股价、期权价值的浮动。

另一个方面，一个公司给出一个Offer是需要很大代价的：以上所说的所有HR的时间、
工程师面试的时间、管理团队做决定的时间……可以说，对每个发出的Offer，无论接
受与否，如果考虑其背后需要筛选和面试其他不合适的应聘者的时间，公司可能已经耗
费了很大的成本。所以，如果一个应聘的工程师拿到了Offer，就算ta一时不能决定或
者不能接受，大部分公司还是很愿意保持Offer的——如果时间超过了几个月，Offer的
具体薪酬很可能有改变，Offer的决定和工作级别往往还是有效的（除非这个公司的经
济情况或者整个大环境变得特别差，公司突然决定不再扩张了）。

所以，Offer的决定（是否招收这位应聘者和招聘级别）往往是可以在比较长的时间内
有效的，而Offer的具体数字（工资、奖金、股权等等）是很可能变动很快的。我们最
好把这两个部分分开。

理解这一点很重要：我跟一些准备来硅谷工作的朋友交流的过程中，感觉他们觉得找工
作是一次性的买卖，成了就好，不成就再也不用打交道。有些Recruiter有时候也会给
出这样的误导：“如果你现在不来，以后就很难来了” [3] 或者“我这么辛苦找到VP
才给你争取了这个Offer，你不来的话就是不珍惜我的劳动，以后就别跟我们的团队合
作了……”[4] 其实这些说法都是说服你的手段。如果你现在不接受，而几周之后，或
者半年甚至一年之后再跟他们说想要去，绝大部分情况下，公司还是会非常积极的给你
安排新的Offer的，只是具体的数字可能不一样而已。

理解这一点的另一个意义是：尽量跟所有跟你交流过 Recruiter保持良好关系，就算你
不去他们的公司，也给每个人感谢；就算Recruiter在具体数字的讨价还价过程中跟你
说了一些不好听的话，别放在心上，有机会继续保持联系。这样的心态有助于你长期的
职业成长，因为Recruiter本身流动性也很大，他们到了另一个公司，如果还能想起你
是一个很优秀的应聘者，会给你带来新的机会。

2、Offer的讨价还价
我认为最好把所有可能拿到的Offer的公司都面试好了，知道自己究竟能去哪些公司，
每个公司提出的薪酬待遇是多少都搞清楚了，然后再跟Recruiter做协商。

如果你拿到了一个Offer，还有其他公司没有答复，可以跟其他公司说你有一个Pending
Offer，让他们加快速度；而跟给你Offer的公司说你需要一些时间决定，同时考虑到
对方的担心 ，你可以提出过几周再看Offer的具体数字（这样别人不会觉得你是希望拿
着他们的Offer来回讨价还价）。 在这个过程中，Recruiter很可能会催你决定，但正
如上一段说的，除非经济情况突然变化，绝大部分情况下Offer在几周之内是有效性的。

拿到所有能拿的Offer后，可以跟每个公司说你的所有可能选择，跟他们确认Offer里薪
酬待遇的具体数字，然后把不同的待遇转换成可比的每年收入（见上一部分“薪酬和待
遇”的分析）。这样你就大概知道你在当前就业市场的位置，有了基本的数据跟
Recruiter讨论薪酬待遇了。

在讨价还价之前，我个人的建议是想清楚自己对每个公司（而不是每个Offer的数字）
的态度和自己的自身情况：这是不是所有我能选择的公司里面我最希望去的公司（根据
第二篇讨论讨论的内容，个人目标和公司文化等等）？如果不是，就不必去讨价还价了
：一方面浪费了你的时间，另一方面容易引起误会。比如说你说了一个想要的待遇，对
方答应了，你不去，就不太好跟这个Recruiter拒绝了——拒绝别人总是需要有一些理
由的。

如果这个公司是你非常想去的，那就跟对应的Recruiter讨论Offer的细节。这里面很重
要的一点是讨价还价的目的是什么？为什么这个公司应该多给你工资和股票？我觉得可
以强调两点：1、你很喜欢这个公司，希望加入；2、其他公司的待遇更好，你希望的到
一个公平市场的待遇，让你可以很高兴的工作。

你希望加入这个公司这一点很重要：这表现了你的讨价还价是真诚的，同时把你和
Recruiter放在了同一战线上[5]：Recruiter也很希望你能在这个公司工作，讨价还价
的工程是你们俩共同努力来实现共同的目标。

公平性是大家都愿意接受的一个讨论基础。[6] 从公司角度来说，如果你的待遇低于市
场待遇，那你会觉得没有被公平对待，可能很快离开公司，对公司也不是一个好事情。
从个人角度来说，希望“不吃亏”就好，不要想着从中得到比别的类似的工程师更好的
待遇：待遇总是跟期望值挂钩的，如果你真的要到了更好的待遇，公司对你的期望值也
会更大。

如果这个公司的待遇正好也是最好的，那就很难讨价还价了——但你也没有吃亏；如果
这个公司的待遇比其他公司要差，你可以把其他Offer里面最好的拿出来跟Recruiter一
起讨论你的分析，强调你希望到这个公司和你希望公平这两点。如果你的分析有道理，
也就等于给Recruiter提供了跟管理团队协商依据。Recruiter会比较容易给你争取更好
的待遇。

最后讨价还价的结果可能是令人满意的（比如说公司的确把待遇水平涨到了你希望的水
平），也可能不完全满意：比如说公司的管理团队认为你的分析不完全合理，比如说对
股票未来价格的预测跟管理团队的预测不一样；或者另一个公司给出的待遇是非理性的
…… 一个前Yahoo的Recruiter曾经在Caltech的就业中心做过讨论，她的建议一般不要
超过两个回合的讨价还价——如果一开始的Offer是x，你回复说希望要a，对方说不行
，最高是y，你回复说要b，对方再给你z。到了这步基本上就很难再有大的变化了。这
是一个特定的Recruiter说的经验，可能不是放之四海皆准的道理，但我觉得也有一定
道理：第一回合是Recruiter自己的上限，第二回合是Recruiter跟管理团队讨论之后的
上限。在这个时候，如果对方给你的待遇还不能满足你的期望，我会建议静下心来想想
这个Offer是不是合适：长远来看，找一个自己喜欢的工作更重要；但你如果有一些短
期的期望（比如说需要一笔钱还房贷），那可能就要为了短期的目标而去一家自己不喜
欢（但薪酬更高）的公司了。如果短期没有迫切的期望，而两个公司Offer的差距也不
是很远，我还是建议去自己喜欢的地方。无论哪种决定，关键是要在讨价还价之后冷静
下来综合考虑，讨价还价的过程本身很容易让人专注于薪酬数字而忽视了其他的考虑因
素。

3、Offer的接受和谢绝
一旦决定，一般建议先接受一个公司的Offer，等到对方确认了，再谢绝其他的Offer。
这样的操作顺序有两个好处：第一是以防万一，如果你希望去的公司出了什么临时事
故不能聘用你了，你还没有拒绝其他公司，还可以轻松的接受另一个公司的Offer；第
二是而且减少自己犹豫的可能性——一旦你谢绝了其他的公司的Offer，对方可能还会
给你一个更高的Offer（往往比你拿到的高一点），这个时候如果你已经答应了最喜欢
的公司了，就不会为多一点点的待遇而再反复犹豫了。

无论接受Offer也好，谢绝Offer也好，一定要给所有公司所有跟你联系过的人发信感谢
。他们都在这个过程中花时间为你提供了有用的信息，感谢他们并且交个朋友；以后的
路很长，总有碰到的时候的。

4、Offer的绑定性
最后讨论一下Offer的绑定性。硅谷绝大部分的IT公司的绝大部分Offer都是At-will
employment：雇佣双方的任何一方都可以随时随地无条件的解除雇佣协议 。而一般礼
貌的做法是雇员决定离开公司的话，一般在离开前的两周通知公司；公司如果需要解除
雇佣协议，一般提供两周左右的补偿。

同样道理，就算你接受了一个Offer，随时可以谢绝——当然最好是礼貌的谢绝：跟对
方公司的HR沟通，解释为什么你要谢绝这个Offer，然后跟所有帮助过你的人联系，向
他们解释并且道歉。

我见到过的一些例子是有个朋友接受了一个公司的Offer，然后又打算去另一个公司上
班，但并没有通知第一个公司，直到报到的那天不出现，对方才知道。这就非常不好。

所以， 如果你有更喜欢更想去的公司，你是可以谢绝一个接受了的Offer的。只要你礼
貌地处理好这个过程，跟所有人充分沟通，以后也还是可以保持很好的关系的。这跟你
在美国的信用记录无关。关键是你是否真心想去一个公司。

——–【作者简介】——–
魏小亮（@魏小亮9），1997年国际信息学奥林匹克银牌。2001年，本科就读于清华大学
计算机系，在读期间担任系科协副主席，毕业时获得本科优秀毕业生称号；2004年，毕
业于加州理工学院计算机专业，获得硕士学位；2007年，于加州理工学院计算机专业，
获得博士学位。学习期间，在网络领域的顶级期刊IEEE/ACM Transaction of
Networking、会议IEEE Infocom上发表多篇文章，其中发表在IEEE/ACM Transaction
of Networking上的文章引用次数超过400次。目前，在美国Facebook公司担任总监，领
导Facebook移动产品线性能、可靠性和用户体验分析等方面的研发团队，同时也是
Facebook软件部署团队的一员，负责软件的快速部署；另外，他也是Facebook“新兵营
”的领队之一，负责新员工的培训。（摘自清华博学网）

Iterative Binary Tree Traversal in Java

/** Iteratively traverses the binary tree in pre-order */
public void preorder( ) {
    if( root == null ) return;

    Stack<Node> stack = new Stack<Node>( );
    stack.push( root );

    while( ! stack.isEmpty( ) ) {
        Node current = stack.pop( );
        if( current.right != null ) stack.push( current.right );
        if( current.left != null ) stack.push( current.left );
        System.out.print( current.data + " " );
    }
}

/** Iteratively traverses the binary tree in in-order */
public void inorder( ) {
    Node node = root;
    Stack<Node> stack = new Stack<Node>( );
    while( ! stack.isEmpty( ) || node != null ) {
        if( node != null ) {
            stack.push( node );
            node = node.left;
        } else {
            node = stack.pop( );
            System.out.print( node.data + " " );
            node = node.right;
        }
    }
}

/** Iteratively traverses the binary tree in post-order */
public void postorder( ) {
    if( root == null ) return;

    Stack<Node> stack = new Stack<Node>( );
    Node current = root;

    while( true ) {

        if( current != null ) {
            if( current.right != null ) stack.push( current.right );
            stack.push( current );
            current = current.left;
            continue;
        }

        if( stack.isEmpty( ) ) return;
        current = stack.pop( );

        if( current.right != null && ! stack.isEmpty( ) && current.right == stack.peek( ) ) {
            stack.pop( );
            stack.push( current );
            current = current.right;
        } else {
            System.out.print( current.data + " " );
            current = null;
        }
    }
}

Inorder Tree Traversal without Recursion(use stack)

Using Stack is the obvious way to traverse tree without recursion. Below is an algorithm for traversing binary tree using stack. See this for step wise step execution of the algorithm.

1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then 
     a) Pop the top item from stack.
     b) Print the popped item, set current = current->right 
     c) Go to step 3.
5) If current is NULL and stack is empty then we are done.

Let us consider the below tree for example

            1
          /   \
        2      3
      /  \
    4     5

Step 1 Creates an empty stack: S = NULL

Step 2 sets current as address of root: current -> 1

Step 3 Pushes the current node and set current = current->left until current is NULL
     current -> 1
     push 1: Stack S -> 1
     current -> 2
     push 2: Stack S -> 2, 1
     current -> 4
     push 4: Stack S -> 4, 2, 1
     current = NULL

Step 4 pops from S
     a) Pop 4: Stack S -> 2, 1
     b) print "4"
     c) current = NULL /*right of 4 */ and go to step 3
Since current is NULL step 3 doesn't do anything. 

Step 4 pops again.
     a) Pop 2: Stack S -> 1
     b) print "2"
     c) current -> 5/*right of 2 */ and go to step 3

Step 3 pushes 5 to stack and makes current NULL
     Stack S -> 5, 1
     current = NULL

Step 4 pops from S
     a) Pop 5: Stack S -> 1
     b) print "5"
     c) current = NULL /*right of 5 */ and go to step 3
Since current is NULL step 3 doesn't do anything

Step 4 pops again.
     a) Pop 1: Stack S -> NULL
     b) print "1"
     c) current -> 3 /*right of 5 */  

Step 3 pushes 3 to stack and makes current NULL
     Stack S -> 3
     current = NULL

Step 4 pops from S
     a) Pop 3: Stack S -> NULL
     b) print "3"
     c) current = NULL /*right of 3 */  

Traversal is done now as stack S is empty and current is NULL. 

Iterative Tree Traversals (转载)

Tree traversals, are very important for any interview. Almost any interview question that you get, can be solved by finding out the correct traversal to use. You can read and compare various tree traversals from here .

Although the recursive tree traversals, can be coded very neatly but recursion is generally not preferred. Excessive recursive function calls may cause memory to run out of stack space.

Since the depth of a balanced binary search tree is about lg(n), we need not worry about running out of stack space, even if there are a million elements in the tree. But alas perfectly balanced trees, come at their own cost. Rather efficient height balanced trees is still an active area of interest. So it is quite possible in practical scenarios that the tree may not be balanced. If that is the scenario then we are asking for trouble using recursion, because in the worst case the height of the tree may go up to n and in this case, the stack space will eventually run out and the program will crash.
Iterative tree traversals can be coded easily, using a _ visited _ flag. This has been sufficiently explained at this wiki page . But this requires us to change the structure of the tree, and we would not want that. here we will attempt to develop iterative traversals, without modifying the structure.
Understanding the below given iterative traversals can be a little tricky so the best way to understand them is to work them out on a piece of paper. Use this sample binary tree and follow the steps of the below given codes.

In Order Traversal:
The in order traversal requires that we print the leftmost node first and the right most node at the end. So basically for each node we need to go as far as down and left as possible and then we need to come back and go right. Steps of algorithm are:

1. Start with the node equals root
   
2. Store the node in the stack and visit it's left child.
   
3. Repeat step 2 while node is not NULL, if it's NULL then pop it's parent (i.e. the last node in stack) and print it.
   
4. Now move to node's right child and repeat step 1
   
5. Repeat whole procedure while node is not NULL and stack is not empty
   

Inorder(Tree *p)
{
    stack < Tree* > S;
    do
    { 
        while (p!=NULL)                      
        { 
            // store a node in the stack and visit it's left child
            S.push(p);
            p=p->left; 
        }

        // If there are nodes in the stack to which we can move up
        // then pop it
        if (!S.empty())
        { 
            p=S.top();
            S.pop();

            // print the nodes value
            cout << p->ele << "-";

            // vistit the right child now
            p=p->right; 
        }

    // while the stack is not empty or there is a valid node
    }while(!S.empty()||p!=NULL);
}

Food for Thought: The above given iterative solution makes use of explicit stack. We have only managed to eliminate the recursion, but not the extra space requirement. Can there be another way in which we can give an in-order traversal without using a stack?
Yes! you can do that and there are two methods. But both of them require to change the tree structure as we generally us it.

• One is pretty intuitive, and that is to have a parent pointer, in addition to the child pointer. This eliminates the need for extra space, because the whole purpose of using a stack was to save the parent nodes.
  
• The second is not so intuitive, but a very popular data structure and that is Threaded Binary Tree . This along with the normal structure, also stores a pointer to the next in-order successor of a node. In case there is a right child then the in-order successor is the child otherwise it is one of the successors.
  

Pre Order Traversal:
Pre order is very similar to in order traversal. The way of accessing all the nodes remains the same except the position where we print the node. Now the node is printed/visited before visiting the children of the nodes. Steps are very similar to in-order

1. Start with node equal to root node
   
2. Store the node in the stack, print it and visit it's left child.
   
3. Repeat step 2 while node is not NULL, if it's NULL then pop it's parent (i.e. the last node in stack).
   
4. Now move to node's right child and repeat step 2
   
5. Repeat whole procedure while node is not NULL and stack is not empty
   

  Preorder(Tree *p)    
{ 
    stack < Tree* > S;
    do
    {     
        while (p!=NULL)
        { 
            // storea node in stack and print it's value
            S.push(p);
            cout << p->ele << "-";
            // visit the left child
            p = p->left; 
        }

        // visit the right child
        if (!S.empty())
        {
            p=S.top();
            S.pop();
            p = p->right; 
        }

    } while(!S.empty()||p!=NULL);
}

Post Order Traversal:
Post order traversal is the trickiest one out of them all and hence it is not very frequently asked as an interview question. But Amazon has asked the iterative implementation once. It is useful in some cases

• Tree deletion: In order to free up allocated memory of all nodes in a tree, the nodes must be deleted in the order where the current node is deleted when both of its left and right sub-trees are deleted. This can be done using post-order traversal only.
  
• It is also used in evaluating Post-fix or Reverse Polish Notation.
  

The problem with post-order traversal is that in the previous two cases when a node was popped of from the stack, then it was finally removed and was not accessed again. However in case of post-order the node needs to be accessed from the stack twice, and is deleted only in the second access.
First time we find a node, we push it on to the stack, the second time we examine it from the stack to go to it's right child and then finally after visiting both the right sub-tree and the left-subtree we remove the node from the stack. So a node stays in the stack as long as it's sub-trees have not been visited.

Since, a node has to be visited(printed in the trivial case) only after it's left and right child have been visited, we print a node's value after we have visited the left child followed by the right child. The property that is exploited in this implementation is that the the parent node will always be visited just after visiting it's right child.

After visiting the left child, when we come to the parent node in the stack if the right child is NULL, then we can straight away print the node, but if it's not NULL then we have to check whether the previous node which was printed is it's right child. If it's the right child then we can visit the current node, otherwise the right child has not been visited and we must proceed with the right child.
Hence in this traversal, we have to use a previous pointer, only then will we able to correctly traverse the node. Otherwise we do not know when the right child has been visited or not.

1. Start with the root node.
   
2. Store the node in the stack, and visit it's left child.
   
3. Repeat step 1 while node is not NULL, if it's NULL:
   
   • Pick the top most node from the stack.
     
   • If it's right child is NULL, then print the node and set prev pointer to this node
     
   • If it's not NULL, check whether the right child is equal to prev pointer, if it is then print the node, else repeat step 1 with the right child
     
   • In this step, if you print the node then current is made equal to NULL and this sub-loop is repeated untill stack is not empty and current is NULL
     
4. Since the root node remains in the stack till the end, the terminating condition is untill stack is empty
   

  Postorder(Tree *p)  
{
    stack < Tree* > S;
    Tree *prev;
    do
    { 
        while (p!=NULL)
        { 
            S.push(p);
            p=p->left;
        }
        if(!S.empty())
        {
            while(p==NULL && !S.empty())
            {
                p=S.top();
                if(p->right!=NULL)
                {
                    if(p->right == prev)
                    {
                        cout << p->ele  <<  "-";
                        S.pop();
                        prev = p;
                        p = NULL;
                    }
                    else
                        p = p->right;
                }
                else
                {
                    cout << p->ele  <<  "-";
                    S.pop();
                    prev = p;
                    p = NULL;
                }
            }
        }    
    }while(!S.empty());
}

说一下学术派的代码（java）

前面看到有人说写出来的代码让人一眼就看出是没有工作经验的 这个的确是有可能的，从我自身经验判断 一般来说，具备以下一个或几个特点的代码 会被认为是写java代码写不够多的人写出来的 

 1) 变量名和方法名首字母大写 这个是大忌，一般遇到了，不让过是很正常的 从某种意义上说，这个不是风格的问题 跟goto一样，其实是个错误 

2) 命名中使用下划线 尤其是自定义的系统变量，喜欢用下划线开始 这说明程序猿喜欢介入系统内部实现 which正好是java不提倡的做法 java提倡非侵入式编程 也就是对于已经做好的东西，比如jvm 采用输入参数形式来tune 其次，对于具体对象的管理，采用反射等高级手段来做 直接介入系统内部实现，比如介入jvm内部实现 的方式，其实是不提倡，甚至可以说是禁止的 对于下划线的命名，能不用就不用 所以当你遇到了_myInstance的时候，嗯 

3) static关键字的使用 能写出static方法是好事 说明你懂static是干什么的 但是多数时候，static其实并不是那么频繁滴被使用到 static的代码实现多数时候交给了框架去做 一般如果你要用static 建议单独搞一个类，然后在这个类的命名最后加上Util 比如MyApplicationUtil，这样就显得professional一点 static变量应该尽量避免 关于2和3，有一个特例，就是全局常量（不变的变量）的定义 比如public static final String BIG_COW = "goodbug"; 这个时候你需要static变量和下划线，其它时候，最好不要了 

4) 封装的意识         对于一个类，实现之后，看是否意识到实现了private和set/get方法 还是直接访问内部变量 这个是oop，set/get方法可以有很多理由 比如说，只实现get而不实现set，那么这就是read only 还有并发的时候，可以通过syncrhonized set/get方法来控制并发 等等 

5）最后一个就是看对于各种类的使用 比如Hashtable，这个已经too old了 还有Vector这几个类，都已经old太久了 有新类能够替换这些类，所以如果你打算用java写代码 请躲开这几个“老”类 

这几个细节，虽然说都是rule of thumb，都不难，稍微留意一下，都很容易避开 但是很有趣的是，往往是一些有其它语言经验的程序猿 比如写c++写得比较多的，转过来，会犯这些错误 所以有时候雇主更喜欢新人，白纸一张，可塑性很强 换编程语言的程序猿，会带来不少坏习惯 当然最理想的还是有相关经验的程序猿 只要能针对上诉五点，稍加练习，你的代码显得比较professional问题不大

print all root to leaf paths in a binary tree

public void PrintAllPossiblePath(Node node,List<Node> nodelist)
{
    if(node != null)
    {
            nodelist.add(node);
            if(node.left != null)
            {
                PrintAllPossiblePath(node.left,nodelist);
            }
            if(node.right != null)
            {
                PrintAllPossiblePath(node.right,nodelist);
            }
            else if(node.left == null && node.right == null)
            {

            for(int i=0;i<nodelist.size();i++)
            {
                System.out.print(nodelist.get(i)._Value);
            }
            System.out.println();
            }
            nodelist.remove(node);
    }
}

nodelist.remove(node) is the key, it removes the element once it prints the respective path

3.2 --- design a stack with function min() at O（1） time

Q: How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

A： Thinking at after min value is popped out, it need find the minimum value that pushed before it.
So, we only need a pointer to it.  Thus, for stack S, with min value of B, we add a pointer, when push(A), where A is so far the minimum, then its pointer would point to node B.
但，这样， 修改了Node的结构，是否有点儿太深了？  -------------  书上就是这样解的。
就是把Node的结构，换成了，<Node , int curMin>

另一个方法，就是，加一个min-list,representing that, till now, the minValue,
 （考虑到有重复的min值出现的情况，我们有两个办法：
1：在每个min-list的node中，还要加一个，出现的次数
2：在加入min-list时，如果和迄今为止的最小的同样小 ，我们也加入min-list中。(从书上看到的，其实这个list，更多的是一个stack的功能。可以用stack代替。)

下面是实现。 (但是，从list加入item到stack的时候，push(),总是漏几个，问题出在哪儿呢？？？？)

public class MinStack3_2 {
 LinkList stackList;
 LinkList minList ;

 Node pop() {
  Node poppedNode  = stackList.deleteAtBeginning();
  if (poppedNode.data == minList.header.next.data) {
   minList.deleteAtBeginning();
  }else if(poppedNode.data == minList.header.next.data){
   System.out.println("Error at functioin pop();-----------minList is wrong");
  }
  return poppedNode;  
 }

 void push(Node t) {
  stackList.insertAtBeginning(t);  
  //update the minList, record only the ones, that is the minimum so far
  if (minList.header.next == null || t.data <= minList.header.next.data) {
   minList.insertAtBeginning(t);
  }

 }

 Object min() {
  return minList.header.next;
 }
 public MinStack3_2(){
   stackList = new LinkList();
   minList = new LinkList();
 }
}

 Mistakes:
 1:  Stack的实现 中，由于stack是基于linkList的，所以，如果直接加入的话，仅仅是加入了一个引用。其后，在list中的任何值改变的话，stack的值也会变化。------>故而尽量new 一个值。
2：  又是在printStack的时候， 没有update runner.

3：总是有两个top值，为什么呢? 应该是继承了一个，自己又声明了一个？？？？？是这样的吗？


Learned:

3.1 --- Describe how you could use a single array to implement three stacks.

Q: Describe how you could use a single array to implement three stacks. A: 1) for three stacks, top1, top2,top3, where top1= 3*i top2= 3*i+1 top3= 3*i+2 2) devide array into 3 parts, part 1: 0- array.length()/3; part 2: array.length()/3+1 - 2* array.length()/3; part 3: 2* array.length()/3+1 - array.length() 这个，要好好看看书上的， clean, maintainable 的例子。

3 --- stack and queue

自己写的，两个基本类型的，基于链表的实现。

public class Stack implements Cloneable {
 Node top; // pointing to the toppest node on a stack

 Node pop() {
  if (top != null) {
   Node item = top;
   top = top.next;
   return item;
  }
  return null;
 }

 void push(int k) {
  Node t = new Node(k);
  t.next = top;
  top = t;
 }

 Object peek() {
  return top.data;
 }

 public Stack clone() throws CloneNotSupportedException {
  return (Stack) super.clone();
 }
 
 boolean isEmpty(){
  return (this.top ==null);
 }
}

public class Queue {
 // in this implementation, tail.next is always null;, so that we can enqueue() at tail
 // thus, delete at head();
 Node head, tail;
 void enqueue(Node item){// enqueue at tail. 
  if(tail ==null){
   tail = item;
   head = item;
  }else{
   tail.next = item;
   item.next = null;
   tail = item;
  }
 }
 Object dequeue(){//  dequeue at head 
  // head point to the just added item. or the first in a single list
  if(head!=null){
   Object item = head;
   head = head.next;
   return item;
  }
  return null;
 }
}

Learned:
1: Constructor call must be the first statement in a constructor

2.7 --- check if a list is palindrome

Q:
Implement a function to check if a linked list is a palindrome.

A：
Solution #1: reverse and compare
Idea： create another list reversely , and compare two list  (注意，我们只需要对比前一半儿就行了。 也就是说，创建新的list的时候，计数得知listSize）

 private static boolean checkPalindrome(LinkList list) {
  // create another list reversely , and compare them one by one
  LinkList newList = new LinkList();
  Node runner = list.header.next;
  while (runner != null) {
   Node tmpNode = new Node(runner.data);
   newList.insertAtBeginning(tmpNode);

   runner = runner.next;
  }
  // compare the two list
  Node runner1 = list.header.next;
  Node runner2 = newList.header.next;
  while (runner1 != null && runner2 != null && runner1.data == runner2.data) {
   runner1 = runner1.next;
   runner2 = runner2.next;
  }
  if (runner1 == null && runner2 == null) { // reach the end of these two
             // list
   return true;
  } else {
   return false;
  }

 }

Solution #2: Iterative Approcach
 use a stack to store the first half part.
1) if the list size is already known, delete the size,  (be careful of when the list size is odd.
2) if the list size is unknown.  use a fast/ slow runner, when the fast reach end, slow only at middle, 

 private static boolean checkPalindrome(LinkList list) {
  // create another list reversely , and compare them one by one
  Node slowRunner = list.header;
  Node fastRunner = list.header;
  // in math, fastRunner point to the node: 2,4,6,8
  // slow point to the 1,3,5,7
  while (fastRunner != null && fastRunner.next != null) {
   fastRunner = fastRunner.next.next;
   slowRunner = slowRunner.next;

  }
  boolean isListSizeOdd = false; // default is Even number
  if (fastRunner == null) {// list length is odd number
   // Now slowRunner point to exactly the middle one
   isListSizeOdd = true;
  }

  fastRunner = list.header.next;
  // put into Stack
  Stack stack = new Stack();
  if (isListSizeOdd) {
   while (fastRunner != slowRunner) {
    stack.push(fastRunner);
    fastRunner = fastRunner.next;
   }
  } else { // list length is even number, the slowRunner point to the
   while (fastRunner != slowRunner.next) {
    stack.push(fastRunner);
    fastRunner = fastRunner.next;
   }
  }
  slowRunner = slowRunner.next; // slowRunner point to the half tail part.
  while (slowRunner != null && !stack.isEmpty()) {
   Node tmpNode = stack.pop();
   if (tmpNode.data != slowRunner.data) {
    return false;
   } else {
    slowRunner = slowRunner.next;
   }

  }
  if (slowRunner == null & stack.isEmpty()) {
   return true;
  } else {
   System.err.println("something wrong");
   System.exit(1);
   return false;
  }

 }

这里犯了一个错误，就是由于 边想边写，头脑不够清晰。 导致判断的时候，有混淆。
以后写这种代码的时候，要先想清楚了，在纸上写好了，再誊到eclipse上

Solution #3: Recursive Approcach

要recursively 建立一个前后匹配的对儿。然后，逐层缩简。









Mistakes: 
1: 两个runner， 刚开始用了runner1.equals(runner2). 但是，其实二者是不同的list里的对象。 不能这样搞的。

2.6 -- find the first node of a circular linked list

Q：
Given a circular linked list, implement an algorithm which returns the node at
the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points
to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input: A - > B - > C - > D - > E - > C [the same C as earlier]
Output: C

首先，我们先make circular.(for simplicity，没有边界检查什么的)

 public static void makecircular(LinkList list1, int ithPosition) {
  // making the list1 as circular , by putting the last one's next to the i_th postion
  Node ithNode = null;
  Node runner = list1.header;
  int cound = 0;
  while(runner.next!=null){
   cound++;
   if(cound == ithPosition){
    ithNode = runner;
   }
   runner = runner.next;
  }
  runner.next = ithNode;
 }

A：
 最SB 的方法，就是将map every object into a hash table, and if exist, check whether they are exactly the same. ------但如何保证对象的hash也没有重复呢？？？

用两个指针， 或者说，是两个runner，一快一慢，走阿走，直到快的，追上慢的。（可是这样只能说明有loop. ---- 慢的一次走一步，快的一次走2步)
再一个SB的算法，就是 从头儿一个个得删除节点，然后，看是否还有回路。
呵呵，先用SB的算法做吧。

自己写的算法，比较SB， 而且，结果也不全对，还是不写在这儿了。肏，浪费了好几个小时。



第二种方法，就是书上的解释。
fast runner一次跑2个节点。
slow runner一次跑1个节点。
第一次相遇后，fast runner的速度降为1，并回到header所指向的起始位置。，slow runner继续跑。直到再次相遇的时候，就为第一个节点。
自己的证明如下。

代码如下：

	private static Node findFirstOfLoop(LinkList list) {
		Node slowRunner = list.header.next;
		Node fastRunner = null;
		if (slowRunner != null) {
			fastRunner = slowRunner.next;
		}
		// find the first meet, record its position
		while (slowRunner != fastRunner) {
			if (fastRunner == null || fastRunner.next == null) {
				// we find that the list do not contains loop
				return null;
			}
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next.next;
		}
		// Now they are the same, we reset the fastRunner at the beginning, and
		// run again
		fastRunner = list.header.next;
		slowRunner = slowRunner.next;
		while (slowRunner != fastRunner) {
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next;
		}
		return slowRunner;

	}

Mistakes：
1： 在方法中， i 应该每次增加的，可是为什么没有增加呢？
     static void printList(LinkList list, int maxNumElements) {
      
        Node node = list.header.next;
        int i =0;
        while (node != null && i<maxNumElements) {
            System.out.print(node.data + "\t");
            node = node.next;
            i=i+1;
        }
        System.out.println();
    }

运行时，i的值，一直是0. 而如果变成i = i+1 就可以了。为什么呢？ Learned: 1: java中， constructor call constructor

class AA { 
    private String a;
    private String b;
 
    public AA(String a){ 
        this.a = a;
    } 
   
    public AA(String a, String b){ 
        this(a);
        this.b = b;
    } 
}

2:在 circular list中， 仅仅delete 指向的一个节点，是并不能真正删除的， 要考虑是否因为是circluar的，所以，被略过的object，依然还存在。

3：  看下面的一段代码，

		// Now they are the same, we reset the fastRunner at the beginning, and
		// run again
		fastRunner = list.header.next;
		while (slowRunner != fastRunner) {
			slowRunner = slowRunner.next;
			fastRunner = fastRunner.next;
		}

仅仅这样的话，slowRunner 和fastRunner会相差一个的距离。-------->而再上图的证明中，第一次相遇后，fastRunner要回到队列的首位置，   而  slowRunner是要走到下一个的。

2.5 ---- sum at two list (reverse and forward order)

Q:  (书上的forward 的解法，明显更繁琐些）

You have two numbers represented by a linked list, where each node contains a
single digit. The digits are stored in reverse order, such that the Ts digit is at the
head of the list. Write a function that adds the two numbers and returns the sum
as a linked list.
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2).That is, 617 + 295.
Output: 2 -> 1 -> 9.That is, 912.
FOLLOW UP
Suppose the digits are stored in forward order. Repeat the above problem.
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5).That is, 617 + 295.
Output: 9 -> 1 -> 2.That is, 912

A:
Reverse case:

simply extract the data into an inter, and add them ,then transform them back to the list form. ( in CtCi, they add on the list, directly. which make us to manipulate the math and (进位)

 
public static LinkList reverseOrderSum(LinkList list1, LinkList list2) {
  LinkList newList = new LinkList();
  int sum1 = 0;
  int sum2 = 0;
  Node runner = null;
  int numDigits = 0;
  // calculate sum of list1,
  runner = list1.header.next;
  while (runner != null) {
   sum1 += runner.data * (Math.pow(10, numDigits));
   runner = runner.next;
   numDigits++;
  }
  // calculate sum of list2,
  runner = list2.header.next;
  numDigits = 0;
  while (runner != null) {
   sum1 += runner.data * (Math.pow(10, numDigits));
   runner = runner.next;
   numDigits++;
  }
  int total = sum1 + sum2;
  Integer totalInt = new Integer(total);
  String strSum = totalInt.toString();
  System.out.println(strSum);
  for (int i = strSum.length() - 1; i >= 0; i--) {
   String subChar = strSum.substring(i, i + 1);
   int nodeData = Integer.valueOf(subChar);
   newList.append(new Node(nodeData));
  }

  return newList;

 }

Forward case:

 public static LinkList forwardOrderSum(LinkList list1, LinkList list2) {
  LinkList newList = new LinkList();
  int sum1 = 0;
  int sum2 = 0;
  Node runner = null;
  // calculate sum of list1,
  runner = list1.header.next;
  while (runner != null) {
   sum1 = sum1 * 10 + runner.data;
   runner = runner.next;
  }
  // calculate sum of list2,
  runner = list2.header.next;
  while (runner != null) {
   sum2 = sum2 * 10 + runner.data;
   runner = runner.next;
  }

  int total = sum1 + sum2;
  Integer totalInt = new Integer(total);
  String strSum = totalInt.toString();
  System.out.println(strSum);

  for (int i = 0; i < strSum.length(); i++) {
   String subChar = strSum.substring(i, i + 1);
   int nodeData = Integer.valueOf(subChar);
   newList.append(new Node(nodeData));
  }
  return newList;

 }

Mistakes:
1:   因此， 不能简单得用 10^2 来期待得到100， 而应该用Math.pow(10,2)
^ is the bitwise exclusive OR (XOR) operator in Java (and many other languages). It is not used for exponentiation. For that, you must use Math.pow.

2.4 -- partion a linked list around a value x

Q:
Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x.

A:
find a pivot point,   (e.g. the first one)   and all the rest of node, whose value less than pivotValue x,  insert at head.

 private static void partitionOnPivot(LinkList list, int pivotValue) {
  // use the first node as the pivot, if the following less then
  // pivotValue, insert before, otherwise, insert after
  Node runner = null;
  Node preRunner = null;;
  if (list.head != null) {   
   preRunner = list.head;
   runner=preRunner.next;
  }
  while (runner != null) {
   if (runner.data < pivotValue) {// insert before pivotNode
    preRunner.next=runner.next; //delete runner off the list
    //insert runner at the beginning of the list
    runner.next = list.head;
    list.head = runner;
    
    //position runner 
    runner = preRunner.next;
   }else{
    preRunner = runner;
    runner = runner.next;
   }
   
  }

 }

Mistakes:
1:
对于一个LinkList类，定义为：

public class LinkList {
 Node head;
}    

  Node runner = null;
  Node preRunner = list.head;
  if (list.head != null) {   
   runner = list.head;   
  }

那么，对于一个列表为：
8 40 41 的list，
runner.data的值为什么呢？？？ -------------------          未定义（或者说，没有）
preRunner.data的值为什么呢？？？？？------------------ 8

update ： 上面这个问题，会造成混乱。 原因就在于，我们定义LinkList中的head时， 是把它作为一个单独的object，or a pointer pointing to the first element of the list.

以后的程序中，暂定是前者。（否则，就应该叫 firstNode)

2.3 --- given only the middle node, delete it from the list

Q: 2.3 
Implement an algorithm to delete a node in the middle of a singly linked list, given only access to that node.
EXAMPLE
Input: the node c from the linked list a - > b - > c - > d - > e
Result: nothing is returned, but the new linked list looks like a- >b- >d->e

A:
就是，从后向前，一个个地copy，似乎没有别的办法了。

 
public static Node getMiddle(LinkList list, int listSize){
  Node tmp = list.head;
  for(int i = 0 ;i<(int)(listSize/2); i++){
   tmp = tmp.next;
  }
  return tmp;
 }
 public static void deleteMiddleNode(Node node){
  Node nextNode = node.next;
  while(nextNode.next != null){
   node.data = nextNode.data;
   
   node = nextNode;
   nextNode = nextNode.next;
  }
  node.data= nextNode.data;
  node.next=null;
 }

记得，检查边界值。 

2.2 --- find the kth to the last element of a singlely linked list

Q:
Implement an algorithm to find the kth to last element of a singly linked list.

A:

假设只需要得到答案从前数是第几个，（ 可以），利用一个变量来记下，递归的次数，nthToLast(curNode.next, k)  ，以此来返回从正向数，应该输出的index数。（不能得到data）。

Method 1: use two iterations, first to calculate the size of list.
               Then run through size - k  of the elements.

Method 2:  use two pointers, with their distance as k.

 public static Node twoRunKthtoLast(LinkList list, int k) {
  int listSize = 0;
  Node pointer = list.head;
  while (pointer != null) {
   listSize++;
   pointer = pointer.next;
  }
  if (k > listSize) {
   System.err.println("no enough node in list");
   return null;
  } else {
   int frontIndex = listSize - k;
   pointer = list.head;
   for (int i = 0; i < frontIndex; i++) {
    pointer = pointer.next;
   }
   return pointer;
  }
 }

 public static Node twoPointerKthtoLast(LinkList list, int k) {
  Node preRunner, behindRunner;
  preRunner = list.head;
  for (int i = 0; i < k; i++) {
   if (preRunner == null) {
    System.err.println("no enough node in list");
    return null;
   } else {
    preRunner = preRunner.next;
   }
  }
  // Now all preRunner point to the k+1 th element,
  behindRunner = list.head;
  while (preRunner != null) {
   preRunner = preRunner.next;
   behindRunner = behindRunner.next;
  }

  return behindRunner;
 }

Mistakes：
1：LinkList.head 所指向的，是一个node， 因此不能计数
2:  永远记住， 返回的对象，可能是null的。 不能随便用它来干活儿。  LOL

2.1 --- remove duplicates from unsorted linked List

Q:
2.1
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

A:
Using hash table
（没想到，或者想到了，但是以前没有做过，故而不知道去搞）

 public static void deleteDuplicates(LinkList list){
  Hashtable table  = new Hashtable();
  Node pointer = list.head;
  Node prePointer = null;
  while(pointer != null){
   if(table.containsKey(pointer.data))
    prePointer.next = pointer.next;
   else{
    table.put(pointer.data, true);
   }
   prePointer = pointer;
   pointer = pointer.getNext();
  }
 }
 public static void deleteDuplicatesNoBuffer(LinkList list){
  // use two pointers to delete duplicates
  Node curPointer = list.head;
  Node runner = null;
  Node preRunner = null;
  while(curPointer != null){
   preRunner = curPointer;
   runner = curPointer.next;
   // check if all has the same value
   while(runner!= null){
    if(runner.data == curPointer.data){
     // delete the at position runner. 
     preRunner.next = runner.next;
    }else{
     preRunner = runner;     
    }
    runner = runner.next;
   }   
   curPointer = curPointer.next;
  }
  
 } 

Mistakes:

1: 在list iterate的时候， 经常忘记，update指针，使之指向下一个位置。

2 Linked Lists ---------- LinkList, 和 Node class 及一些常用基本操作

 例如: LinkList 类

public class LinkList {
 Node head;

 public LinkList() {
  head = null;
 }

 void append(int d) {
  Node end = new Node(d);
  Node n = this.head;
  while (n.next != null) {
   n = n.next;
  }
  n.next = end;
 }

 void append(Node newNode) {
  // make sure newNode.next point to null
  newNode.next = null;
  Node n = this.head;
  if (n == null) {
   this.head = newNode;

  } else {
   while (n.next != null) {
    n = n.next;
   }
   n.next = newNode;
  }
 }
}

class Node {
 Node next;;
 int data;

 public Node(int d) {
  data = d;
  next=null;
 }
}

Mistakes:
1: 创建类的constructor时，不能有void 等返回关键字。。
另外，一个java源文件，只能有一个public的类。
2: 在创建Node类时，要注意在constructor里，声明next=null；否则，就不知道跑哪儿去了。

Learned:
1：注意： “runner” technique

和 “ Recursive Problems.

1.8 ---- check string rotation, using one call of subString();

Q:
Assume you have a method isSubstring which checks if one word is a
substring of another. Given two strings, si and s2, write code to check if s2 is
a rotation of si using only one call to isSubstring (e.g.,"waterbottle"is a rota-tion of "erbottlewat").

A:
idea:
s1 = xy
s2 = yx

那既然，单独的，这样，无法直接得到。
我们就想办法，给他们增大（增长）    。
例如：
s2 = yz
s1" = s1+s1 = xyxy

然后，就可以用：isSubstring()了。
当然，还是要check the string length.



Mistake:
刚开始，又是没有看明白题目。  难怪，感觉太简单了呢。
并不是全部的, s1.length的rotation，可能仅仅是rotatte了一部分。

哎， 看不明白题目，害死人啊~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后面试的时候，一定要多问一下面试官，确认自己搞明白了题目。


Learned：
这个，因为刚开始看错了题目。
看了一眼答案。  （只看了s1=xy）给了提示。
哎，还是自己不够聪明阿

1.6 ---- rotate the matrix

Q:
 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

A:

 
public class Main {

 public static void main(String[] args) {

  int imSize = 6;

  int[][] image = new int[imSize][imSize];
  // Initialize image
  Tool.randomInitializeArray(image);
  Tool.printArray(image);

  rotateImage90(image);

  Tool.printArray(image);
 }

 public static void rotateImage90(int[][] im) {

  // rotate the matrix in place, clock wise direction of 90 degree
  int numRow = im.length;
  int numCol = im[1].length;

  // check they are square matrix
  if (numRow != numCol) {
   System.out.println("not square matrix");
  }
  if (numRow == 0) { // actually, this could be ignored.
   System.out.println("no elements");
  }
  int imSize = numRow;
  if (imSize % 2 == 1) {
   // if imSize is odd number, rotate from the most inner circle ( of
   // size 1*1)
   int centerIndex = (int) (numRow / 2) + 1; // in math, this is the
              // center point.
   centerIndex = centerIndex - 1; // because java starts array index
           // from zero, we need minus 1
   int radius = (int) (numRow / 2);
   for (int d = 1; d <= radius; d++) {
    // there are four lines per circle. we rotate them
    // one-by-one
    int lineLength = 2 * d;
    int[] tmpLine = new int[lineLength];
    // save the line above to tempArray
    for (int i = -d + 1; i <= d; i++)
     // ignore the left most vertex
     tmpLine[i - (-d + 1)] = im[centerIndex - d][centerIndex + i];

    // copy left to above
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex - d][centerIndex + i] = im[centerIndex - i][centerIndex
       - d];

    // copy below to left
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex - i][centerIndex - d] = im[centerIndex + d][centerIndex
       - i];

    // copy right to below
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex + d][centerIndex - i] = im[centerIndex + i][centerIndex
       + d];

    // copy original above(now in tmpLine) to right
    for (int i = -d + 1; i <= d; i++)
     im[centerIndex + i][centerIndex + d] = tmpLine[i - (-d + 1)];
   }
  } else { // imSize is even number, i.e. , imSize == 2, 4 , 6, 8....
   int indexLeftTop = (int) (imSize / 2) - 1;
   int indexRightBottom = (int) (imSize / 2);
   int radius = (int) (imSize / 2);
   // because by considering
   System.out.println("we are working on the array, sized == "
     + imSize);
   for (int d = 1; d <= radius; d++) { // for each layer,with distance
            // to center is d
    int lineLength = indexRightBottom - indexLeftTop;
    int tmpLine[] = new int[lineLength];
    // save the above circle into the tmpLine ( do not include the
    // topLeft corner
    for (int i = 1; i <= lineLength; i++) {
     tmpLine[i - 1] = im[indexLeftTop][indexLeftTop + i];
    }
    // transfer the left into above
    for (int i = 1; i <= lineLength; i++) {
     im[indexLeftTop][indexLeftTop + i] = im[indexRightBottom
       - i][indexLeftTop];
    }
    // transfer the bottom into left
    for (int i = 1; i <= lineLength; i++) {
     im[indexRightBottom - i][indexLeftTop] = im[indexRightBottom][indexRightBottom
       - i];
    }

    // transfer the right into the bottom
    for (int i = 1; i <= lineLength; i++) {
     im[indexRightBottom][indexRightBottom - i] = im[indexLeftTop
       + i][indexRightBottom];
    }

    // transfer the saved,original above line into the right
    for (int i = 1; i <= lineLength; i++) {
     im[indexLeftTop + i][indexRightBottom] = tmpLine[i - 1];
    }
    indexLeftTop--;
    indexRightBottom++;
   }// end of the for, for each layer, from inner most to the outer
    // most

  } // end of else, for the case that the length is even number
 } // end of function rotateImage90
}

Mistakes:
0：  FUCK！！！！！！！！！！！
因为在rotate完毕，要打印数组的时候，是直接从上面copy的两个for loop，其中，就包含了一行 image[i][j] 的初始化代码。。我日阿
        以后再copy代码的时候，一定要注意，先看看代码里都是什么。(即使是自己写 的）
 
1: 遇到数组溢出。 问题出在
int centerIndex = (int)(numRow/2) + 1;
        int radius =  (int)(numRow/2)+1;  //这里，的radius是从上面一行copy下来的。
而应该自己写， 就不会加上这个 1 了。----------哎，人生阿

2： 遇到数组问题，  毛病出在。

  自己作运算的时候， 都是按照数学里的start from 1, 来计算，安排的。
可是，java中是start from 0.   ------------>  刚开始的时候，还记得，但是，直接写index的时候，就忘了。

3：for odd number, for each line, to copy and rotate into another line, 应该记住，一条边，随说是包括两边顶点。 但rotate的时候，只需要一个顶点就够了

            for(int i = -d; i<=d;i++) ------------------------这是错误的
            for(int i = -d; i<d;i++) ------------------------这是正确的。

 4：对于数组
a b c
d e f
g h i

如果按照上面的rotate算法，[a; d] 应该是 取代[ b c ] 的位置。
而不是，[ d ; g] 取代 [a b]的位置。
因此：我的初始代码中

  int imSize  = numRow;
  // if imSize is odd number,  rotate from the most inner circle ( of size 1*1)
  int centerIndex = (int)(numRow/2) + 1;  // mathetically, this is the center point. 
  centerIndex = centerIndex -1;       // because java starts array index from zero, we need minus 1
  int radius =  (int)(numRow/2);
  for (int d = 1; d <= radius; d++){
   // there are four lines for each circle.  we just rotate them one-by-one
   int lineLength = 1+2*d;
   int[] tmpLine = new int[lineLength];
   // save the line above to tempArray
   for(int i = -d; i

是错误的， 是假设了[ d ; g] 取代 [a b]的位置。 5: 对于，矩形边是偶数的时候 ， 在rotate完了每一圈之后，  忘了update indexLeftTop 和indexRightBottom的值了。

1. Strings and Array ------ 一些简单的，常用的操作，放在一个Tool类里。

思想就是： 对于，例如， 实例化一个数组， 和打印出一个数组， 自己声明了一个常用的类。

public class Tool {

  static void printArray(int[][] arr){

  System.out.println();
  int row = arr.length;
  int col = arr[0].length;
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    System.out.print(arr[i][j] + "\t");
   }
   System.out.println();
  }
 }

  static void randomInitializeArray(int[][] arr) {
  // TODO Auto-generated method stub
  int row = arr.length;
  int col = arr[0].length;
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    arr[i][j] = (int) (Math.random() * 50);
   }
  }
 }
 
}

1.7----- set entire row and column as zeros if element is 0

Q:

Write an algorithm such that if an element in an MxN matrix is 0, its entire row
and column are set to 0

A：
using two index array to remember which row(column ) would be set to zeros.

public class code1_1 {
public class code1_1 {

 public static void main(String[] args) {

  // String str = " 234o;908aslfjz";
  int M = 8;
  int N = 7;
  int[][] arr = new int[M][N];
  initializeArray(arr);
  // print out the array.
  for (int i = 0; i < M; i++) {
   for (int j = 0; j < N; j++) {
    System.out.print(arr[i][j] + "\t");
   }
   System.out.println();
  }

  checkAndSetZero(arr);
  System.out.println();
  System.out.println();
  // print out the array.
  for (int i = 0; i < M; i++) {
   for (int j = 0; j < N; j++) {
    System.out.print(arr[i][j] + "\t");
   }
   System.out.println();
  }
 }

 private static void checkAndSetZero(int[][] array) {
  int row = array.length;
  int col = array[0].length;
  int[] rowIndex = new int[row];
  int[] colIndex = new int[col];
  // check zero, and set indexes
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    if (array[i][j] == 0) {
     rowIndex[i] = 1;
     colIndex[j] = 1;
    }
   }
  }
  // set the rows into 0s, if rowIndex is zeros
  for (int i = 0; i < row; i++) {
   if (rowIndex[i] != 0) {
    // change the whole row as zero
    for (int j = 0; j < col; j++) {
     array[i][j] = 0;
    }
   }
  }
  // set the col into 0s, if colIndex is zeros
  for (int j = 0; j < col; j++) {
   if (colIndex[j] != 0) {
    // change the whole row as zero
    for (int i = 0; i < row; i++) {
     array[i][j] = 0;
    }
   }
  }
 }

 private static void initializeArray(int[][] arr) {
  // TODO Auto-generated method stub
  int row = arr.length;
  int col = arr[0].length;
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    arr[i][j] = (int) (Math.random() * 50);
   }
  }
 }

}

Mistakes:

 Learned:
Use two index array

1.5 ------------------- string compress

Q:
1.5 Implement a method to perform basic string compression using the counts
of repeated characters. For example, the string “aabcccccaaa” would become
“a2blc5a3”. If the "compressed" string would not become smaller than the original string, your method should return the original string.


A：

public static String compressString(String str) {

    // assume str are all ASCII

    if (str == null)

        return null;

    // check there do not exist digits

    for (int i = 0; i < str.length(); i++)

        if (isDigit(str.charAt(i))) {

            System.err.println("inputs string exist Digits");

            System.exit(-1);

        }

    // count the repeated char number

    int[] charCount = new int[str.length()];

    char lastChar = str.charAt(0);

    for (int i = 1; i < str.length(); i++) {

        if (str.charAt(i) == lastChar)

            charCount[i] = charCount[i - 1] + 1;

        else

            lastChar = str.charAt(i);

    }

    // after counting , if at most two sequence,(i.e. no compress)

    // return original

    // now, this can be compressed

    StringBuffer sbf = new StringBuffer();

    for (int i = 0; i < str.length(); i++) {

        char ch = str.charAt(i);

        if (charCount[i] == 0)

            sbf.append(ch);

        // Then, we need add the digits, instead of chars

        while (i + 1 < str.length() && charCount[i + 1] > charCount[i]) {

            i++;

        }

        sbf.append(charCount[i] + 1);

    }

    String newStr = sbf.toString();

    if (newStr.length() >= str.length())

        return str;

    else

        return newStr;

}

private static boolean isDigit(char ch) {

    if (ch <= '9' && ch >= '0')

        return true;

    else

        return false;

}

  



Mistakes:
0：  一上来，题意没看清。    例子中，"b" 后面，压缩后，为1的。
  应该仔细看题的。----------> 面试时，应该重复听到的问题。 说出自己的理解。


1:  all objects should be checked "null" , otherwise, when running, there might be some nullPointerException.
2:   系统运行，遇到error，要打印提示，并跳出的语句不会。
          这是刚刚用到的。
               System.err.println("   error message      ");
                System.exit(-1);
3:   做循环的时候，应该先判断边界问题， 再去作别的判断。
例如，上面答案里： 
      while( charCount[i+1] > charCount[i] && i+1<str.length()  )      是不对的。会有边界溢出。
应该 while(i+1<str.length() && charCount[i+1] > charCount[i] )



学到：
1：       在paper上写完，一定要自己在脑子里，把各种情况都考虑一遍。
           例如，这里，就因为开始申请的chCount 全为零， 最后StringBuffer.add(count)的时候，要加1的。
2：   

1.4-------Replace space in char[]

Q:
Write a method to replace all spaces in a string with'%20'. You may assume that
the string has sufficient space at the end of the string to hold the additional
characters, and that you are given the "true" length of the string. (Note: if imple-menting in Java, please use a character array so that you can perform this opera-tion in place.)
EXAMPLE
Input: "Mr John Smith"
Output: "Mr%20Dohn%20Smith"


A:

static void replaceSpace(char[] ch, int n){

    // n is the number that actually saved in str

   

    //scan to count the number of space

    int numSpace = 0;

    for(int i = 0 ; i<n; i++){

        if(ch[i]==' ')numSpace++;

    }

    //reversely replace the tokens

    int numSpaceUnreplaced = numSpace;

    for (int i = n-1; i >= 0;i-- ){

        if(ch[i] != ' '){

            ch[i+2*numSpaceUnreplaced] = ch[i];

        }

        else{

            ch[i+2*numSpaceUnreplaced-2] = '%';

            ch[i+2*numSpaceUnreplaced-1] = '2';

            ch[i+2*numSpaceUnreplaced]   = '0';

            numSpaceUnreplaced--;

        }

    }

    System.out.println(ch);

}

Mistake:
1: 竟然不知道怎么声明 char 数组，  哎， 最后只能用String.toCharArray()来声明。
  应该是这样：

  char[] copyFrom = {'d', 'e', 'c', 'a', 'f', 'f', 'e',
            'i', 'n', 'a', 't', 'e', 'd'};

2:

1.3------- check if one string is the permutation of the other

Q:
 Given two strings, write a method to decide if one is a permutation of the other.

A:

public static boolean isPermutation(String str1, String str2){

    if (str1 == null && str2 == null)return true;         //both are not nulll

    else if (str1 == null || str2 == null)                       // only one is null

        return false;

    else{                                                                // both are not null ,  maybe of length 0

        if(str1.length()!= str2.length())

            return false;

        // Now they are of the same length, and

        char[] arr = str1.toCharArray();

        Arrays.sort(arr);

        str1 = new String(arr);

       

        arr = str2.toCharArray();

        Arrays.sort(arr);

        str2 = new String(arr);

        if(str1.equals(str2))    return true;

        else                return false;

    }

}

Mistakes：
1： java里面， 没有elseif 语句， 只有 else if
2:   没有清楚， Arrays.sort(arr); 返回是void，  而所谓的排序，就是在arr里直接操作了。
    另外， 要import java.util.Arrays; 
 
3: 书上说“    in your interview, you should always check with your interviewer about the size of the character set."
4:   另外一个方法，就是  ”check if the two strings have identical character counts.

学到的：


 可以看这里 java传值还是传引用
 
参见
http://www.javaresearch.org/article/3156.htm
1、对象是按引用传递的
2、Java 应用程序有且仅有的一种参数传递机制，即按值传递
3、按值传递意味着当将一个参数传递给一个函数时，函数接收的是原始值的一个副本
4、按引用传递意味着当将一个参数传递给一个函数时，函数接收的是原始值的内存地址，而不是值的副本写的没错，但是文字太多，第二条就已经把人弄糊涂了，得仔细看完4条才清楚。而且对String类型的疑惑没有解决。
这么简单的事情，何必这么绕呢？为啥没人跟c++过不去，偏要跟Java来劲？
三句话总结一下：
1.对象就是传引用
2.原始类型就是传值
3.String等immutable类型因为没有提供自身修改的函数，每次操作都是新生成一个对象，所以要特殊对待。可以认为是传值。
对于，String类型 ，可以看这里，
说完了java的String类型，我们最后看看java函数参数的传递，到底是值传递还是引用传递呢？一般的说法是对于基本类型比如int、char是值传递，对于对象类型是引用传递。这种说法没错，但是请看下面的例子：
String s=”abc”;
change(s);
System.out.println(s);
public void change(String str)
{
     str=”abcd”;
}
上面的程序会有什么结果呢？打印abc还是abcd，运行程序会发现打印的是abc，完了，似乎不合乎常理，按理说String 也是对象，应该是引用传递才对啊，有的同学知道java的String类型是不可变类型，会得出结果abc，具体解释是String就相当于是char[]的包装类。包装类的特质之一就是在对其值进行操作时会体现出其对应的基本类型的性质。在参数传递时，包装类就是如此体现的。所以，对于String在这种情况下的展现结果的解释就自然而然得出了。同样的，Integer、Float等这些包装类和String在这种情况下的表现是相同的。下面从函数参数传递的方式来理解也可以得出相同的结果。
java的参数传递本质上都可以认为是值传递，对基本类型自然不必说，对于对象类型，传递的是对象的地址，地址是个数字，也是基本类型，所以也还是值传递的， 有了这个基础，上面的题目可以这样理解，s是字符串abc的地址，调用change方法时，把s的拷贝赋给str，即str也指向abc，但是在方法里又把str指向abcd，str就是abcd的地址了，但是s还是指向的abc。

1.2 ---- using C, reverse a null-terminated string

Q:
Implement a function void reverse(char* str) in C or C++ which reverses a null-
terminated string.
A:

1.1-------- check if a string has all unique characters

Q:
    implement an algorithm to determine if a string has all unique characters.

   What if you cannot use additional data structures?

A:

// (With additional structures.)

    public static boolean isUniq(String str){

        // assuming that the str chars are all ASCII character

        if (str == null && str.length()==0) return true;

        if (str.length() > 128) return false;

        int[] ascii= new int[128];

         char ch;

        for(int i = 0; i< str.length();i++ ){

ch = str.charAt(i);

            if (ascii[ch]>0) {

                return false;

            }else{

                ascii[ch]++;

            }

        }

        return true;
    }

Mistakes:
0：  最恶心的是， 上面的128，是ASCII码的数目吗？  明明应该是256，  日啊~~~~
1: Cannot make a static reference to the non-static method isUniq(String)
    either declare an object, or  use static

2:  having a returned data type in a method declaration, you MUST return something eventually.
    Even you returned somethig earlier,  but should also return something

3: 竟然在上面，忘了取出str的各个char 的值~~~~~~~~~~~~丢人

4:if (str == null && str.length()==0) return true;
    这里，&& 后面的str   “can only be null"
    而且，这里应该用或    ||   的，  逻辑混乱。   哎~~~

5：  ascii 用boolean格式，明显比 int 要好，又不是让你数数。 哎



改进：
1：    用 bitvector 代替boolean, 只用1/8的空间。
2：   如果假设仅仅是a-z的时候，只用一个int 类型， 4*8 = 32 个bit，就可以了。
             但，书里面的移位是啥意思？