经典面试题 之 查字典

题目的大意是先给出一些字符串做为字典D,然后再依次输入单个字符串A做查询,如果A在D中,则输出Yes,否则输出No。比如:

字典:Hello、World、Time、Table
查询:Hello、Get、Found、Time
输出:Yes、No、No、Yes

很明显这道题可以用HashSet很简单地解出来,O(n)时间构造,O(1)时间查询/次。但是HashSet有一个问题,就是使用的内存比较大,字典中每个单词都要存一遍,而其中有些空间是浪费掉的,比如:

  • Astray
  • Astrology
  • Astronaut
  • Astronautics

这几个单词的开头几个字母都是一样的,它们可以被压缩起来,只保存一份就可以了。那什么样的数据结构可以共享几个元素的头部,而分离它们的尾部呢?比较常用的是树形结构,根部是共享的,树枝就分叉了。但是似乎传统的二叉树(Binary Tree)不能很好地解决字典的问题,因为它一个结点只有两个分支,而单词的一个字母后面可能有26种字母的可能,(假设单词都是小写英文字母),于是就想到了26叉树。树的结构大约是:

其实它的学名是Trie,标准的实现要更灵活高效一点,这里只是用26叉树来举个例子。

将单词插入字典,方法是每个节点保存一个字母,单词从前到后的字母顺序就是树中从上到下的路径。

在字典中查找单词,方法和插入时类似,只有当整个单词都走一遍,并且当前节点的complete为true中,才表示单词已找到,返回true:

不完全测试:

经典面试题 之 按单词逆序

题意大致是:给出一个字符串,将其中的单词的顺序颠倒,而单词本身不变,即输入"ab bc cd de",输出"de cd bc ab"。

第一次听说这个题目是在大学里,告诉我题目的那个人,没有留给我思考的时间,就直接把答案说了,所以我也不知道能不能独立想出这道题的答案。这道题的解法有很多,其中描述起来最简单的是,先把整个字符串倒序,再把每个单词倒序。

以下是代码:(这个代码假设输入数据中只包含空格和英文字母)

以下是测试数据,不是很全,应该还很多吧……

经典面试题 之 在单调矩阵中查找元素

题目的大意是要求在一个N*N的矩阵中,找出一个特定的元素,这个矩阵满足两个条件:1)每一行的元素,从左到右严格递增;2)每一列的元素,从上到下严格递增。

这道题的限制太多,以至于很容易想到结果。元素都是递增(或者递减也行)的,要在一行上找元素,很显然用二分搜索了,那么一共N行,时间复杂度就是O(N*logN)。显然这不是最快的方法,要不然题目就没有意义了。

继而想到每一行递增,每一列也递增,那么主对角线也是递增的,而且满足一个很好的性质:

A11 A12 A13 A14 A15 A16 A17

A21 A22 A23 A24 A25 A26 A27

A31 A32 A33 A34 A35 A36 A37

A41 A42 A43 A44 A45 A46 A47

A51 A52 A53 A54 A55 A56 A57

A61 A62 A63 A64 A65 A66 A67

A71 A72 A73 A74 A75 A76 A77

假设以上矩阵A满足递增的性质,那么对于A55而言,[A11, A55]这个矩阵中所有的值都不超过A55,而[A55, A77]这个矩阵中所有的值都不小于A55。所以说,如果要找个值比A44大,而比A55小,那么它一定在[A15, A67]和[A51, A76]这两个矩阵中,于是搜索规模直接减少了一半。对于[A15, A67]和[A51, A76],继续套用之前的算法就行了。

代码略,会写二分搜索的话,没几分钟就写完了。算法的总体复杂度大约是O(logN * logN),没有详细得证明过,若有错误请指出。

经典面试题 之 洗牌问题

问题的大意是:有两堆牌A[1...n]和B[1...n],通常洗牌方法是把两堆牌一张一张地交叉然后合成一堆,就变成了A[1], B[1], A[2], B[2] ... A[n], B[n]。要求用程序实现之。

最朴素的方法当然是新一个大小一样的数组,填充结果,然后复制回原来的数组即可。时间O(N),空间O(N)。程序略。

当然O(N)的空间是没有必要的,直接在原数组上修改即可,方法和之前的数组题差不多。其实我并不理解这题的难点在哪里,也许是找循环节,但是不找循环节的话,时间复杂度也近似为O(N),(尽管有多了一些判断)。找循环节的算法在一篇论文里有描述:Computing the cycles in the perfect shuffle permutation

以下是暴力(即不找循环节)的做法(其中n为总的牌数,a的初始状态是A[1], A[2] ... A[n], B[1], B[2], ... B[n]):

以下是测试代码:

经典面试题 之 数组的循环右移

题目的大意是将一个长度为n的数组A内的元素循环右移m位(当然左移也可以),比如数组 {1, 2, 3, 4, 5}右移3位之后就变成{3, 4, 5, 1, 2}。

这题最平凡的做法是开另一个大小一样的数组B,遍历一下,令B[(i + m) % n] = A[i],再将B的内容写回到A即可。这个方法的时间复杂度为O(N),空间复杂度也为O(N)。

很明显,需要优化空间的使用。有一种很优美但不太好懂的方法,是先将A的元素倒置,即{1, 2, 3, 4, 5}变成{5, 4, 3, 2, 1},然后将前m位倒置,即{3, 4, 5, 2, 1},再将后n-m位倒置,即{3, 4, 5, 1, 2}。完成。证明略,代码如下:

不过这种方法需要对每个位置写入2次,看上去也不怎么好,那有没有更好的呢?

我们要做的只是把每个元素放到它应该在的位置,比如开头的例子,1应该放在4的位置,把1放好之后,4就没地方了,那4应该在哪呢,在2的位置,以此类推,就可以把所有的元素都放好,而且只放了一次。看上去这样做很完美,但仔细想想就能想出反例子,比如{1, 2, 3, 4, 5, 6, 7, 8, 9}右移3位,就是1放在4个位置,4放在7的位置,然后7放回1,这时候一圈兜完了,但只排好了3个元素,剩下的6个元素没有动过,怎么办呢?继续下个呗,就是2,然后2、5、8也排好了,继续3、6、9,这时候下一个元素是1了(因为1之前就被放在了4的位置),应该停止了,那程序怎么会知道停在这里了,于是就想到了最大公约数,9和3的最大公约数是3,于是做前3个数的循环就可以了,为什么上一个例子只需做一次,因为元素个数(5)和移动位数(3)互质。

具体的数学证明略,直接上代码:

以下是测试数据:

经典面试题 之 单链表找环

大概的题意是,给出一个单向链表的头节点,求这么链表是否有环。有环的定义是,链表的尾节点指向了链接中间的某个节点。单链表的定义如下:

这道题目还有一些变种,比如求链接的长度,求链表的尾节点等,不过大同小异。第一次听说这个题目,是在大三的时候,从一个刚面完试的学长那里。他当时的做法是对这个链表求逆,求逆的结果链表上每一个指针都反向,如果逆序完之后,链表的头节点不变,即说明链接有环。具体的证明过程略。这个方法的复杂也是O(N),但是需要修改原链表,或者使用O(N)的额外空间。

标准做法是使用两个指针,一个每次往前走2步,一个每次往前走1步,如果两个指针相遇,即说明链表有环,时间复杂度为O(N),空间复杂度为O(1)。

代码如下:

测试数据也比较简单,考虑一下空指针、单个节点成环、整条链表成环就可以了: