Coursera: Algorithms, Part I: Interview questions week 1

Coursera上Robert Sedgewick的算法课本周开始了,第一周的课是并查集和基本的算法分析方法,大概听了下,一个让我有点感兴趣的地方是有一张ppt里列了并查集的具体应用,里面有一些是我没听说过但是看上去又比较好玩的,不过都被一带而过了。有一个比较有趣的栏目叫Job Interview Questions,题目还不错,不计分,点提交按钮可以看到简略的提示。在这里把我觉得有意思的题目做一下,给我这个blog添些文章充数。

Inverview Questions: Union-Find

3.给定集合S={0,1,…,N-1},有两种操作:
(a)从集合中删除一个给定的数x
(b)求给定的数y的后继,即集合里比y大的最小的数
要求所有操作都是对数时间或更低。

答:如果不是因为出现在这一课,我觉得还是有点不好想的。可以把每个存在的数和比它小的连续的若干被删除的数看作一个集合(如果用X表示被删除的数,这个序列是类似OXOXXXOO的形式,集合为{O}{XO}{XXXO}{O})删除x就是把x所在的集合和x+1所在的集合合并,注意要对每个集合记录一个标记,表示该集合里没被删除的那个数,合并两个集合时把标记更新为较大的那个。查询操作就是得到y+1所在的集合的标记。复杂度就是并查集操作的复杂度。

4. 如果Union操作时是按照树的高度进行合并(让高度大的树的根作为合并后的树的根),证明对N个结点的操作得到的树的高度上界是lgN

答:用归纳法证明:高度为x(只有叶子的树高度为0)的树至少包含2^x个结点。高度为0时显然成立。设高度不超过k时成立,若两树合并后高度比两树都大,只有当两树高度均为k时,合并得到高为k+1的树,此时结点数不小于2^k + 2^k = 2^(k+1),得证。

ps. 在视频里证明了如果是按照树的结点数进行合并,高度上界也是lgN。证法比归纳法更巧妙:考虑结点a距离树根的距离,如果这个距离增加,说明a所在的树被接在了另一棵树上,因为是按结点数合并,另一棵树的结点数不少于a原来在的树,合并后的结点数至少double。因为一共N个结点,这种double最多只能进行lgN次,得证。

Inverview Questions: Analysis of Algorithms

2. 在bitonic array里查找一个数。所谓bitonic array是指一个先递增后递减的序列,没有重复元素。要求比较次数最坏大约是3lgN

答:先用三分搜索找到最大值(每次比较把区间缩小到原来的2/3,算了一下大概要1.7lgN次比较)。再在两个序列里分别进行二分搜索(2lgN)。

3. 从楼上扔鸡蛋问题的各种版本:共有N层楼,鸡蛋从第T层扔下摔不坏,在第T+1层扔下会摔坏,想找出这个T值。在各种鸡蛋数和扔的次数的限制下的策略。
a. 1个鸡蛋,<= N次扔
b. ~lgN个鸡蛋,~lgN次扔
c. ~lgT个鸡蛋,~2lgT次扔
d. 2个鸡蛋,~2sqrt(N)次扔
e. 2个鸡蛋,<=c*sqrt(T)次扔, c是固定常数

答:a. 一个鸡蛋从低层向高层依次扔,直到摔坏
b. 二分查找。先试N/2,如果摔坏了,就试N/4,否则试3N/4。要试约lgN次,最坏情况下摔坏约lgN个鸡蛋
c. 以1,2,4,8…倍增的间距从低层向高层扔,即从1,3,7,15…层逐次向下扔,直到摔坏。设扔了k次后摔坏,此时的间距x=2^k满足 1+2+4+…+2^k = 2^(k+1) – 1 >= T,所以k约为lgT,定位出一个不超过2T的区间。在此区间内二分查找,最坏摔坏lgT个鸡蛋,此步又需要扔lgT次。一共约摔坏lgT个鸡蛋,扔2lgT次。
d. 以约sqrt(N)为间距从低层向高层扔,直到摔坏,最坏情况约扔sqrt(N)次,可以确定一个约为sqrt(N)的楼层区间,在这个区间里用第二个鸡蛋从低向高逐层扔,直到摔坏,最坏情况约再扔sqrt(N)次。
e. 以1,2,3,4…递增的间距从低层向高层扔,直到摔坏,此时的间距x满足1+2+…+x = (x^2 + x) / 2 >= T,所以x约为sqrt(T),这一步扔了约sqrt(T)次。再在这个大小为x的区间内逐层扔,最坏约再扔sqrt(T)次。

  1. Good problem!
    可以拿来面试别人了-,-

  2. :lol: 我也在跟这个课程,当然部分原因是看到Robert Sedgewick,顺带当复习下算法~

  3. 感觉Union-Find问题3用双向链表挺好做的?

  4. Analysis of Algorithms 的第二题不能用三分 因为是单峰 但不是凸函数, 二分 每次比较相邻的数是递增还是递减

  5. I have noticed you don’t monetize your website, don’t waste your traffic,
    you can earn extra bucks every month because you’ve got high quality content.
    If you want to know how to make extra money,
    search for: best adsense alternative Wrastain’s tools

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>