Amazon VO 两轮 Coding：会议室安排 + 算术表达式计算（双栈）

两轮 Coding 分享，BQ 就不展开了。

第 1 题：会议室安排

题目：给一堆会议的开始和结束时间，问最少需要几个会议室才能安排下所有会议，重叠的会议必须用不同的会议室。

解题思路：

1. 把所有会议按开始时间排序，按时间顺序一个个处理。
2. 用最小堆存当前正在使用的会议室的结束时间，堆顶就是最早结束的会议。
3. 遍历每个会议：如果堆顶的结束时间早于或等于当前会议的开始时间，说明这个会议室空了，可以复用；否则就要新开一个会议室。
4. 把当前会议的结束时间放进堆里，记录堆的最大大小，这个最大值就是最少需要的会议室数量。

面试官很看重代码的清晰度和时间复杂度分析，整个过程很耐心，会引导思考。建议面试前多练习类似的区间问题，熟悉最小堆的应用。

代码可以参考 Google Intern VO：Meeting Rooms II。

第 2 题：算术表达式计算

题目：实现一个函数，计算一个包含非负整数和运算符（+、-、*、/、()）的算术表达式字符串。表达式可能包含空格，输入保证合法。按正常的算术规则计算，除法向零取整，返回整数结果。

解题思路：

1. 用两个栈，一个存数字，一个存运算符。
2. 遍历字符串：
   • 遇到数字：解析出完整的多位数，压入数字栈。
   • 遇到运算符：和运算符栈顶比较优先级。如果当前运算符的优先级低于或等于栈顶，就先计算栈顶的运算符，把结果压回数字栈；然后再把当前运算符压栈。
   • 遇到左括号：压入运算符栈。
   • 遇到右括号：一直计算，直到遇到左括号为止。
3. 最后把两个栈里剩下的内容都算完，剩下的数字就是结果。

def calculate(s):
    nums, ops = [], []
    prec = {"+": 1, "-": 1, "*": 2, "/": 2}

    def apply():
        b, a, op = nums.pop(), nums.pop(), ops.pop()
        if op == "+":
            nums.append(a + b)
        elif op == "-":
            nums.append(a - b)
        elif op == "*":
            nums.append(a * b)
        else:                                   # 向零取整
            q = abs(a) // abs(b)
            nums.append(q if (a >= 0) == (b > 0) else -q)

    i = 0
    while i < len(s):
        c = s[i]
        if c.isdigit():
            j = i
            while j < len(s) and s[j].isdigit():
                j += 1
            nums.append(int(s[i:j]))
            i = j
            continue
        if c == "(":
            ops.append(c)
        elif c == ")":
            while ops[-1] != "(":
                apply()
            ops.pop()
        elif c in prec:
            while ops and ops[-1] != "(" and prec[ops[-1]] >= prec[c]:
                apply()
            ops.append(c)
        i += 1                                  # 空格直接跳过
    while ops:
        apply()
    return nums[-1]

这题有点难度，主要难在运算符优先级和括号嵌套。面试官会关注边界情况的处理，比如空格、多位数的解析等。建议面试前多练习字符串处理和栈的应用。