在这篇文章中，我将分享一次Grammarly 面试真题 - Climbing Stairs and Perfect Substrings: A Technical Interview Journey -的技术面试经历，包括两道算法题的解答过程：Climbing Stairs 和 Perfect

---

题目一：Climbing Stairs

题目描述（英文原文）： You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? You can assume n is greater than 0.

示例：

• Example 1:
  • Input: n = 2
  • Output: 2
  • Explanation: There are two ways to climb to the top.
    1. 1 step + 1 step
    2. 2 steps
• Example 2:
  • Input: n = 3
  • Output: 3
  • Explanation: There are three ways to climb to the top.
    1. 1 step + 1 step + 1 step
    2. 1 step + 2 steps
    3. 2 steps + 1 step

---

面试过程回顾

1. 澄清问题环节

候选人首先提出了几个问题，以便更好地理解题意：

• “我是否只需要返回所有可能的路径数量？”
• 面试官确认道：“是的，只需要计算总共有多少种不同的走法。”

2. 解题思路沟通环节

候选人从朴素的递归解法入手，解释了基本思路：

• “我们可以将这个问题定义为 S(n)，表示到达第 n 个台阶的不同方法数。”
• “因为到达第 n 个台阶有两种方式：从第 (n-1) 个台阶迈一步或者从第 (n-2) 个台阶迈两步，所以递推关系为 S(n) = S(n-1) + S(n-2)。”

候选人还指出，纯粹使用递归会导致时间复杂度为指数级，原因是存在大量重复计算。

3. 优化方案讨论

候选人继续探讨了如何优化该算法，提出了两种方案：

• “我们可以使用记忆化递归（Memoization）或者动态规划（Dynamic Programming, DP）来避免重复计算。”
• “我倾向于使用迭代的动态规划解法，这样可以更高效地解决问题。”

4. 动态规划解法详细说明

候选人详细介绍了动态规划的思路：

• “我们创建一个数组 dp，其中 dp[i] 表示到达第 i 个台阶的不同方法数。递推关系是：dp[i] = dp[i-1] + dp[i-2]。”
• 基础条件：dp[1] = 1 和 dp[2] = 2。
• 最后，候选人提出：“可以在此基础上编写代码实现，代码中我会从第 3 个台阶开始遍历，逐步计算到第 n 个台阶的走法。”

5. 时间复杂度总结

候选人总结了该方案的时间和空间复杂度：

• “由于只需线性遍历数组，所以时间复杂度为 O(n)。”
• “空间复杂度也是 O(n)，因为需要存储 dp 数组。”

---

题目二：Perfect Substrings

题目描述（英文原文）： A string s comprised of digits from 0 to 9 contains a perfect substring if all the elements within a substring occur exactly k times. Calculate the number of perfect substrings in s.

示例：

• Example:
  • Input: s = "1102021222", k = 2
  • Output: 6
  • Explanation: The 6 perfect substrings are:
    1. s[0:1] = 11
    2. s[0:5] = 110202
    3. s[1:6] = 102021
    4. s[2:5] = 0202
    5. s[7:8] = 22
    6. s[8:9] = 22

---

面试过程回顾

1. 澄清问题环节

候选人首先询问了一些问题来确保对题意的正确理解：

• “我们可以假设 k 始终大于等于 1 吗？”
• “输入字符串的长度是否始终大于或等于 k？”

2. 解题思路沟通环节

候选人先提出了一个朴素解法：

• “暴力解法是枚举所有可能的子串，这需要 O(n^2) 的时间复杂度。”

在提出改进方案时，候选人解释了如何利用滑动窗口（Sliding Window）技术来优化算法：

• “可以使用滑动窗口技术，用字典记录当前窗口内每个字符的出现频率，利用两个指针来表示窗口的边界。”

3. 优化方案讨论

候选人进一步解释了算法的优化步骤：

• “如果当前窗口内某个字符的出现次数超过了 k，我们就将左指针右移，直到频率小于等于 k。”
• “在每次检查窗口大小时，如果所有字符的频率都等于 k，则计数器增加。”

4. 时间复杂度总结

候选人总结了优化算法的时间复杂度：

• “这个算法的时间复杂度是 O(n)，因为滑动窗口从左到右遍历每个位置，且每个位置最多访问一次。”

---

行为问题（Behavioral Questions）对话

面试官在算法题之后，问了一些行为面试问题来考察候选人的团队合作和解决问题的能力。例如：

• “Can you tell me about a time when you faced a challenging problem and how you solved it?”
• 候选人回答道：“在过去的项目中，我曾经遇到过一个无法复现的 bug。当时我仔细分析了日志文件，并结合用户行为模式进行推测，最终定位到问题出在并发处理的某个模块中。我修改了代码并增加了日志记录，问题得到了彻底解决。”

如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。

In this interview, I demonstrated my understanding of common algorithmic problems and my problem-solving abilities. Each problem presented different challenges, but all could be solved through logical algorithm strategies.

If you need more interview support or interview proxy practice, feel free to contact us. We offer comprehensive interview support services to help you successfully land a job at your dream company.