LinkedIn 高频面试题：不用 replace 做字符串替换 + 用户关系距离（Connection Distance）

# 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，获得真题。