这轮面试来自 eBay 的 Unified Listing Platform Team，团队主要负责高并发、高性能的 Federated GraphQL 平台，服务于 eBay listing data，也就是商品数据相关的核心 API。面试中先聊了项目经历，之后进入技术题环节。

Problem Statement

Given two strings A and B, return the 0-based starting index of the first contiguous substring in A that is a permutation (anagram) of B.

If no such substring exists, return -1.

Constraints

1 <= length of B <= length of A <= 100,000

A and B consist entirely of lowercase English letters.

Example:

Input: A = "cbaebabacd", B = "abc"
Output: 0

Explanation:
The substring "cba" starting at index 0 is a permutation of "abc".

题目要求在字符串 A 中找到第一个子串，使得这个子串是 B 的一个排列。也就是说，顺序不重要，但字符种类和数量必须完全一样。

解题思路

这道题的关键是：

如果一个子串是 B 的 anagram，那么它的长度一定等于 len(B)。

所以我们只需要在 A 上维护一个长度固定为 len(B) 的滑动窗口。

每次窗口向右移动时：

1. 加入右边的新字符；
2. 移除左边的旧字符；
3. 比较当前窗口的字符频率是否和 B 一致。

因为题目只包含小写英文字母，所以可以用长度为 26 的数组统计字符频率。

面试 Follow-up：如果 A 是 stream 怎么办？

面试官进一步追问：如果 A 不是一次性给出的字符串，而是一个字符流，一个字符一个字符进来，该怎么办？

思路还是一样：

• 不需要保存完整的 A；
• 只保存最近 len(B) 个字符；
• 用 queue / deque 维护当前窗口；
• 每来一个字符，更新窗口频率；
• 如果窗口长度超过 len(B)，就移除最旧字符；
• 当窗口频率和 B 一致时，返回对应起始位置。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~