Google 6月新鲜电面

给你一些"alphabet blocks"，每个block像筛子一个有6个面，每个面上有一个letter。函数inputs是一条message和一些blocks。

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求大米，谢谢！


补充内容 (2020-6-24 08:09):
原题：蠡口/discuss/interview-question/267985/google-interview-construct-a-word-using-dice

amgfan 发表于 2020/06/24 15:08:40
匈牙利算法是不是只能求一个最大匹配?

对的，只有一个。我看题主用的是 or，假设只需要一个解了

这个题的DP解法属于极度冷门的吧- -匈牙利算法,这都属于比较高级的算法实现了....面试估计能给出dfs+backtrack解法就可以了....

丑猪宝 发表于 2020-6-24 06:09
backtracking？map建立每个字母对应的block, traverse message每个字母，然后找有这个字母的block加入path ...

我也觉得要backtracking, dp不可行，因为每个block明确规定只能用一次。
这道题应该可以reduce成Maximum Matchings in Bipartite Graphs,polynomial的实现超级复杂，面试应该就给个O(n!)的。

二分图匹配？

Dp，外层for blocks里层for那个message，，可用一维dp滑动就行

backtracking？map建立每个字母对应的block, traverse message每个字母，然后找有这个字母的block加入path，以此类推不能使用已经使用过的block

jyyzzj 发表于 2020/06/24 05:58:39
Dp，外层for blocks里层for那个message，，可用一维dp滑动就行

你是说dynamic programming？具体怎么实现？或者我题目没解释清楚。比如上面那个例子，message是r和e两个字母。第三个block有r, 第一个block有e，所以返回第一个和第三个block，顺序无所谓。

Teddyw 发表于 2020-6-23 17:10
你是说dynamic programming？具体怎么实现？或者我题目没解释清楚。比如上面那个例子，message是r和e两个 ...

下午点开随便想的，首先是指数级应该不是最优解，而且得data range符合。
做法就先for block，然后for message的status，跟一维背包的滑动一样，保证每个item(block here)只用一次。
状压背包？哈哈

1. n = len(message)
   
2. dp = [[] for _ in range(1<<n)]
   . Χ
3. dp[0] = [[]]
   
4. for bid in range(len(blocks)):
   
5.     ndp = copy.deepcopy(dp)
   
6.     for status in range(1<<n):
   
7.         for i in range(n):
   
8.             if (1<<i) ^ status and message[i] in blocks[bid]:
   
9.                 ndp[(1<<i) ^ status] += [blks + [bid] for blks in dp[status]]
   
10.     dp = ndp
    
11. ans = [[*map(lambda i: blocks[i], blks)] for blks in dp[-1]]
    
12. print(ans)

复制代码

二分图建模：
分为 a，b 两类点，其中 a 类点表示 blocks，b 类点表示 message 上的每个字母。如果 block 存在 message 中的字母就从当前点向 b 类对应的点链接一条边。
之后求一个二分图最大匹配，如果匹配的结果等于 message 的长度，那么题目存在合法的解。那么就把每个 message 字母对应的 b 类点所对应的 a 类点对应的 block 加入答案就可以了。
匈牙利匹配算法时间复杂度 O(n^3)

rikoizz 发表于 2020-6-24 10:50
二分图建模：
分为 a，b 两类点，其中 a 类点表示 blocks，b 类点表示 message 上的每个字母。如果 block  ...

匈牙利算法有办法给出所有最大匹配的matching吗？还是只能给出达到最大匹配的一种matching？如果这个题目让给出所有的最大匹配，感觉也只能n!暴力枚举了把...

rikoizz 发表于 2020-6-24 10:50
二分图建模：
分为 a，b 两类点，其中 a 类点表示 blocks，b 类点表示 message 上的每个字母。如果 block  ...

匈牙利算法是不是只能求一个最大匹配?