Solve meeting scheduling and robot cleaning tasks
Company: Google
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two independent coding problems.
---
### Problem 1: Prioritized Meeting Scheduling
You are asked to schedule meetings in a single meeting room.
You are given an array of meeting requests. Each request is represented as a tuple:
- `start`: integer start time (inclusive)
- `end`: integer end time (exclusive), with `end > start`
- `priority`: an integer representing the importance / value of that meeting
No two meetings can overlap in time in the single room. Your goal is to choose a subset of **non-overlapping** meetings to **maximize the sum of priorities**.
Write a function with the following signature (language-agnostic):
```text
int maxTotalPriority(Meeting[] meetings)
```
that returns the maximum possible total priority.
**Example**
Input:
```text
meetings = [
(1, 3, 4),
(2, 4, 3),
(3, 5, 2),
(0, 6, 7)
]
```
One optimal schedule is to pick meetings `(1,3,4)` and `(3,5,2)` for a total priority of `4 + 2 = 6`.
Another choice, `(0,6,7)`, has total priority `7`, which is better, so the answer is `7`.
**Constraints**
- `1 <= n <= 2 * 10^5` where `n` is the number of meetings
- `0 <= start < end <= 10^9`
- `-10^4 <= priority <= 10^4` (priorities can be non‑positive; you may choose to skip such meetings)
- Time complexity should be **O(n log n)** or better.
- You may assume `meetings` is given as a list/array in arbitrary order.
Describe the algorithm and then implement the function.
---
### Problem 2: Robot Room Cleaning on an Unknown Grid
You are controlling a vacuum cleaning robot in a 2D grid room. The room is divided into 1x1 cells. Each cell is either **empty** or **blocked**. The robot:
- Starts on an **empty** cell in an **unknown** position in this room.
- Does **not** know the layout of the room in advance.
- Only knows about the cell it is currently in and whether the cell in front of it is blocked when it tries to move.
You are given the following interface:
```text
interface Robot {
// returns true if the cell in front is open and the robot moves into the cell.
// returns false if the cell in front is blocked and the robot stays in the current cell.
boolean move();
// robot will stay in the same cell, but turn 90 degrees to the left.
void turnLeft();
// robot will stay in the same cell, but turn 90 degrees to the right.
void turnRight();
// clean the current cell.
void clean();
}
```
The robot is initially facing **up** (towards negative y direction in some internal coordinate system you choose).
You must implement a function:
```text
void cleanRoom(Robot robot)
```
that makes the robot **clean all reachable empty cells**. You **cannot**:
- Directly access the room grid or its dimensions.
- Track the robot's absolute position from the environment; you must build your own coordinate system relative to the starting cell.
You **can**:
- Maintain an internal set of visited coordinates in your own coordinate system (e.g., treat the starting cell as `(0,0)`).
- Move, turn, and clean using only the provided API.
**Constraints and assumptions**
- The number of reachable empty cells is at most 200.
- The room is bounded (finite) but shape and size are unknown.
- The robot must eventually stop after all reachable cells have been cleaned (no infinite loops).
Design an algorithm and implement `cleanRoom(Robot robot)` to guarantee that all reachable empty cells are cleaned.
Quick Answer: The first problem evaluates algorithmic optimization and interval scheduling concepts—specifically reasoning about selecting non‑overlapping intervals to maximize aggregate priority under time constraints—while the second evaluates exploration, stateful search and backtracking skills for traversing an unknown grid via a limited robot API.