算法（数据结构）面试问题准备 二分法/DFS/BFS/快排

一、算法概念题

1. 二分法

• 总结链接
• 几种查找情况的模板
• 另一个好记的总结
• 总结：搜索元素两端闭，while带等，mid±1，结束返-1
  搜索边界常常左闭右开，while小于，mid看边界开闭，闭±开=，结束if检查左=？然后返回
• 例1：标准
  • 循环条件：left <= high
  • left = mid + 1, right = mid - 1
  • return mid / -1
• 例2：找左边界：有序，有重复
  • 循环条件：left < high
  • left = mid +1, right = mid（右边界向左收缩）
  • return nums[left] == target ? left : -1
• 例3：找右边界：有序，有重复
  • 循环条件：left < high
  • mid = xxx + 1
  • left = mid, right = mid - 1
  • return nums[right] == target ? right : -1
• 总结：基本上是循环条件，判断条件，边界更新方法的不同组合

2. DFS

• Leetcode-695. 岛屿的最大面积
• 代码模板

 def dfs(row, col):
      if row < 0 or col < 0 or row >= m or col >= n or not grid[row][col]:
          return 0
      grid[row][col] = 0
      return dfs(row-1, col) + \
          dfs(row+1, col) + \
          dfs(row, col-1) + \
          dfs(row, col+1) + 1
  
  if not grid:
      return 0
  m = len(grid)
  n = len(grid[0])
  ans = 0
  for i in range(m):
      for j in range(n):
          if grid[i][j]:
              ans = max(ans, dfs(i,j))
  return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. BFS

• Leetcode-1162. As Far from Land as Possible
• 代码模板

def maxDistance(grid: List[List[int]]) -> int:
    # 从1开始出发bfs，记录距离
    m = len(grid)
    n = len(grid[0])
    start = []
    # 存入所有起点1的位置
    for i in range(m):
        for j in range(n):
            if grid[i][j]:
                start.append([i,j,0])
    # 特例
    if not start or len(start) == m*n:
        return -1
    
    # 四个方向
    x = [1,0,-1,0]
    y = [0,1,0,-1]
    while start:
        i, j, dis = start.pop(0)
        for k in range(4):
            row = i + x[k]
            col = j + y[k]
            if row < 0 or col < 0 or row == m or col == n or grid[row][col]:
                continue
            start.append([row,col,dis+1])
            grid[row][col] = 1 #访问过的位置记录为1
    return dis #最后一个dis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

4. 动态规划

• 典型题总结

5. 滑动窗口

• 双指针、快针慢针
• 典型题：链表、数组、子串

6. 快排

def quick_sort(array, l, r):
    if l < r:
        q = partition(array, l, r)
        quick_sort(array, l, q - 1)
        quick_sort(array, q + 1, r)


def partition(array, l, r):
    x = array[r]
    i = l - 1
    for j in range(l, r):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[r] = array[r], array[i + 1]
    return i + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

各种树

• Trie树
• 红黑树

二、算法题

1. topK的3种解法

• 冒泡
• 最小堆
• 快排，分布式

2. 3Sum

3. 反转链表

4.1 判断有向图是否存在环

• DFS：从一点出发若回到该点则说明存在环（从入度为0的点出发）；邻接表储存的时间复杂度为O(V+E)
• 拓扑排序例题：把所有入度为0的点和其输出的边依次删除，如果最后不剩点了则说明没有环（代码）
  • 拓扑序表示有向无环图

4.2 判断无向图是否存在环

• Union-Find并查集
  • 初始化所有元素的根为-1，遍历每一条边，修改根节点：合并集合时让两者拥有相同的根，其中一个的根一定是-1
  • 如果出现相同的根，则说明有环
• BFS
  • 黑白灰：初始化为白，入队为灰，出队为黑
  • 如果子结点的颜色有不是白色的，说明有环（在此之前已经访问过一次了）

5. 最近一个小时内访问频率最高的10个IP

• 每秒对应一个HashMap，IP地址为key，出现次数作为value
• 同时建立一个固定大小为10的小根堆，用于存放当前出现次数最大的10个IP
• 每次来一个请求，就把该秒对应的HashMap里对应的IP计数器增1，并查询该IP是否已经在堆中存在
  • 如果不存在，则把该IP在3600个HashMap的计数器加起来，与堆顶IP的出现次数进行比较
  • 如果已经存在，则把堆中该IP的计数器也增1，并调整堆
• 每过一秒，把最旧的那个HashMap销毁，并为当前这一秒新建一个HashMap，这样维持一个一小时的窗口
• 每次查询top 10的IP地址时，把堆里10个IP地址返回来即可

三、编程语言概念题

1. python中is和==的区别

• is是用来判断两个变量引用的对象是否为同一个
• ==用于判断引用对象的值是否相等
• （可以通过id()函数查看引用对象的地址）

python生成器

四、大数据Spark/MapReduce

1. Spark性能如何调优

• 避免创建重复的RDD
• 尽量复用同一RDD
• 尽量避免使用shuffle类算子
• 优化数据结构
• 使用Hive ETL预处理数据
• 过滤少数导致倾斜的key
• 提高shuffle操作的并行度
• 两阶段聚合
• 将reduce join转为map join