interview

面试刷题总结(八)- 字符串

解决两个字符串的动态规划问题,一般都是用两个指针 i,j 分别指向两个字符串的最后,然后一步步往前走,缩小问题的规模。

解字符串问题常用的算法是采用滑动窗口的方法。

避免字符串 O(n) 比较的一个方法是使用 hash。

字符串问题本质上都是自动机问题,实际上还是图论问题。

后缀数组技巧

kmp

  1. next 数组的定义为:当前位置的子字符串,前缀和后缀匹配的最大长度为多少。
  2. KMP 计算 next 数组和查找字符串的过程几乎是一样的,所以关键就在于构造 next 数组。
  3. 构造 next 数组的关键就一句话:次大匹配就是(失败的)最大匹配处的子串的最大匹配,也即 j = next[j-1]
def kmp(t, p):
    """return all matching positions of p in t"""
    next = [0]
    j = 0  # j 表示当前自创中前缀和后缀匹配的最大长度
    # 注意这里是从 1 开始
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = next[j - 1]  # 关键之处
        if p[i] == p[j]: # 相等时,最大匹配自然要 +1
            j += 1
        next.append(j)
    ans = []
    j = 0
    for i in range(len(t)):
        while j > 0 and t[i] != p[j]:
            j = next[j - 1]  # 关键之处
        if t[i] == p[j]:
            j += 1
        if j == len(p):
            ans.append(i - (j - 1))
            # 这里是匹配成功了,但是要接着找下一个,所以按失败处理
            j = next[j - 1]
    return ans

def test():
    p1 = "aa"
    t1 = "aaaaaaaa"

    assert(kmp(t1, p1) == [0, 1, 2, 3, 4, 5, 6])

    p2 = "abc"
    t2 = "abdabeabfabc"

    assert(kmp(t2, p2) == [9])

    p3 = "aab"
    t3 = "aaabaacbaab"

    assert(kmp(t3, p3) == [1, 8])

    print("all test pass")

if __name__ == "__main__":
    test()

自动机

Trie 是一个自动机,KMP 是一个自动机,AC 自动机是 Trie 上运行 KMP 得到的自动机。Trie 和 KMP 都可以用于单模匹配,AC 自动机可以用于多模匹配。AC 自动机是确定性有限状态自动机 (DFA)。

正则表达式构建出来的却是一个非确定性有限状态自动机(NFA),非确定指的是跳转的时候可能有多个分支。要实现非指数时间解,也就是不用回溯,其实就是把回溯的深度优先遍历改成了广度优先遍历从而实现了剪枝。

哈夫曼树

https://juejin.im/post/5d1c7df2e51d45775c73dd49

参考资料

  1. https://oi-wiki.org/string/hash/
  2. https://www.zhihu.com/question/21923021/answer/37475572
  3. https://swtch.com/~rsc/regexp/regexp1.html
  4. https://stackoverflow.com/questions/31429865/trie-for-unicode-character-set
  5. https://oi-wiki.org/string/sa/
  6. https://oi.men.ci/suffix-array-notes/
  7. https://blog.csdn.net/u013421629/article/details/83178970
  8. https://oi-wiki.org/string/ac-automaton/
  9. http://nark.cc/p/?p=1453
  10. https://lingeros-tot.github.io/2019/03/05/Warming-Up-%E8%87%AA%E5%8A%A8%E6%9C%BA%E6%A8%A1%E5%9E%8B/
  11. http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/

面试刷题总结(九)- 数学知识

数学类问题一定要记得进位 v = v1 + v2 + carry

最大公约数和最小公倍数

辗转相除法(欧几里得算法). 原理在于 gcd(a, b) == gcd(b, a % b)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

排列组合

卡特兰数,为什么除以 n+1

牛顿迭代法

格雷码

二进制

  • 判断一个数是不是 2 的正整数次幂:n > 0 && (n & (n - 1)) == 0
  • 对 2 的非负整数次幂取模:x & (mod - 1)
  • 判断符号是否相同:(x ^ y) >= 0
  • 获取某一位:(a >> b) & 1
  • 遍历某个集合的子集:for (int s = u; s; s = (s - 1) & u)
  • 一的个数:while (n) {n = n & (n-1); count++}

求幂

long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

全排列

几何

有时候几何题也会出现在面试中。不过,毕竟是 coding interview 而不是 math interview,这部分复习的优先级不高。

参考

  • https://oi-wiki.org/math/

面试刷题总结(一) – 递归问题

递归是几乎一些算法的基础。实际上我认为算法题大致可以分为两类:递归和其他。

实际上计算机能解的唯二问题:

  1. 足够简单的问题:比如 x * x, x^0 = 1.
  2. 把复杂问题约简到简单问题:比如 x^n = x^(n/2) * x^(n/2)

分治、树、深度优先搜索等等实际上都是递归。

递归的核心思想:明白每个函数能做的事,并相信它们能够完成,千万不要试图跳进细节。

在面试的时候,如果允许写递归(一般是允许的),那一定要写递归解。

解题思路

对一个给定的问题:

  1. 确定哪些情形是基础情形,不需要再做递归。比如说:高度为 0 的树,或者 null 根节点,空字符串等。
  2. 把问题转化为规模更小的问题。
def fact(a, n):
    if n == 1:
        return a
    return a * fact(a, n-1)  # or n/2 or whatever...

def fact(a, n):
    if n == 1:
        return a
    h = fact(a, n/2)
    return h * h

好多时候,需要编写一个私有的 helper 方法,更改一下函数的签名。对于 Python 或者 JavaScript 的话,直接写一个闭包函数是最好的,也避免了全局变量。

Algorithme by Jeff Erickson

最后推荐一本神书:Algorithms by Jeff Erickson. 这本书全书都是在按照递归的思路讲解。

其它的书和文章的问题在于每个知识点似乎都是孤立的,比如说动态规划就在重点讲解状态转移方程和状态矩阵,而分治就在讲解如何用递归树计算时间复杂度等等。这种讲解方式下,每个知识点之间看不到有什么关联,往往熟悉了这个又忘了那个。实际上这些知识点都是有联系的,所谓的动态规划不过是状态空间搜索的一个巧妙转换,本质上和回溯是一致的,都是递归而已。每个技巧的内核都是一致的,只不过特异化之后有不同的表现,如果你不去抓住内核,通过一个主干把所有知识串联起来,而只看表面现象,那么永远也记不住的。

其他的书就好比盲人摸象,而这本书则是讲解的大象的骨骼结构和肌肉构造。分治和动归这些算法好比是大象的耳朵、尾巴等等部位,可以在外部摸到,而递归则是大象的骨架,虽然摸不到,但是只有画出了骨骼,才能把大象画好。

参考

  1. https://stackoverflow.com/questions/25367781/tips-on-solving-binary-tree-binary-search-tree-problems-using-recursion-java

面试刷题总结(七) – 树和图

图的表示方法

标准的表示方法应该是邻接表。在邻接表中我们使用链表来表示相邻节点。

任意优先搜索(Whatever First Search)

这是 Jeff Erickson 在书中提到的搜索算法框架,一个框架就综合了所有遍历算法。

树的遍历实际上和图的遍历完全一样,只是不需要标记有没有访问过当前节点。

WhateverFirstSearch(s):
  把 s 放入 bag
  while bag 非空:
    从 bag 取出 v
    if v 未标记:
      标记 v
      for 每个边 vw:
        把 w 放入 bag 中

如果 bag 的算法选用 stack,那么就可以实现深度优先遍历,如果选用 queue 就可以实现广度优先遍历。

如果选用 priority queue,那么就可以实现最优优先遍历。

  1. 如果我们使用每个边作为排序依据,那么就可以得到最小生成树,也就是传说中的 Prim 算法。
  2. 如果我们使用 dist(v) + w(v->w) 作为排序依据,那么就得到了传说中的 Dijkstra 算法。其中 dist(v) 为从源点 s -> v 的距离。
  3. 未完待续

对于没有连通的图,我们还可以使用 WFSALL 来遍历所有节点

WFSALL(G):
  for 所有节点 v:
    取消标记 v
  for 所有节点 v:
    if v 未标记:
      WhateverFirstSearch(v)

深度优先搜索

深度优先搜索实际上就是上面的 任意优先搜索 算法的特例化

DFS(v):
  标记 v
  PreVisit(v)
  for 每个边 vw:
    if w 未标记:
      parent(w) <- v
      DFS(w)
  PostVisit(v)

其中的 PreVisit 和 PostVisit 就是我们可以插入的目标函数,通过改变这两个函数就可以实现不同的算法。

拓扑排序

拓扑排序就可以简单地使用深度优先搜索实现,只不过在最后需要把顺序倒过来。

TopologicalSort(G):
  pass

二叉树外部节点总是等于内部节点加 1

解决树问题的思路

树的最大问题在于要从底层叶节点开始思考,而不是自上而下看图。递归是从基础 case 开始向上递归的。一定要画出访问的顺序图。

访问顺序图

  1. 对于任何树的问题,还是优先考虑递归,因为树本身就是一个递归性质的数据结构。
  2. 树还是天然 Devide and Conquer 的,也就是说可以分层左右两个树分别处理,然后合并得到答案。

解树的问题就只有两种方法:

  1. 分治:后序遍历,并通过左右子树和根节点一起解决问题。
      /   \
    2      3
  /  \   +---+
4      5   B
+------+
    A
  1. 遍历:在遍历过程中解决问题,比如记录最大值等。

对于树的题目,到底是迭代解还是递归解呢?

最好写递归解,比较简单。写迭代性解首先考虑栈。函数调用过程本来就会用到栈使用栈可以模拟递归调用。使用栈还可以把需要反转的操作自动反转。比如在 zigzag 层序遍历的时候。

递归的出口是选 NULL 还是叶子节点?

最好选择 null,具体来说:

  1. 有一个 corner case 是直接就传一个 null 的节点进来,所以要选 null
  2. 叶子节点比较复杂,只要判断 null 的 return 之后结果 ok, 就 null

改变函数签名与参数传递

参考回溯文档中的讲解

常见问题总结

遍历

参考 这里

二叉查找树

一定是用中序遍历来解的

其他常见的树

2-3-4 树

234 树的意思是每个节点的子节点可能有 2、3、4 个,所有的叶节点都在同一深度。

插入

对于 2-节点和 3-节点,显然是比较简单的,我们只要直接插入就行了。对于 4-节点来说,我们不能插入。不过解决方法也很简单,我们把 4-节点分裂,然后把中间节点提到上一级,然后就有两个 2-节点了,这时候就可以插入了。

在自上而下插入的过程中,我们还会把遇到的每一个 4-节点都分裂,这样保证了我们

红黑树

红黑树是为了解决二叉查找树不平衡的问题发明的。

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点永远是黑色的。
  3. 所有的叶子节点都是空节点(即 null),并且是黑色的。
  4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的路径上不会有两个连续的红色节点。)
  5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。

Null 也算节点,从头到尾都是黑色节点,红色节点只能是内部节点。每条路径都包含相同的黑色节点。

红黑树保证的是没有一个节点长度是其他路径的 2 倍,而不是每一个路径之间的差在常数倍,比如说下面这个树。

为了保证平衡,也就是第 5 个条件,插入的新节点必须是红的,如果恰好插入到了一个黑色节点下面,那就结束了,如果插入到了一个红色节点下面,需要调整。

跳表

跳表显然不是一颗普通意义上的树,但是因为他的时间复杂度和红黑树类似,并且实现起来简单,不容易出 bug,所以很多时候,都把跳表作为红黑树的一个替代来使用,比如在 Redis 中。

B 树

B 树用于基于硬盘的数据库的索引。为什么不直接用二叉树呢?B 树本质上来说就是 2-3-4-n 树,因为硬盘读取相对于内存访问来说实在太慢了,所以减少树的层级有利于提升速度。

更多的树

有些题看起来是树,实际上是利用递归关系的,或者只是利用到了一个性质,但本质上是其他问题

参考资料

  1. https://stomachache007.wordpress.com/2017/03/12/%E4%B9%9D%E7%AB%A0%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0-3-binary-tree-divide-conquer/
  2. https://blog.csdn.net/yang_yulei/column/info/easydatastruct
  3. https://web.archive.org/web/20200112020131/https://merunas.io/tree-data-structures/
  4. 《数据结构与算法分析:C 语言描述》
  5. https://stackoverflow.com/questions/8765558/why-dont-we-use-2-3-or-2-3-4-5-trees

SDE 面试问题储备

前提

  • English is a MUST.
    文艺复兴以降,西方积累了几百年的知识不是一朝一夕就能超越的。即使我们现在在某些方面已经取得了优势,也应该虚心学习。阅读英文文档是对个人能力的极大提升。
  • 如果只会一门语言,大大减分,尤其是只会 Java
    一个合格的程序员工作中可能只使用一种主力语言,但是不应该故步自封,停留在一个语言的一个非常不好的征兆。尤其是 Java 程序员,好多都对外界的知识完全不了解。Java 是一门优秀的语言,但是很多其他语言也都有各自的优点。

综合型问题

  • 如何实现一个服务器?用 python 理解服务器模型
  • 统计 Redis 中每个 Key 占用的空间大小
  • 设计一个翻页系统。使用 select * from table limit 10 offset 10 翻页有什么问题 参考
  • 如何实现 adblock plus 的过滤算法
  • 敏感词过滤算法
  • 简单设计一下群聊或者微博的 feed。推和拉各有什么优缺点?
  • http 请求的实现?http 代理的原理如何?https 代理呢?

操作系统

  • web server 的多进程模式是如何实现的。fork 之后数据库连接怎么办?preload 和 copy-on-write 之间如何抉择?

数据库

LSM 和 B+树各有什么优缺点?什么是为读优化,什么是为写入优化

用数据库的自增 ID 来作为唯一 ID 有什么问题呢?使用 UUID 呢?

  1. 使用 limit offset。实现非常简单,但是当页码越来越大的时候,查询会越来越慢
  2. 记录 id,每次查询都按条件 where id > x 过滤。缺点是需要记录中间状态。

下面这段代码可能有什么问题?如果有,如何优化

posts = db.execute("select * from posts limit 10").fetch_all()
for post in posts:
    post.author = db.execute("select * from users where id = %s" % post.author_id).fetch_one()
return posts

典型的 N+1 问题,即使不知道这个概念,也应该能看出问题来。

前端

  • 虚拟 DOM 如何实现?虚拟 DOM 的 diff 算法如何实现

智商鉴定题

  • int main() 和 void main() 的区别是什么?返回的 int 是用来干嘛的?

LSM 和 sstable

核心要点

lsm 是 bigtable、leveldb、rocksdb 等数据库采用的算法。

硬盘,尤其是机械硬盘,顺序写入性能远大于随机写入性能,所以 lsm 把大量的随机写入抓换成了顺序写入,从而极大地又花了写入能力。同时查找效率收到了损伤。

适用于顺序写入多,随机读取少的场景。

之所以要使用 Immutable Memtable,就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

操作

  1. 插入

    写入 WAL,然后操作 memtable。WAL 是顺序读写,而 memtable 是跳表,操作都很迅速

  2. 更新

    和插入其实是一样的操作

  3. 删除

    插入一条特殊的删除日志,在 memtable 中标记删除

  4. compaction(压缩)

    当 memtable 达到设定的阈值的时候,会写入到 immutable memtable,然后写入到硬盘上的 sstable。当 sstable 的数量达到某个阈值的时候,就合并到下一级的 memtable。需要注意的是只有第一级的 memtable 可能有重复的键值,其他层都不会有重复的,所以可以多线程 compact。

  5. 读取

    最原始的算法:首先从 memtable 读,然后从 sstable 中往高层读取。

    可以采取的优化方法:

    1. 把 sstable 的一些原始信息放到 manifest 中,放在内存中,快速查找
    2. 使用 bloom filter 先过滤一遍,看 key 是否在 LSM 中,然后再查找。

一图胜千言:

参考:

  1. http://blog.fatedier.com/2016/06/15/learn-lsm-tree/

动态规划(LeetCode 413. Arithmetic Slices)

LeetCode 413. Arithmetic Slice

是一道可以用动态规划解的问题

题目

给定一个数组,找出其中等差数列的个数。等差数列的定义:3 各元素以上,每个元素之间差相等。

比如:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

下面的就不是:

1, 1, 2, 5, 7

例子:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

解法

观察发现,当我们遍历数组的时候,如果能和前一个元素构成等差数列,那么在这个位置可以构成的等差数列的个数就是上一个位置加一,所以的到递推公式:

dp[i] = dp[i-1] + 1

借用官方答案里的图片:

所以我们就得到了答案:

class Solution:
    def numberOfArithmeticSlices(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        dp = [0] * len(A)
        for i in range(2, len(A)):
            if A[i] - A[i-1] == A[i-1] - A[i-2]:
                dp[i] = dp[i-1] + 1

        return sum(dp)

大规模字符串的匹配

问题:假设我们有一组比较长的文本,每一个文本都有几十 k 左右,还有一些敏感关键词需要删除,大概有几千,然后需要在这些文本中把关键词找出来。

方法 1:暴力搜索

import re

compiled_words = [re.compile(r"\b" + word + r"\b") for word in my20000words]

for sentence in sentences:
  for word in compiled_words:
    print(re.sub(word, "***", sentence))

改进 1:把正则组合起来

pattern = "\b(word1|word2|word3)\b"

for sentence in sentences:
  print(re.sub(pattern, "***", sentence))

改进 2:使用 Trie 优化正则

对于数组:[‘foobar’, ‘foobah’, ‘fooxar’, ‘foozap’, ‘fooza’],使用上面的方法,我们可能会写出正则:

"\b(foobar|foobah|fooxar|foozap|fooza)\b"

但是这并不是最优的正则,应该使用前缀树的思想来合并单词,形成下面的正则:

r"\bfoo(?:ba[hr]|xar|zap?)\b"

具体的方法可以看这里:https://stackoverflow.com/a/42789508/1061155

改进 3:基于集合的搜索

import re

def delete_banned_words(matchobj):
    word = matchobj.group(0)
    if word.lower() in banned_words:
        return ""
    else:
        return word

word_pattern = re.compile("\w+")

for sentence in sentences:
    sentence = word_pattern.sub(delete_banned_words, sentence)

参考:

https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3/42789508

https://medium.freecodecamp.org/regex-was-taking-5-days-flashtext-does-it-in-15-minutes-55f04411025f

跳表(skiplist)

平衡二叉树可以实现 O(logn) 的查找复杂度。跳表可以实现相当于平衡二叉树的复杂度查询数据,而代码实现比较简单。在 Redis 中,zset 就用到了 skiplist。

跳表是用并连的链表来实现的查询结构

  • 每个节点包含的指针的层数是由一个随机数决定的。
  • 跳表的时间复杂度和平衡二叉树相同,但是在实现上要简单很多。
  • 跳表是有序的,跳跃表的特点就是有序的,所以对于一些有序类型的数据,比如整数,日期这种,用跳跃表可以进行范围查找。
  • 在构建跳跃表和查询跳跃的复杂度一致,所以也比较适合于在线的实时索引查询,可以来一个文档,一边查找就一边知道要如何进行插入操作了。
  • 保存到磁盘和从磁盘载入也比较简单,因为本质上是几个链表,所以保存的时候可以按照数组的方式分别保存几个数组就可以了。

一些优化

空间优化,把底层的表放到硬盘里,影响增加删除节点的效率

时间优化,用数组代替链表,可以使用二分查找而非遍历

对于类似时间这种数据,比如 24 小时对应 1440 分钟对应 86400 秒钟

甚至可以固定直接用索引随机访问

实现

https://github.com/begeekmyfriend/skiplist/blob/master/skiplist.h