# LinkedIn 高频面试题：不用 replace 做字符串替换 + 用户关系距离（Connection Distance）
本文由 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，获得真题。
联系方式
Email: [email protected] Telegram: @OAVOProxy