在 TikTok 的面试中，CSOAHELP遇到了两道技术题目。以下是这些题目的详细描述和我们辅导的解答过程。

---

问题 1：删除一个字符后判断是否是回文

问题描述

给定一个字符串 s，如果最多删除一个字符后它能成为回文，则返回 true。

示例：

1. 输入: s = "aba"
   输出: true
2. 输入: s = "abca"
   输出: true （解释：你可以删除字符 'c'。）
3. 输入: s = "abc"
   输出: false

我的解答

为了解决这个问题，我实现了以下函数：

1. 辅助函数：is_palindrome(string)
   • 这个函数检查给定字符串是否是回文，通过将字符串与其反转后的字符串进行比较。

2. 主函数：validPalindrome(s)
   • 这个函数使用两个指针，left 和 right，分别从字符串的开头和结尾开始。它检查这些指针所指的字符是否相同。如果不同，它会检查删除 left 指针或 right 指针所指的字符后，剩下的字符是否是回文。如果是，则返回 true，否则继续检查下一个字符。

面试官和我的交流记录：

面试官：可以确认一下，空字符串是否被认为是回文吗？

我：空字符串应该返回 False。如果输入为空字符串，我们应该返回 False。

面试官：好的，你可以开始编写代码了。

我：好的，我会在代码中处理这种特殊情况。

面试官：你的算法思路是什么？

我：我会使用两个指针，分别从字符串的两端向中间移动。如果发现不相等的字符，我会尝试删除其中一个字符，然后检查剩余部分是否是回文。

面试官：可以详细说明一下吗？

我：比如说，对于字符串 "abca"，左指针从索引 0 开始，右指针从索引 3 开始。首先检查 s[left] 是否等于 s[right]，这是对的，所以我们将左指针移动到 1，右指针移动到 2。接着检查 s[left] 是否等于 s[right]，这不对，所以我们尝试删除左指针或右指针所指的字符，然后检查剩余部分是否是回文。

面试官：听起来很合理，你可以开始编写代码了。

---

问题 2：检测无向图中是否存在环

问题描述

判断一个无向图中是否存在环。

示例：

1. 输入: [[1,2],[1,3],[2,3]]
   输出: true （解释：节点 1, 2 和 3 构成一个环。）
2. 输入: [[1,2],[2,3],[3,4],[1,5]]
   输出: false （解释：图中不存在环。）

我的解答

为了解决这个问题，我实现了一个使用深度优先搜索（DFS）算法的辅助函数来检测无向图中的环。

1. 辅助函数：dfs(node, parent, visited, graph)
   • 这个函数在图上进行深度优先搜索（DFS），将节点标记为已访问。它通过确保访问过的邻居节点不是当前节点的父节点来检查环。

2. 主函数：has_cycle(edges)
   • 这个函数首先根据给定的边构建图，然后遍历所有节点，从每个未访问的节点开始进行 DFS，以检测任何环。

面试官和我的交流记录：

面试官：图是连通的还是可能不连通的？

我：图可能是不连通的。我们需要检查每个节点。

面试官：输入是一组边吗？比如 [1, 2] 表示可以从 1 到 2 吗？

我：是的，输入是一组边，每条边连接两个节点。

面试官：你的算法思路是什么？

我：我会使用 DFS 从每个节点开始遍历，如果在同一次遍历中看到同一个节点两次，就说明存在环。

面试官：可以详细说明一下吗？

我：比如说，对于输入 [[1,2],[1,3],[2,3]]，我们从节点 1 开始，访问它的邻居节点 2，然后访问节点 2 的邻居节点 3，再访问节点 3 的邻居节点 1。由于节点 1 已经访问过，说明存在环。

面试官：听起来很合理，你可以开始编写代码了。

---

面试总结

两个题目分别涉及了删除字符后检查回文和使用 DFS 检测无向图中的环。这些任务要求我对数据结构和算法设计有深入的理解。

后续我与面试官讨论了一些公司相关的问题，比如她认为有趣的项目是什么，我应聘岗位的职责是什么等。

后续的feedback十分的不错，如果你也有面试的需要，欢迎购买我们的面试辅助服务。