Monthly Archives: October 2012

Coursera: Algorithms, Part I: Week 5 & 6

最后两周的题目不多,所以写在一起吧。KD-Tree是一个对我来说比较不熟悉的东西,视频里没有讲一些关键复杂度的证明,但是这个东西给我的感觉不美……不过对于那样的问题也没有什么太好的办法了吧。还讲了一个线段组成的BST,不过功能上和ACMer常用的线段树相比真是弱爆了啊。

Inverview Questions:

2. 文档中依次有N个词,现在有一个依次包含M个词的检索串,要求在文档中找到一个包含最少词数的连续片段,使得检索串里的M个词依序出现在这个片段中(当然,可以不连续)。

答:首先遍历文档建立一个索引:对每个词,记录一个表示它在文档里出现的位置的列表。然后维护M个指针指向M个检索词对应的列表。向后移动相应指针得到第一个满足顺序要求的解(即M个指针指向的位置值是递增的且尽可能小),这样就找到了一个片段。继续向后移动指针找下一解,直至扫描完所有列表。建索引时如果借助hash表,复杂度就是O(N)。扫描的总复杂度也是O(N)。

Interview Questions: Hash Tables

1. 4-SUM: 给定一个长为N的数组a,要求找出不同的四个数满足a[i]+a[j]=a[k]+a[l]。要求时间复杂度是O(N^2)

答:枚举所有数对的和,用hash表判断是否出现重复即可。“下标不同”这个要求可能需要一点处理,不过我懒得想细节了……囧

(完)

Coursera: Algorithms, Part I: Week 4

前段时间事情较多,所以进度跟不上了,我会尽快把剩下的补完。

第四周的内容是优先队列和二叉搜索树。只记得最后提到,如果用普通的BST(非平衡的)进行随机的插入和删除,期望复杂度会是O(sqrt(N)),这个我之前倒是不知道,只知道故意构造的最坏情况会变成O(N)。已经不记得有什么其它的有趣的点了,直接看题目吧。

Interview Questions: Priority Queue

1. 设计一个表示动态集合的数据结构,使得插入元素是对数时间,查询中位数是常数时间,删除中位数是对数时间。

答:实际上我见过一道类似的ACM题。我们假定在集合中有偶数个元素时,中位数是指较小的那个中间数。用两个堆,一个大顶堆包含集合里较小的(N+1)/2个数,另一个小顶堆包含集合里较大的另一半数。查询中位数时,直接看大顶堆的堆顶元素即可。插入元素时,先将其与两个堆顶元素比较,以决定插入哪个堆。如果插入之后两堆的元素个数之差超过了1,就把多的那个堆的堆顶元素插入到另一堆里。删除元素时,将中位数删掉之后,同样调整两个堆的元素个数。

2. 设计一个优先队列,支持两种额外操作:随机访问队列里一个元素,随机删除队列里一个元素。

答:因为堆用连续的一段数组表示,随机访问只需要随机得到一个[0,N-1]之间的数组下标即可。随机删除元素和删除堆顶元素其实是一样的,把最后一个元素放到被删除的元素的位置,然后把它向下沉直到合适为止。

3. 找出所有的四元组(a,b,c,d),满足a^3+b^3=c^3+d^3 (a,b,c,d <= N)。要求O(N^2*logN)的时间,O(N)的空间。

答:先看另外一道很有趣的问题:给定两个排好序的数组A和B,两数组长度都为N,我们从两个数组各取一个元素求和,这样就得到了N^2个和,要求把这N^2个和按序输出,空间不能超过O(N)。方法是建立一个堆,开始时堆中的元素A[1]+B[1], A[1]+B[2], …, A[1]+B[N],每次从堆中取最小元素输出,然后看看这个元素是怎么来的,假设是A[i]+B[j],就把A[i+1]+B[j]插入堆。回到本问题,现在只是A,B数组都是1^3, 2^3, … N^3而已,用同样算法,如果发现相邻两次输出的值相同,说明找到了一组解。空间显然是O(N),因为共输出N^2个元素,每次堆操作是O(logN),所以时间是O(N^2*logN)

Interview Questions: Elementary Symbol Table

2. 判断一个树是否是BST。要求使用O(h)的空间,h是树的高度。

答:

int check(Node *p, int low, int high) {
  if (low > high) return 0;
  if (p == NULL) return 1;
  return check(p->left, low, p->value) && check(p->right, p->value, high);  
}