Amazon VO, Two Coding Rounds: Meeting Rooms + Arithmetic Expression Evaluation (Two Stacks)

Sharing the two coding rounds; I'll skip the behavioral part.

Q1: Meeting rooms

Problem: given meetings with start and end times, what's the minimum number of rooms needed so that overlapping meetings use different rooms?

Approach:

1. Sort meetings by start time and process them in order.
2. Keep a min-heap of the end times of rooms currently in use; the top is the meeting that ends earliest.
3. For each meeting: if the top's end time is at or before the current start, that room is free and can be reused; otherwise open a new room.
4. Push the current meeting's end time and track the heap's maximum size — that's the minimum number of rooms.

The interviewer cared a lot about clean code and complexity analysis, and was patient and helpful throughout. Practice similar interval problems and get comfortable with min-heaps before the interview.

For code, see Google Intern VO: Meeting Rooms II.

Q2: Arithmetic expression evaluation

Problem: implement a function that evaluates an arithmetic expression string with non-negative integers and the operators +, -, *, /, (). The expression may contain spaces and is guaranteed to be valid. Follow normal arithmetic rules, with division truncating toward zero, and return an integer.

Approach:

1. Use two stacks: one for numbers, one for operators.
2. Scan the string:
   • Digit: parse the full multi-digit number and push it onto the number stack.
   • Operator: compare precedence with the top of the operator stack. If the current operator's precedence is lower than or equal to the top's, evaluate the top operator first and push the result back; then push the current operator.
   • Opening parenthesis: push it onto the operator stack.
   • Closing parenthesis: keep evaluating until you reach the opening parenthesis.
3. Finally, evaluate whatever remains on the stacks; the last number is the result.

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:                                   # truncate toward zero
            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                                  # spaces are simply skipped
    while ops:
        apply()
    return nums[-1]

This one is tricky, mostly because of operator precedence and nested parentheses. The interviewer pays attention to edge cases such as spaces and multi-digit numbers. Practice string processing and stack problems beforehand.