Lexi's Leetcode solutions

最近看到一段很受启发的话，我用翻译腔翻译如下：

“去神秘化” – 如果我们知道一个让外界看起来很神秘的东西是如何运作的，我们就有责任分享我们的所知。知识就是力量——而且力量从来不会因为被分享而减弱，它只能增强。“去神秘化”帮助的不仅仅是我们自己，他更可以帮助别人。

相反的，“神秘化”则是故意把简单的东西搞得神秘兮兮，好让别人觉得我们很了不起。“去神秘化”一般来源于我们自己的不安全感。

我被感动够呛，心想怎么能更帮助别人呢，想来想去决定写一篇博文，去神秘化由来已久的关于“硅谷大公司招的都是最牛的员工”的想法。

我在Google将近三年了。每次回国都耀武扬威的，有一次我朋友的老公一听我是Google的做Android的，干脆要拉我去360（他的公司）做讲座。这种现象在和这个blog的读者互动的时候也很常见，经常有人觉得我特别厉害，什么都会，然后黯然神伤的认定自己啥也不会，Google这种公司对他（她）来说是不可能的。

To help people demystify this “硅谷大公司招的都是最牛的员工” perception, here’s a little something I want to share:

I don’t know SQL. I know “Select.. from..”, but I don’t know wtf is a foreign key, and I have to google if I need to write a “like” expression for regex. My manager first heard it, he said “Are you a CS major?” – not in a hurtful way, but was surprised because DB is supposed to be a required class for CS major. I replied confidently: “Yes.”

直到今天，我还是不知道foreign key是啥。我也并不是个垫底员工，我的performance一般是above average，尽管我在工作上花的时间肯定是below average。我其实OS也不怎么会，computer architecture也不怎么会，接到一个新project的时候心里都是黑人问号脸。以前有人在MITBBS上人肉我，说我是刷脸进的公司，但其实我也认识很多男生同事，他们跟我水平基本一致。不是我以貌取人，但是他们真的不太可能是刷脸进的。但我们都有一个共同特点——我们都只刷刷题就被放进来了，但是都干得不错。难道Google要做的工作难度那么低么？也不是，系统也很复杂，但我发现只要静下心来，learn on the job就可以了。SQL这事儿，我也就是开开w3schools稍微看了几篇我能用上的，若是以后要用foreign key，我再看就是了。至于我老板会不会发现我连SQL都不会而看低我，以后不给我promotion？If anybody think that way, I figure they have a lot of growing up to do.

天，我的文笔太烂，简直写不下去了。总之，我就是想告诉我的读者，如果你想来硅谷大公司，不要被名头吓到了。真的没什么了不起的，我们都是CS专业上缺胳膊短腿的人，你不要觉得“就刷题进，别的啥也不会”不靠谱。光刷题这个事情，我觉得已经考验了你的恒心，毅力，逻辑，面对挫折的能力，举一反三的能力等软实力，而硬实力永远可以靠软实力获得。这毕竟还是个刷题博客，博主就苦口婆心的劝你，别瞻前顾后的，埋头刷题吧！

转眼也写了一年Android app了，每次却总是左抄抄右抄抄，好使就行，回头就忘。不好好理解总结，同样的事情做过之后竟一点印象都没有。是不是很熟悉？这跟当年刷leetcode的状况一模一样。所以今天决定开始在这个blog总结android开发经验，再加上中文的安卓文档也不咋地，csdn几个blog则太面向中国程序员（动不动什么“句柄”之类的词都能出现，让在美国学CS的人不知所云），所以希望这个blog能帮助那些看满篇子英文头疼，但是又找不到好的中文resource的android developer, like myself 🙂

前一阵我的朋友拿到了某著名IT公司offer (as developer)，出于隐私，我只能说这个公司不是FLG但是和Amazon差不多。I’m very proud!

Her background: 国内金融类本科，美国金融类master，毕业不好找工作，于是来湾区上了一所不知名的regional college的engineering grad school，两年program，一毕业立刻拿到了两个大IT公司的offer.

于是一时间她成了我身边不少妹子的role model；湾区很多程序员男生养一个非程序员且收入较低或待业的女生的情况，这些程序员男生有不少希望自己妹子能转行CS的；一来更有共同语言，二来两个程序员的工资才能在湾区这个失控的地方买得起房子。我狐假虎威的到处炫耀朋友的成就，无意间忽悠了这么一批人，于是我觉得应该再来顺道忽悠一下我的读者们！So, how did she do it?

我觉得有这么几个重点：

1. 决心转行要趁早。两年时间一晃而过，当你同样背景的文科妹子还在自我怀疑，纠结要不要转CS的时候，你已经学成并拿到offer了。
2. 湾区本地学校的CS master还真不少，入学要求不高，而且申请费也不贵，感觉简直是专门cater需要转行CS的人的要求；学生大概也都是类似经历，去了更会有“不是一个人在战斗”的气氛，和有共同愿景的人一起努力会更有劲头吧~
3. CS真心是个不需要基础的学科，所以众多高中生才能从车库里统治世界的。黑屏绿字都吓唬人的。一切从头开始，理科背景的人也未必多多少优势。
4. 上了学就开始刷题，静心刷一年，只要没有傲娇到非某个dream company不去，湾区底薪11k+的大公司多如牛毛，拿下这些offer都不是问题。那么专业课没时间好好学，拿到offer后在工作中露馅了怎么办？Just learn everything on the job.
5. 最好身边有一个CS的朋友可以支持你，在你不会的时候给你讲两句；但是没有也没关系，多问问同学，也正好培养自己独立思考。

So, ask yourself:

1. 我喜欢程序员的生活吗？（而不是“我能干得了CS吗我够聪明吗” —— Everyone can be a programmer）
2. 我有两年时间用来转行吗？
3. 我有30w人民币闲钱交学费吗？
4. 我是不是两年后在当前的职业也不会涨到CS毕业生的底薪？而且挣多少钱对我来说是重要的？而且我本来也不喜欢当前的职业？
5. 我GRE是不是还没过期？

If you answer “Y” to all of above, 就快来湾区实施吧！有点意志力和决心就能改变命运（如果你喜欢程序员的命运的话），快来和我们抢饭碗吧！

今天上班的时候，一个旁边组的中国男生给我发了一条信息，让我写他的peer review（promotion的时候要用）。这个promotion cycle其实早就开始了，他今天忽然找我，信息原话是这样的：

“说到这个还想让你写review呢。之前没想起你因为你修为相对较低说话分量可能不是最重的，不过manager说还是该加上。你意下如何？周四截止好像”

我泪奔。大哥你跟我一个级别好么！！！有这样求人帮忙的吗！！我们很熟吗？还有，什么叫“修为”？What year are you from, 1846? So I replied:

“哈哈哈，这是我听过最屌的求人帮忙的开场白了 – ‘I didn’t ask you because you are such a low lever I didn’t thought what you said would matter, but my manager insist, so .. whatever’ – How can anybody resist that temptation?”

二十分钟后，他回复：

“多谢多谢，详细描述下我有多靠谱。改天当面再谢”

。。。

您是Sheldon吗？我的irony这么明显还看不出来么？？这是神马情商？？FYI，这货从来没有开过玩笑，也不会开玩笑，so it’s not me reading too much into it. 唉，以前最讨厌别人说“中国人在美国公司都有glass ceiling”之类的负能量的话，但是今天我信了。。

最近几乎每天都有读者加我微信（能交很多朋友很开心），但是发现大家问的问题都大同小异，于是还是在这写一个frequently asked question post好了，希望对大家有帮助。

* claim:我的回答完全是个人观点，出自我2013年年末面试的经验，现在已经2015，形势有可能已经完全不一样了（比如我当年leetcode才100题，现在都tm快200了，做题赶不上出题快啊）。所以仅供参考喔。还有就是，问题很多，我没法一下写完，最近会经常更新。

• Q: 设计题怎么准备（几乎人人都问这个）？
  • A: 你是校招吗？校招不怎么考设计题，也就考点OO design之类的，就算考工业的system design要求也不高，不用太担心。如果不是校招，请开始担心吧。。。LinkedIn & Facebook专卡设计题，因为算法全民刷，拉不开距离；Google和其他大公司也必考。解决方法？平时上班自己多design，写一些design doc，然后从mitbbs上找点design的面经题自己试着想想，没有答案就找大牛同事同学给做一下。看看他们怎么design了，就知道套路了，面试时不至于完全尴尬的站在那一句话也说不出。。平时看看一些大公司的technology blog/video，比如amazon aws是怎么运作的，当然估计刷题都刷不过来肯定没时间看那个。。对了，还有Map Reduce必须会。总之还是积累+运气了。
• Q: Leetcode要刷几遍？
  • A: 刷到会做为止。对于用心的人是一遍，大部分人是两遍，还有没记性的同学那就刷吧。。有个好的reference，就是想面Facebook之类的专考leetcode的公司，那么中档题（不是难题！）最好能15分钟bug free。这个猛一看有点夸张，但实际上第二遍就经常会达到这个境界了。加油！
• Q: 除了leetcode，算法还要看别的吗？
  • A: 有空就看看别的（推荐CC150），没空的话，我觉得leetcode也够了。其他top coder之类的，可以刷完leetcode，凭感觉再决定看不看。一下给自己找太多材料，强迫自己都做完，精神压力就太大了喔。
• Q: 我做了题，第二天就忘光光怎么办？
  • A: 我也是啊！所以我才开了个博么。别因此丧失信心，it happens to every one！最后的赢家是坚持下来的人，不是自暴自弃的”靠反正也记不住老子不做了“的人。
• Q: 准备面试要多长时间？
  • A: 学生的话，每天有大把时间，可以一个月突击。工作的人，只能周末刷刷题，战线就可能拖上好几个月。所以别听说谁谁谁刷了一个月就进Google了你刷了仨月也没个onsite就绝望了，因人的环境而异。不过也有人不上心，做题不太理解就混混过去了，那样的就要刷好多遍才能长记性，就要半年。。
• Q: 我gpa低咋办？
  • A: 别往简历上写就行！面试全过程GPA完全是不透明的，直到你拿到offer签约的时候对方才要你的成绩单，这时候给就行了，就算你2.8反正offer都拿到了人家也不能反悔了。
• Q: 我是EE（或者是生物，金融，会计。。）转CS，有救吗？
  • A: 只要能拿到面试，那就都是考算法，都一样。认识无数非CS出身拿到好公司offer的。现在只有CS最好找工作，满世界都是和CS抢饭碗的，所以相信我，你不是一个人在战斗。I understand，你不懂OS，compiler, networks, database，一想自己啥也不会就totally overwhelmed觉得艹还不如嫁了算了 – I felt the same way before；那也没事儿，我也见过不少只会algorithm的拿到好offer。我现在还认识好多Google的中国人不知道什么是system call呢。刷好leetcode，你和cs出身的人面对同等的机会。
• 下次再整理更多questions，或者你有想问的问题并且懒得加我微信，在下面留言我会整理到这篇回答。Thanks!

最近搬家，发现自己各种utility late fee，然后没想起来提前30天通知land lord，罚了$2000的lease termination fee，另外relocation也是弄得各种紧张，还有三天就要被撵出去了还没找到新的住处，然后又是各种罚钱，以及浪费Google给的relocation benefit。

另外天天上班迟到，和搬家公司约好时间却睡过头，在craigslist上约好别人来买家具结果忘了，然后被发邮件咒traffic accident。

昨天在回家的十字路口仰天长啸——我为什么是这么个不负责任的人？？

Is it just me? 我tmd自从来美国，交了不知多少罚款了，每次都是掏钱息事宁人，然后难受一晚上第二天就忘光了。Also, I’m bad at negotiation，一要跟人argue我就浑身难受，usually just choose to settle just to make ppl like me. Will it ever change? If so, what can I do to change? 

I feel like 12 or something. Totally irresponsible. And I sometimes cry at confrontation.

I’m open to suggestion..

我惊讶又欣喜的发现，自己这个blog每天都有几百流量，而且很多人都会点击主页。于是我想继续写下去，尽管面试结束了，但是接着update更好的leetcode solution，并且记下自己的学习过程。我想，当你看多了算法，烦的不行的时候，翻翻别人的日记也挺有意思的，是不是？

今天花时间读了Sheryl Sandberg的Lean In: Woman, Work and the Will to Lead，惊讶的发现我的很多缺点原来是女性共有的，不是我一个人的错。比如每次我小有成就的时候，短暂的兴奋之后，随之而来的百分之百是恐慌。How can I perform (note: perform, not “excel”) on that level ? I’m a fraud, I don’t deserve this and oh my god they will get on me and what do I do?? 这种情形apply to every scenario，无论是被好学校录取还是被好公司录取，我的结论永远是”Well I got lucky”. “I studied hard even though I’m not talented”. And most ridiculously – “I’m pretty and the interviewer likes me.” 当Google打电话说feedback very positive的时候，我的第一句话是”Seriously?”；当公司说明target bonus指的是perform average的员工能拿到的奖金的时候，我理所当然的认为自己会perform below average，所以对自己的年薪期待也低了一万；当男性applicant都在argue offer的时候，我尽管安排了别的公司的面试为了拿counter offer好negotiate，但是居然两个晚上做梦希望自己挂了另一个公司的面试，这样就不至于要跟Google argue——我何德何能，拿到offer就已经是奇迹了，还敢argue??argue没了怎么办？人家生气了不要我了怎么办？少挣几万块钱买个踏实吧还是。。

Sheryl在书里解释，这是大部分女性都有的想法。她们不会把成功归功于自己的聪明才智，而是“擦了一把汗，尼玛太幸运了又忽悠住别人一回”的心态。男性从小被鼓励有自信，女性却很少被鼓励。Confident boys are shining stars, confident girls are shameless and annoying and probably ugly（检讨一下，我从小没少在背地里嘲笑有自信的女生）。在书中的例子里面，Sheryl和Mike考同一门课，男生平时不怎么学习，期末狂cram，然后考场出来女生觉得自己答的糟透了，男生则手舞足蹈必须A。结果是两个人都是A，但是对自己的perception截然不同，结果就是女生多了好几天的自我怀疑和煎熬。This exactly what I experience all the time. 我回忆自己长大的过程，很少有什么是让我非常自信的。我在现在这家公司工作，不自信到老板特地给我请了别的department出名自信的女员工给我辅导心理问题（不是技术问题，是心理问题啊啊），都奇葩了。就连刷leetcode的时候也是，很多时候觉得“这哪是人类能做出来的呢？”“我数学最差了，现在学计算机就体现出来基本功不行了”然后上升到“我就是不行。天生不行。北大清华出来的学霸一抓一大把，哪能轮到我呢？我永远也找不到工作。我现在在公司表现也不好。没准马上就要被fire掉了。我就快走投无路了”。然后大部分时间花在worry about what I can’t do上，真是关于做题的没想多少。

If you are reading this, and you have at some point feel the same, what will you do to change it?

我想，接着写这个博客就是对自己的自信的锻炼and this is what I’m doing to change it。你见过校内那种写一篇有点争议的文章下面几百条对骂回复的吗？要我说，it takes courage to show your opinions. 尤其我的心智本身也很幼稚，我做题也一般，还胆敢在网上公开发表自己的想法和算法，也算等着被嘲笑吧（你看我对自己的认知是多么谦卑自贱！写完我才发现这都成习惯了！）。谢谢你花时间读这篇文章，你的点击和回复都在帮我的自信心成长！

不知道怎的，回家反而没那么高兴了。我就是有毛病——两年前拿到现在这个大公司offer的时候也没高兴起来，尽管之前的半年都快为工作愁死了。几个月的付出，最后有了最最完美的结果——Google is no question my fav company！为什么还是情绪低落？？？I can do everything!!

Damn, I’ll wash dishes and go to sleep. I’ll think about it tomorrow.