Stripe OA 面试真题解析：按属性匹配、加权匹配与间接关联商户

题目描述

Part 1 直接匹配：给定目标商户，返回所有与它共享至少一个相同属性值的商户。Part 2 加权匹配：按共享属性数量或置信度给匹配结果打分排序。Part 3 间接关联：两个商户即使不共享属性，只要通过若干次共享属性形成链，也算关联。

解题思路

直接匹配用「属性值 → 商户集合」的倒排索引，一次查表即可。间接关联是图连通性：把「共享同一属性值」的两两商户连边，用并查集把同一连通分量的商户归为一组。加权匹配则在直接匹配基础上按共享属性数排序。

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.p[ra] = rb

def indirect_groups(attr_values):
    groups = {}
    for mid, attrs in enumerate(attr_values):
        for a in attrs:
            groups.setdefault(a, []).append(mid)
    dsu = DSU(len(attr_values))
    for mids in groups.values():
        for i in range(1, len(mids)):
            dsu.union(mids[0], mids[i])
    result = {}
    for mid in range(len(attr_values)):
        result.setdefault(dsu.find(mid), []).append(mid)
    return list(result.values())

复杂度与易错点

倒排索引构建 O(总属性数)，并查集操作近似 O(α(n))。注意同一商户重复出现的属性不要重复连边；Part 3 的「关联」是传递闭包，不能用一次共享属性的直接邻居代替。

FAQ

间接关联为什么不能只查直接邻居？

关联关系可传递：A 和 B 共享属性，B 和 C 共享属性，A 与 C 虽无共同属性也算关联，必须用并查集或 BFS 求连通分量。

参考来源

• LeetCode 721 — Accounts Merge
• LeetCode 947 — Most Stones Removed with Same Row or Column

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。