Meta OA 面试真题解析：Product of Array Except Self + Word Break All Combinations

Q1. Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Input: [4, 3, 2, 1]

Output: [6, 8, 12, 24]

Please solve it without using the division operator and in O(n).

Q2. Given a short string S and a dictionary D, find out all possible ways to split S using words in D.

Test examples:

S = 'abcd', D = ['a', 'b', 'ab', 'cd'] -> ['a-b-cd', 'ab-cd']
S = 'aaa', D = ['a'] -> ['a a a']
S = 'abcd', D = ['ab'] -> []
S = 'abcd', D = ['abcd'] -> ['abcd']

这组 Meta 面试题分别考察了数组前后缀乘积和字符串分词枚举。第一题经典做法是用两次线性扫描：先计算每个位置左侧乘积，再从右向左累乘右侧乘积，最终在不使用除法的前提下得到每个位置“除自身外的乘积”，时间复杂度 O(n)，额外空间可以优化到 O(1)（不计输出数组）。第二题本质是 Word Break 的变体，需要返回所有合法切分方式，通常用 DFS 回溯配合记忆化，或先做动态规划判断可达性，再搜索所有路径。