在这个“金三银四”早已内卷成“铜三铁四”的时代，能收到字节跳动（TikTok的母公司）的面试邀请，心情无疑是复杂的。一半是“终于轮到我了”的窃喜，一半是对传说中“面试造航母”的恐惧。作为一名在科技大厂求职路上跋涉的华人，这次的远程面试经历，确实让我对字节的技术面试有了新的认识，特别是那道看似简单却暗藏玄机的算法题。

题目是这样的：

Swapping Parentheses

Description

Parentheses strings are strings containing only the characters '(' and ')'. A parentheses string is considered balanced when its opening parentheses align with its closing parentheses. For example, "()()" and "(())()" are balanced parentheses strings, while ")()(", ")(", and "))(( " are not.

Given a string consisting of the same number of opening and closing parentheses, determine the minimum number of character swaps required to make the string a balanced parentheses string.

Example

s = "))(( "

Swap the first and the last characters to get "()()", a balanced parentheses string. The minimum number of swaps is 1.

坦白说，看到这道题我心里稍微松了一口气。毕竟不是什么动态规划难题或是复杂的图论。但直觉告诉我，事情没那么简单。题目强调“最小交换次数”，这通常意味着贪心算法（Greedy Algorithm）或者需要一些巧妙的计数方法。

我首先想到的暴力解法是尝试所有可能的交换，但这立刻被我否决了，时间复杂度会爆炸。我向面试官分享了我的这个想法，并说明了其不可行性，他点了点头，示意我继续。

我的思路开始转向如何一次遍历就解决问题。一个关键的观察点是，一个平衡的括号字符串，在任何一个位置，它前面的开括号数量总是大于或等于闭括号的数量。

基于这个观察，我开始从左到右遍历字符串。我维护一个计数器来追踪括号的“平衡度”，遇到'('就加一，遇到')'就减一。当计数器在某个位置变为负数时，就意味着这里出现了一个“不该出现”的闭括号，导致了不平衡。

这个多余的')'必须和它后面的某个'('进行交换。为了保证交换次数最少，我们应该用最“划算”的方式来修正这个不平衡。一个贪心的策略就是，当我发现一个错位的')'时，我就从字符串的末尾开始寻找一个'('来和它交换。这样做的好处是，可以一次交换就“大概率”把两个字符都放在正确的位置上。

于是，我提出了一个具体的思路：使用两个指针，一个从左向右（left），一个从右向左（right）。当left指针遇到一个导致平衡度为负的')'时，就启动right指针从后往前寻找第一个'('，然后进行交换，并计交换一次。

面试官在我讲解思路的过程中，时而点头，时而追问一些边界情况的处理，比如为什么从后往前找'('是最佳策略。我解释说，这样可以最大化地保证被换到前面的'('能够对后续的子串平衡做出贡献。

最终，在白板上将这个思路转化为代码后，面试官露出了满意的神情。我们又简单探讨了一下时间复杂度和空间复杂度，显然，这个一次遍历加双指针的方法是非常高效的。

这次面试给我的最大感受是，字节跳动的面试非常务实，注重对问题本质的理解和高效解决问题的能力。它不一定用最难的题来“劝退”你，但一定会通过题目考察你的思维深度和代码实现能力。对于正在求职路上的朋友们，我的建议是，刷题不仅仅是记住答案，更重要的是理解每种数据结构和算法思想背后的逻辑和适用场景。希望这次的真题分享，能为你冲向心仪大厂的道路上，点亮一盏小小的路灯。

本文的作者 石老师，在这里给大家打个硬广，csoahelp.com每日分享北美大厂面经，小红书也有更新，我们还提供种类多样的收费服务协助您进入北美科技大厂，有意向的微信扫码联系我，或者也可以通过其他方式联系我