Amazon VO 面试真题解析：Oncall Shifts 与 Cartesian Product 组合生成

Oncall shifts of people with start and end time

Name | Start | End
Adam | 10 | 100
Ben | 50 | 70
Cathy | 150 | 300
Diane | 60 | 120

We give a start and end time; we want to know who are oncall during that time period.

Output:

Start | End | Names
10 | 50 | Adam
50 | 60 | Adam, Ben
60 | 70 | Adam, Ben, Diane
70 | 100 | Adam, Diane
100 | 120 | Diane
150 | 300 | Cathy

Write a function that, given a jagged matrix as input, generates all combinations containing 1 element from each inner list in the input matrix.

(i.e. Python’s itertools.product)

For example:

input = [["A", "B", "C"],
  ["X", "Y"],
  ["1", "2"],
]

Result:

[
  "A-X-1",
  "A-X-2",
  "A-Y-1",
  "A-Y-2",
  "B-X-1",
  "B-X-2",
  "B-Y-1",
  "B-Y-2",
]

Another example with token order [2, 1, 0]:

1-X-A
2-X-A
1-Y-A
2-Y-A
1-X-B
2-X-B
1-Y-B
2-Y-B

这道题包含两个典型的面试思路：第一部分是区间扫描，给定每个人的 oncall 起止时间后，把所有时间点按边界排序，利用扫描线或事件合并找出每个时间段内同时在线的人；第二部分是对 jagged matrix 做笛卡尔积，也就是从每个子数组中各取一个元素，生成所有组合，顺序与输入维度顺序有关。前者考察区间合并、边界处理和排序，后者考察回溯 / 递归或迭代式组合生成，适合用深度优先搜索逐层扩展结果。