一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 6945|回复: 47
收起左侧

[算法题] 面试准备关键在于掌握方法,而不是刷题(干货版)

  [复制链接] |试试Instant~ |关注本帖
geniusroger2000 发表于 2015-4-9 13:31:49 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
上篇文章因为给新写的书打了广告,给版主封了。我理解和支持版主的工作,所以这篇只谈方法,只讲事实。

之前帮优秀的版友内推,也顺便结识了不少朋友,回答了一些大家的疑问。一个普遍的问题是:我cc150刷了两遍,leetcode刷了两遍,算准备好了么?还应该做什么题目?去看看EPI?是啊,其实我自己也在想,怎么样做题算是“够了”?就和准备高考一样,3年模拟题做完做5年的?本地的做完了做全国的?

我高中参加数学竞赛,然后得奖保送北大。那时具体的题目、公式都忘得差不多了,但学到了一点终生受益:要把做过的题目联系起来,然后总结方法。寻求为什么这么做,而不是怎么做。否则,不通过举一反三,而寄希望于在考试/面试时出现做过的内容,那就真是“以有崖求无崖,殆哉矣”。这里,我只谈方法。给个实例:

大家可能都觉得,算法题中动态规划是比较麻烦的问题。但当你碰到这类问题时,仔细总结过方法么?考虑过题目为什么要用动态规划么?动归和递归的区别在哪里?
我觉得,从子问题解决原问题, 无非是两种方法,自底向上(Bottom-Up)与自顶向下(Top-Down),形式上前者对应iteration,利用循环将结果存在数组里,从数组起始位置向后计算;后者对应recursion,即利用函数调用自身实现,如果不储存上一个状态的解,则为递归,否则就是DP。举个斐波那契数列(0,1,1,2,3,5…)的例子:
1) 自底向上
int array[n] = {0};
array[1] = 1;
for (int i = 2; i < n; i++)
    array = array[i-1] + array[i-2];

事实上,额外空间可以进一步缩小到O(1):利用几个变量记录之前的状态即可。由于记录了子问题的解,故给出的方法就是DP。事实上,自底向上的方式往往都是通过动态规划实现。

2) 自顶向下
int Fibonacci(int n)
{
    if(n == 0)
        return 0;
    if(n == 1)
        return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

为计算Fibonacci的第n个元素,我们先自顶向下地计算子问题:第n-1个元素和第n-2个元素。由于没有储存子问题的运算结果,给出的方法是递归。然而,Fibonacci(n-1)与Fibonacci(n-2)包含很多重复的子问题,所以DP效率更高。如果用一个全局数组,将子问题的解储存到数组的对应位置,在重复计算的时候直接读取计算结果,那么就是DP的解法。

动态规划的核心在于,如果通往一个问题的solution,subproblem被重复计算,那么就可以利用记录中间结果,达到用空间换取时间的目的。在递归过程中用hash table记录中间计算结果的DP,称作Memoization。

Memoization的一般形式是: 建立以input为key,以output为value的hash table:
T func(N node, HashTable<N, T>& cache) {
    If (cache.contains(node)) {
        return cache.get(node);
    }
    …
    T sub_res = func(next_node, cache);
    …
    T res = G( sub_res … );  //当前子问题的解,依赖于更小的子问题(s)
    cache.set(node, res);
    return res;
}

从解决问题的角度来说,用Bottom-Up的DP,固然通常可以节省递归本身的空间开销,但有很多缺点和局限:较难理解,边界条件较难处理,只适用于问题的节点空间是离散的整数空间,必须一步步邻接、连续地计算(无论是不是每一个节点的结果都会被用到)。而Memoization,则灵活得多:可以从递归形式轻易修改得到,也更符合普遍的思维过程,并且没有上面说的这些局限,子问题只有在被需要的时候才会被计算。尤其是在某些情况下,不仅需要aggregate的结果,还需要获得achieve这个结果的路径,这时候就算用Bottom-Up的DP,也需要记录prev节点,最后需要递归回溯得到路径,那么节省递归空间开销的优势,也荡然无存了。

那么Bottom-Up的DP可以解决哪类问题?我说,DP适用于解决“收敛结构问题”。所谓的“收敛结构问题”是指关于特解,或数量的问题(例如,第n个元素,第n步有多少种方法等)。这些问题都可以用整数坐标映射所有节点(即DP状态),且当前节点的解只依赖于前驱节点(无论是顺序还是倒序)。那么,这类问题往往可以用DP解决。解决的关键是建立subproblem的解之间的递推关系:
f(n) = G[f(n-1), f(n-2), … , f(1)] 或
f(i, j) = G[f(i-1, j-1), f(i, j -1), f(i-1,j)]
其中G[ ]表示子问题到原问题的映射关系,例如对于斐波那契数列,有递推式:
f(n) = G[f(n-1), f(n-2)] = f(n-1) + f(n-2)

但如果出现类似于“所有解”,“所有路径”等关键词,则用Top-down方法更为直接。

举一道简单的题目: Suppose we have a ladder which has n steps. Each time you can either climb 1 or 2 steps. Please write a function to calculate how many distinct ways that can you climb to the top?

解题分析:本问题描述了一个数量问题,属于前述的强收敛(聚合)性问题,可以用DP。DP的核心在于递推关系:当前节点的值可以由前驱走一步到达,或者前前驱走两步到达,即CountOfWays(n) = CountOfWays(n–1) + CountOfWays(n-2);由于当前节点只与紧邻的两个节点决定,所以只需要2个临时变量来表示前驱节点的解即可,而不用DP table,因为更老的解我们不需要关心。在实现时,往往边界条件直接用if…then return value的形式,成为递归的出口。

因此,当理解到了一定的深度,真不是特别在乎做了多少题目。与之相关的另一个问题是,准备周期得有多长?这里,我只谈事实。看过我之前文章的朋友也知道,我本来是考虑转博的,但后来打算直接工作。我那时一月底开始准备,二月底投简历,到四月底一共onsite了12家公司拿了10个offer。不否认我的基础还算不错,科研也和软件相关,但也不算科班出身,硕士是ECE(在面试google的时候也暴露了CS知识面不够广的问题,所以G家也是我唯一技术上没过的公司)。
但是,我们准备的时候极其认真,效率远远超过现在工作。特别是他为了节约时间,一天只吃固定东西:中午越南粉,晚上Jack in the box或者互换。谈事实的目的就是,如果真正投入加仔细思考方法,几个月搞定心仪的工作也不是不可能。就看你理解的有多深。
大家可以比较下思考的深度。他笔记里的思想后来成了我们书的原型。

只练不想还有两个问题:
1. 看到类似的题目就硬套方法。当面试官要求换个思路时会感觉很困难
2. 看到没见过的题目有时就会慌,结果连正常水平也没发挥出来。

总而言之,希望大家能换个方向看刷题,与其做上两遍,三遍,不如花相同的时间认真总结下适合自己的方法。



评分

13

查看全部评分

zhuli19901106 发表于 2015-7-21 22:04:10 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-21 22:06 编辑

看完此帖觉得作者在气度上更胜一筹,不过两位都是大神。
从另一位老兄身上可以很合理地解释为什么硅谷的华人干不过印度人:竞赛出身,实力超群,但做人太孤傲,典型的不团结。书可以不买,但不能干涉别人写的权利吧。再比如我代码写得烂,岂不是没资格开博客,注册github?我长得丑,也不能禁止我上街啊。是这个理吧?
回复 支持 4 反对 0

使用道具 举报

gbbbb 发表于 2015-4-9 20:48:09 | 显示全部楼层
本帖最后由 gbbbb 于 2015-4-9 20:49 编辑

楼主标题的结论正确。
但是楼主对DP的理解确实不像是科班出身的,描述非常不严谨,漏洞很多,非常不建议楼主去写技术相关的书籍,可以预见的是写出来的书水平也不见得会多高,建议楼主先去多阅读一些经典的算法教材,刷一些较高难度的算法题。

只要有一定的学习能力,大部分人学习算法也不会单一的刷题背代码套公式吧,除非是临时抱佛脚那也没有办法。算法题说到底还是一些题,都是一些套路,用初高中学习解题方法的那一套,不断刷题总结就是了。各种OJ/TOPCODER都是很好的刷题材料,把一套题刷几遍才是无意义的事情。
回复 支持 2 反对 1

使用道具 举报

gbbbb 发表于 2015-4-11 02:02:09 | 显示全部楼层
“那么Bottom-Up的DP可以解决哪类问题?我说,DP适用于解决“收敛结构问题”。”  看了这句就知道楼主水平有限。

1. 连规范的学术用语都不清楚。维基百科对DP的描述原文是It is applicable to problems exhibiting the properties of overlapping subproblems and optimal substructure。 这两个名词,尤其是后者“最优子结构”在任何一本描述DP的无论中英文教科书都会出现。你用自己编出来的名词在面试的时候去解释问题,会让人觉得非常业余。
2. 楼主对于DP的通篇解释表明了自己对于optimal substructure这个名词本身的理解程度不够。http://www.zhihu.com/question/23995189 这个问题下的高票回答比楼主的解释要靠谱的多。

楼主这个水平去写书,恐怕还是误人子弟的多。总结经验没有错,随便用搜索引擎一搜就可以搜到各种前人的经验,在互联网这个自由的平台谁都有发表意见的权利,但是写成书的意义的就完全不一样了。
回复 支持 1 反对 1

使用道具 举报

zhuli19901106 发表于 2015-9-25 03:18:16 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-9-25 03:19 编辑
hanrui_542 发表于 2015-9-25 00:07
真的是这样的,见过算法题做的好的人都怪怪的。楼主算是balanced。

你见到的那些怪怪的家伙,一方面他们在专业上是专注的,另一方面他们在做人上是狭隘的。
觉得不和他们搞同样东西的人,统统都是傻叉。
所以总是一副自以为是的样子。

当正常人碰见一个情商很低的高手码农,态度基本是这样的:
1. 你不认识他时,觉得他真土,又呆又傻的(区别于呆萌)
2. 你认识他以后,发现他不但土,而且还招人讨厌(区别于高冷)
3. 后来你才知道,原来他是某牛校计算机系的/某比赛金牌/超级学霸/XXX的弟子,好厉害(真的很牛)
4. 你转念一想,那又怎么样,这么个傻叉牛不牛跟我有什么关系

所以你碰见的那些怪家伙,不但没什么朋友,一般也没女朋友。
Have mercy on them.
希望我的回复能帮你更好理解那些高手是怎么回事。以后你再碰见这种人,不要被他们搞坏心情就OK啦。
回复 支持 1 反对 0

使用道具 举报

stellari 发表于 2015-4-9 16:41:20 | 显示全部楼层
我觉得吧,现在我看到的书,比如CC150和Leetcode的Clean Code Handbook。它们的共同特点是题目为导向的,也就是更倾向于给出题目,然后给出本题的解法。但是并无太详细的归纳,后者更是如此。CC150做题前有一些总结,但是还是略显简单了些。另外,对于一些很常见的方法,就比如binary Search,听起来简单,但是很多人都未必能一次写对:例如退出条件应该是i <= j还是 i < j? mid < target时应该是i = mid还是i = mid+1?再比如链表问题,也经常容易犯off by one的错误,有没有什么办法可以规避?大部分书里只是给了一些示例代码,并没有总结这些问题。而且现在大家都在刷CC150和Leetcode。去年初Leetcode上一道题的总提交量不过3万左右,现在已经暴涨到了20万。相信很多面试官也知道这个情况,而特意避开这些题目。

所以,我觉得如果楼主的书,或者任何一本书,能够在三点上多下功夫,我会比较支持的:

1. 解题的一般方法的总结;
2. 某一类题的实现方法的模板;
3. 与CC150和Leetcode上重复率不高的题库。

我个人比较支持总结类的书籍
回复 支持 1 反对 0

使用道具 举报

cleverley 发表于 2015-4-9 13:39:32 | 显示全部楼层
lz这种是竞赛参加多了,我觉得对平凡人,没那么多讲究。熟能生巧。总结要总结,没比亚想那么复杂,刷的多了自然就会了。话说回来,刷不到两三遍,也总结不出什么东西来
回复 支持 1 反对 0

使用道具 举报

Hsieh 发表于 2015-4-9 13:44:25 | 显示全部楼层
说来说去还是来卖书了。。。真不觉得你们这本书能比CC150好
回复 支持 反对

使用道具 举报

Deckardmzr 发表于 2015-4-9 14:14:24 | 显示全部楼层
支持一下段公子,我觉得段公子的视频系列还是很实在的,看了对我这个转cs的很有帮助,能打开思路反正,而且是免费的不像九章还要交钱……

书的话这个完全自愿的吧,leetcode也出书了,买不买也是看你自己的需要
回复 支持 反对

使用道具 举报

miss_snow 发表于 2015-4-9 15:36:57 | 显示全部楼层
斐波那契还可以
1.矩阵+快速幂
2.直接套公式
我就是路过的……
回复 支持 反对

使用道具 举报

gbbbb 发表于 2015-4-9 20:53:03 | 显示全部楼层
stellari 发表于 2015-4-9 16:41
我觉得吧,现在我看到的书,比如CC150和Leetcode的Clean Code Handbook。它们的共同特点是题目为导向的,也 ...

总结类的书籍没有多少意义,自己总结的干货才是真的干货。一次写不对的原因是算法没有想清楚,写的慢的原因是写的少。刷题要多刷新题,多写多练,盯着一套题库刷熟练度没有任何意义。
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-4-9 21:46:55 | 显示全部楼层
有幸受过smilence的一些帮助和教导。
回复 支持 反对

使用道具 举报

z928czzc 发表于 2015-4-9 22:03:08 | 显示全部楼层
Fibonacci 是log n 算法,DP不是best solution...
回复 支持 反对

使用道具 举报

 楼主| geniusroger2000 发表于 2015-4-9 23:33:34 | 显示全部楼层
z928czzc 发表于 2015-4-9 22:03
Fibonacci 是log n 算法,DP不是best solution...

并没有说DP是Fibonacci的最好方法啊。。正如楼上说的,还能以O(1)直接套公式。这里只是举个常见、大家都能看懂的栗子,说明一些DP的想法而已
回复 支持 反对

使用道具 举报

nibuxing 发表于 2015-4-9 23:39:05 | 显示全部楼层
geniusroger2000 发表于 2015-4-9 23:33
并没有说DP是Fibonacci的最好方法啊。。正如楼上说的,还能以O(1)直接套公式。这里只是举个常见、大家 ...

怎么能搜到你这本书
回复 支持 反对

使用道具 举报

 楼主| geniusroger2000 发表于 2015-4-9 23:46:59 | 显示全部楼层
gbbbb 发表于 2015-4-9 20:48
楼主标题的结论正确。
但是楼主对DP的理解确实不像是科班出身的,描述非常不严谨,漏洞很多,非常不建议楼 ...

总结不同于你所说的算法教材。教材需要从公式理论开始推导,用词必须精准。总结更多是传达理解和技巧。其区别就像红宝书和美氏字典,红宝书可以告诉你ambulance可以记为"俺不能死",字典里则不能。但是,哪怕看得是教材,最后记住的也不是公式推导,而是形象化的理解。总结的目的在于:在看过教材理论之后,帮助建立理解。所以,语言风格上的差异源自于出发点不同,但如果有错误,那就是水平问题,还请指出 共同进步 :)
回复 支持 反对

使用道具 举报

窗外一棵树 发表于 2015-4-10 07:26:56 | 显示全部楼层
Deckardmzr 发表于 2015-4-9 14:14
支持一下段公子,我觉得段公子的视频系列还是很实在的,看了对我这个转cs的很有帮助,能打开思路反正,而且 ...

能否请问下视频在哪里能看到? 谢谢啦
回复 支持 反对

使用道具 举报

Deckardmzr 发表于 2015-4-10 08:48:23 | 显示全部楼层
窗外一棵树 发表于 2015-4-10 07:26
能否请问下视频在哪里能看到? 谢谢啦

https://www.youtube.com/watch?v=sMtiA5WE4Tg&list=PLdo-di5s83cuHXewaEimetebjMyz9P-jf

前三讲得加段公子的google账号才能看
回复 支持 反对

使用道具 举报

stellari 发表于 2015-4-10 08:50:13 | 显示全部楼层
gbbbb 发表于 2015-4-9 20:53
总结类的书籍没有多少意义,自己总结的干货才是真的干货。一次写不对的原因是算法没有想清楚,写的慢的原 ...

你说的这些我全部同意,我自己也是这样过来的。但是我认为这类书对于一些要求快速上手,并在短时间内掌握概念的同学还是有意义。作为非CS科班学生,我自己归纳的很多规则和经验是在不断试错中总结出来的。如果能够一开始得到这个先验知识,带着这个先验知识加上自己在刷题中体会,可能会避免一些弯路。另外我也乐于看到别人总结出来的经验,因为多少会和自己的有不同,这本身也是个提高的过程。

当然这套书如果只是讲一楼中的这个层次的内容的话,这个总结的程度对我(相信还有相当多的其他人)来说是远远不够的。所以我只能说纯支持了。
回复 支持 反对

使用道具 举报

 楼主| geniusroger2000 发表于 2015-4-10 09:47:27 | 显示全部楼层
stellari 发表于 2015-4-10 08:50
你说的这些我全部同意,我自己也是这样过来的。但是我认为这类书对于一些要求快速上手,并在短时间内掌握 ...

是的,说的很中肯
回复 支持 反对

使用道具 举报

geng77 发表于 2015-4-11 00:36:16 | 显示全部楼层
how can I buy your book??
回复 支持 反对

使用道具 举报

charmingpast 发表于 2015-4-11 03:55:37 | 显示全部楼层
本帖最后由 charmingpast 于 2015-4-11 04:00 编辑
gbbbb 发表于 2015-4-11 02:02
“那么Bottom-Up的DP可以解决哪类问题?我说,DP适用于解决“收敛结构问题”。”  看了这句就知道楼主水平 ...

我就想不清楚为什么这位同学这么强调科班出身。。。而对非科班出身的同学致力于CS的学习,鄙其没有学术规范。。当然仁兄不要生气,小女只谈想法。请问什么是科班出身?小女子也是CS科班出身,修过无数的算法,编程课,除了考试刷题,最后什么也没有记住,没有掌握融会贯通的技巧,相比之下GPA高的不得了。。。在学校,实习时认识了一些对计算机非常感兴趣的非科班出身的人,显然他们对计算机的理解让我敬佩,或许他们说不出什么高深的术语出来,但是思路却比我清晰多了。我想这些博客的出现,或者是给我一些参考,如果能帮助我最好,不能帮助到我自然会有很多其他网络资源。所以对于这些总结式的博客或者书籍,我还是持观望支持态度,毕竟太少。。

期待其提高,能帮助更多像我这样只有刷题,不懂融会贯通的人!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 23:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表