一、算法概念題

1. 二分法

• 總結(jié)鏈接
• 幾種查找情況的模板
• 另一個(gè)好記的總結(jié)
• 總結(jié)：搜索元素兩端閉，while帶等，mid±1，結(jié)束返-1
  搜索邊界常常左閉右開，while小于，mid看邊界開閉，閉±開=，結(jié)束if檢查左=？然后返回
• 例1：標(biāo)準(zhǔn)
  • 循環(huán)條件：left <= high
  • left = mid + 1, right = mid - 1
  • return mid / -1
• 例2：找左邊界：有序，有重復(fù)
  • 循環(huán)條件：left < high
  • left = mid +1, right = mid（右邊界向左收縮）
  • return nums[left] == target ? left : -1
• 例3：找右邊界：有序，有重復(fù)
  • 循環(huán)條件：left < high
  • mid = xxx + 1
  • left = mid, right = mid - 1
  • return nums[right] == target ? right : -1
• 總結(jié)：基本上是循環(huán)條件，判斷條件，邊界更新方法的不同組合

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 0grid[row][col] = 0return dfs(row-1, col) + \dfs(row+1, col) + \dfs(row, col-1) + \dfs(row, col+1) + 1if not grid:return 0m = len(grid)n = len(grid[0])ans = 0for i in range(m):for j in range(n):if grid[i][j]:ans = max(ans, dfs(i,j))return ans

3. BFS

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

def maxDistance(grid: List[List[int]]) -> int:# 從1開始出發(fā)bfs，記錄距離m = len(grid)n = len(grid[0])start = []# 存入所有起點(diǎn)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# 四個(gè)方向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]:continuestart.append([row,col,dis+1])grid[row][col] = 1 #訪問過的位置記錄為1return dis #最后一個(gè)dis

4. 動(dòng)態(tài)規(guī)劃

• 典型題總結(jié)

5. 滑動(dòng)窗口

• 雙指針、快針慢針
• 典型題：鏈表、數(shù)組、子串

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 - 1for j in range(l, r):if array[j] <= x:i += 1array[i], array[j] = array[j], array[i]array[i + 1], array[r] = array[r], array[i + 1]return i + 1

各種樹

• Trie樹
• 紅黑樹

二、算法題

1. topK的3種解法

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

2. 3Sum

3. 反轉(zhuǎn)鏈表

4.1 判斷有向圖是否存在環(huán)

• DFS：從一點(diǎn)出發(fā)若回到該點(diǎn)則說明存在環(huán)（從入度為0的點(diǎn)出發(fā)）；鄰接表儲存的時(shí)間復(fù)雜度為O(V+E)
• 拓?fù)渑判蚶}：把所有入度為0的點(diǎn)和其輸出的邊依次刪除，如果最后不剩點(diǎn)了則說明沒有環(huán)（代碼）
  • 拓?fù)湫虮硎居邢驘o環(huán)圖

4.2 判斷無向圖是否存在環(huán)

• Union-Find并查集
  • 初始化所有元素的根為-1，遍歷每一條邊，修改根節(jié)點(diǎn)：合并集合時(shí)讓兩者擁有相同的根，其中一個(gè)的根一定是-1
  • 如果出現(xiàn)相同的根，則說明有環(huán)
• BFS
  • 黑白灰：初始化為白，入隊(duì)為灰，出隊(duì)為黑
  • 如果子結(jié)點(diǎn)的顏色有不是白色的，說明有環(huán)（在此之前已經(jīng)訪問過一次了）

5. 最近一個(gè)小時(shí)內(nèi)訪問頻率最高的10個(gè)IP

• 每秒對應(yīng)一個(gè)HashMap，IP地址為key，出現(xiàn)次數(shù)作為value
• 同時(shí)建立一個(gè)固定大小為10的小根堆，用于存放當(dāng)前出現(xiàn)次數(shù)最大的10個(gè)IP
• 每次來一個(gè)請求，就把該秒對應(yīng)的HashMap里對應(yīng)的IP計(jì)數(shù)器增1，并查詢該IP是否已經(jīng)在堆中存在
  • 如果不存在，則把該IP在3600個(gè)HashMap的計(jì)數(shù)器加起來，與堆頂IP的出現(xiàn)次數(shù)進(jìn)行比較
  • 如果已經(jīng)存在，則把堆中該IP的計(jì)數(shù)器也增1，并調(diào)整堆
• 每過一秒，把最舊的那個(gè)HashMap銷毀，并為當(dāng)前這一秒新建一個(gè)HashMap，這樣維持一個(gè)一小時(shí)的窗口
• 每次查詢top 10的IP地址時(shí)，把堆里10個(gè)IP地址返回來即可

三、編程語言概念題

1. python中is和==的區(qū)別

• is是用來判斷兩個(gè)變量引用的對象是否為同一個(gè)
• ==用于判斷引用對象的值是否相等
• （可以通過id()函數(shù)查看引用對象的地址）

python生成器

四、大數(shù)據(jù)Spark/MapReduce

1. Spark性能如何調(diào)優(yōu)

• 避免創(chuàng)建重復(fù)的RDD
• 盡量復(fù)用同一RDD
• 盡量避免使用shuffle類算子
• 優(yōu)化數(shù)據(jù)結(jié)構(gòu)
• 使用Hive ETL預(yù)處理數(shù)據(jù)
• 過濾少數(shù)導(dǎo)致傾斜的key
• 提高shuffle操作的并行度
• 兩階段聚合
• 將reduce join轉(zhuǎn)為map join