Katkat
Back

Compute meeting rooms and evaluate RPN

BloombergSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests interval management using sorting and heap-like logic for resource allocation, combined with stack manipulation to evaluate mathematical expressions.

Part 1: Meeting Rooms

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required to hold all meetings.

Example: Input: [[0, 30], [5, 10], [15, 20]] Output: 2 Explanation: Meeting 1 occupies one room [0, 30]. Meeting 2 and 3 occur during this time but can share a second room.

Part 2: RPN Evaluation

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN). Valid operators are +, -, *, and /. Each operand may be an integer or another expression. Division between two integers should truncate toward zero.

Example: Input: tokens = ["2", "1", "+", "3", "*"] Output: 9 Explanation: ((2 + 1) * 3) = 9

Constraints

  • For Part 1: 1 <= intervals.length <= 10^4.
  • For Part 2: 1 <= tokens.length <= 10^4, tokens consist of integers or operators.

Hints

Hint 1

For Part 1, consider sorting the meetings by start time and tracking end times using a min-heap to see if a room becomes free.

Hint 2

For Part 2, remember that RPN inherently follows a Last-In-First-Out pattern, which is the signature use case for a stack.

Hint 3

When implementing the RPN evaluator, ensure you pop the 'right' operand before the 'left' operand for subtraction and division operations.

Follow-up questions

  • How would your approach for meeting rooms change if we wanted to find the total time duration that at least one room was occupied?
  • What would happen to the RPN evaluator if we introduced a modulo operator or a power operator?
  • Can you optimize the space complexity of the meeting rooms problem if the input intervals are already sorted by start time?