本文由 oavoservice 原創整理：兩道常見小題，分別考察「線性掃描的字串處理」和「社交網絡圖的最短距離」。
Question 1：不使用內建 replace 實作字串替換
題目
給定字串 s、模式串 pat、替換串 rep，返回把 s 中所有 pat 替換成 rep 的新字串，要求不調用語言內建的 replace。
思路（雙指標/滑動視窗）
核心就是自己寫一遍「從左到右匹配」：
- 用索引
i掃描s - 如果
s[i:i+len(pat)] == pat，輸出rep並i += len(pat) - 否則輸出
s[i]並i += 1
Python 實作
def replace_without_builtin(s: str, pat: str, rep: str) -> str:
if pat == "":
return s
out = []
i = 0
m = len(pat)
while i < len(s):
if i + m <= len(s) and s[i:i+m] == pat:
out.append(rep)
i += m
else:
out.append(s[i])
i += 1
return "".join(out)
面試官常問
- 重疊匹配怎麼處理？（上述實作是「非重疊、從左到右貪心」，大多數語言 replace 語義也是這樣）
- 時間複雜度？（最壞
O(n*m)，若需要更快可用 KMP 或滾動雜湊）
Question 2：LinkedIn Connection Distance（用戶關係距離）
題目
給定一個無向圖：用戶之間的連接關係（好友/同事），以及兩個用戶 src、dst，求兩者之間的最短連接距離（最少邊數）。
- 若不可達返回
-1
思路（BFS 最短路）
無權圖最短距離就是 BFS：
- 從
src入隊，距離 0 - 擴展鄰居，第一次到達
dst即最短
Python 模板
from collections import deque
from typing import Dict, List
def connection_distance(graph: Dict[str, List[str]], src: str, dst: str) -> int:
if src == dst:
return 0
if src not in graph or dst not in graph:
return -1
q = deque([src])
dist = {src: 0}
while q:
u = q.popleft()
for v in graph.get(u, []):
if v in dist:
continue
dist[v] = dist[u] + 1
if v == dst:
return dist[v]
q.append(v)
return -1
面試官常追問
- 圖很大怎麼辦？（雙向 BFS / 分層加載 / 限制最大層數）
- 如果要返回路徑而不是距離？（記錄 parent 回溯）
如果你在準備 LinkedIn 的 VO/OA，oavoservice 會把這類「基礎題 + 追問擴展」訓練到可快速落地表達。
需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。