漫谈LeetCode解题思路
之所以想要写这篇博文是因为前几天面试了一个女博士, 名校毕业, 简历上有你想要的所有关键字, 什么Java, 什么Angular, 什么Jenkins, 什么Big Data, blabla一大堆, 又会说五门语言, 我自己说四门语言我都觉得再多我就会记串吧的。 面试之前CTO和CEO对她的背景都很满意, 我和另外一个同事看到这份简历也唏嘘不已, 一份5页纸, 写的满满当当的简历, 让人自叹弗如。 我深感惭愧, 我自己博士这三年光顾着玩了, 虽然玩着玩着也发了TKDE(让我嘚瑟一下~~), 也发了很多好会的论文, 也写了一个Semantic Web流处理的Engine。 不过比起 这份简历来, 我的简历就逊色多了。 后来还是同事工作多年, 经验比我丰富, 他跟我说, 这个人的真实水平不一定会很好, 因为她只提到了技术, 并没有提到她是如何应用这些技术的。
心里带着些许疑虑, 我们就开始了对她的面试。 一开始听她介绍她博士的工作, 说的天花乱坠, 我心里越来越胆怯, 对于这么”厉害”的一个牛人, 我准备的面试题会不会太简单了, 被鄙视呢? 无所谓了, 实在不行我还可以拿大数据当follow up, 回到我的老本行, 应该就是我的主场了吧。 所以我还是壮着胆子问她: 我们今天的面试题很简单, 能不能请你将一个字符串中的所有元音字母颠倒顺序呢?
她开始一点点失去了一开始的从容, 在白板上吭哧了半天之后, 她说她Java用的不熟。 同事赶紧打圆场, 没关系的, 你先说说你的思路, Java的哪个用法想不起来了我们来提示你。 她的额角开始冒汗了, 又面壁在白板上画了一些不知道啥, 然后小声说: 对不起我没有思路, 能不能给我一些 hints? 好啊。我说。人都有紧张的时候嘛, 说不定她一紧张就没思路了, 也是正常。 于是, 我拿出我”多天”刷题总结的思路, 引导她: 假设这个字符串是”aeiou”, 你要怎么办? 她又开始吭叽了, 神马Bubble Sort都给我上来了? 打量我书读的少没文化是怎么的…… 不过我可能确实书读的少, 我还第一次听说要用Sort来reverse一个字符串。 不过不要急着否定人家嘛, 最好让她自己发现问题, 更何况本来很简单的问题, 她自己给自己设了个坎, 我在一旁看热闹, 何乐而不为呢(啊吼吼吼)? 她的汗越来越多, 和白板相面很久之后, 她说: 对不起, 我忘了Bubble Sort怎么实现了。 这回换我不淡定了, 你确定你是博士生嘛? 我记得我们学校连本科生都要求会写Merge Sort和Quick Sort的!
后来的过程变得不重要了, 只是面试结束之后我和我的同事都很不高兴。 先不说能力怎么样, 我觉得这个人做人有问题, 吹的那么厉害, 到头来连reverse 字符串都不会, 是不是有点浪费大家感情和时间呢?
所以, 给想要面试的同学的第一条建议就是:
- CV要诚实! 不会的东西不要写在CV上! 不熟的东西不要吹的一幅Google创始人来微服私访的样子! 这样给人感觉真的非常不好。
永远都不要为了把自己”卖”掉而过度包装, 或者造假, 因为迟早要露馅。 在找工作这条路上没有捷径可走, 因为谁都不瞎, 谁都不是傻子, 面试官往往比你有经验的多, 与其想办法去包装自己, 不如好好去提升自己。
另外, 不管是面dev的职位还是面R&D的职位, 都请先准备好了再进行面试, 这是你指望养家糊口的工作, 你不上心人家为什么要招你? 基本功都没练好就去面试, 是一种非常不礼貌的行为。 这样的人如果遇到一次, 就永远会被我拉到黑名单里, 首先三观就不正。
那怎么准备呢? LeetCode那么多题, 盲目的刷总觉得像黑瞎子掰苞米, 最后真正沉淀下来变成自己的东西非常少。 所以, 我的第二条建议是:
- 总结点题型, 记点Templates
其实编程面试远没有你想象的那么难, 一般的公司无非就是问问数组字符串这类小题, 大一点的公司像某G啊, 某A啊, 喜欢问些图相关的问题。 这些问题说难也难, 说简单也简单, 因为其实他们都是有套路的。
看看LeetCode的标签, 无非就是Binary Search, Two Pointers, Sort, Dynamic Programming, Backtracing, Graph, Tree etc. 每类题先搞明白一道, 记一个解题套路, 实在搞不明白就背一个Templates, 遇到类似的问题就往上套。 比如前文说到的那道面试题, 就是典型的两个指针问题, 虽然有点变化, 但是万变不离其宗, 我想如果你想到两个指针那么这道题就解决一半了。 接下来想想, 两个指针最重要的步骤是什么? 无非就是(1)指针怎么往中间走 (2)什么时候调换指针指的值。齐活了。
真正难的是那些没有套路的问题。 比如下面这道问题:
这道题希望我们能设计一个数据结构, 来实现插入删除和随机接入都是O(1)。 乍一看好像很简单, 细想想, 咦, 好像不对劲儿。 再想想, 完了, 焦头烂额了。 我的下一条建议是:
- 一步一步Tackle问题, 锻炼自己的解题思路。
其实刷题都是其次, 锻炼自己解决问题的思路才是最重要的, 因为在日常工作中, 没有套路可寻, 每一个突破, 每一个功能的实现, 都需要你自己动脑筋想解决方案, 判断解决方案是不是最优, 测试解决方案的鲁棒性, 等等。 那么遇到一个问题, 或者想实现一个东西的时候, 如何入手呢? 这不是你拍脑门就能 想出来的, 这需要你平时养成好的思考习惯, 不断的锻炼你的思维能力, 还有在工作中不断的积累经验。 刷题就是一个积累经验的过程。 它把用户想实现的东西以题这种更具象的东西呈现在你面前, 你每次刷题的思考, 其实都是在为你自己将来积累经验。 我听到过很多人跟我说, Java我看了很久, 我熟悉Java的 用法, 可是我为什么就不能用Java实现我的想法呢? 原因很简单, 经验不够, 代码写太少了, 通常这种时候我的建议就是: 要么回家刷题, 要么辞职别干了 — 你痛苦, 你同事有你这么个猪队友比你还痛苦。
我觉得好的思考方式就是大问题化小问题, 把能解决的部分先解决了, 剩下的部分看看能不能有什么其他方法补漏。
拿这道题为例, 如果单纯让你Insert Delete是O(1)那很容易, HashMap就解决了; 如果单纯让你getRandom()是O(1), 那也很容易, ArrayList也能解决。问题在于怎么把两个combine在一起。 想到以上这步并不难, 而且想到这里, 这道题其实也就解决了。HashMap的缺点在于不能random get, 那就让random get 的功能由ArrayList来辅助实现, 但是ArrayList不能Insert Delete是O(1), 退而求其次, 如果每次都在ArrayList的尾部add或者remove就能变成O(1)了。 嗯, 又近了一步。 可是问题是我每次想删除的元素不一定就在ArrayList的尾部啊!! 要不把它换到尾部去吧, 对, 就这么办, 把它和尾部的元素对调。 但是如果对调, 我需要知道这个元素在ArrayList中的位置, 对了, 我不是有个HashMap嘛, 让HashMap的key是我想插入的元素, value是这个元素在ArrayList中的位置不就得了!!! 问题解决了。老规矩, 完整代码在这里。
我还想再强调一遍, 养成一个良好的思考习惯真的非常重要, 如果你现在没有, 那么请你一定从现在开始培养! 要找工作的同学, 都是刚刚毕业, 或者即将毕业的学生, 你们还很年轻, 以后的路很长, 养成一个好的思考习惯对以后的路都很有帮助。 不然只能每天耗在那里, 时间也浪费掉了, 然后还抱怨: 我也学了啊, 我也工作了啊, 为什么别人都有成绩, 我没有?
因为别人过脑子了, 而你没有。
不要让自己的大脑称为别人思想的跑马场, 不要去重复别人的观点, 不要人云亦云, 养成独立思考的好习惯。 这个过程不会很简单, 就像人长肌肉的过程一样, 每次练肌肉一定都是对自己的极限的一次挑战, 要流汗, 要经历撑不住了还得硬撑的时候, 因为只有这样, 肌肉才能生长。
So, for your own good, train your brain just like train your muscle!
P.S.最后这篇文章可能有点跑题, 没有说到太多具体的解题思路, 但是我觉得我已经说的足够多了, 剩下的只能由你自己想了。