Figma 电话面试经验分享 | 系统设计 算法 结构化思维

Figma 电话面试经验分享 | 系统设计 算法 结构化思维

想要了解更多或获取我们的服务，欢迎添加微信 leetcode-king。

---

面试流程概览

职位：Backend Engineer
公司：Figma
面试环节：电话技术面试

• 核心问题：设计一个 文件系统权限管理 API
• 考察重点：
  • 树形结构遍历 (Tree Traversal)
  • 数据结构设计
  • 代码清晰度
  • 状态管理 (State Management)

---

题目解析：File System Permissions

问题描述：

1. 文件系统包含 3 类对象：
   • Team：包含多个 Folder 和 File，定义拥有权限的 user_ids。
   • Folder：可以包含子 Folder 和 File，继承上级 user_ids 权限。
   • File：只包含 user_ids。
2. 访问继承规则：
   • 如果 user_id 具有某个 团队/文件夹/文件 的访问权限，则它 自动继承所有子项的访问权限。
3. 要求实现 2 个 API：
   • init(teams, folders, files): 解析输入并构建权限管理系统。
   • get_fewest(user_id): 找出最少的 Team / Folder / File，使该 user_id 可以访问所有文件。

---

题目难点分析

1. 数据结构不直观：Team、Folder、File 彼此没有直接的关联，需要手动解析。
2. 权限继承逻辑复杂：访问权限要向下传递，意味着 需要构建树结构。
3. 高效查找最少权限集：要求返回最少的高层级节点，避免冗余。
4. 初始化函数 (init_function) 需要存储状态，但不能返回数据，意味着需要 全局存储结构。

---

解法思路

1. 解析数据，构建权限树

• 使用 字典 (dict) 存储 uuid -> 对象 的映射，方便访问。
• 递归遍历 Team -> Folder -> File，构建完整的权限树。
• 采用 Graph Adjacency List 结构：

  graph = {
    "Team1": ["Folder1", "Folder2"],
    "Folder1": ["File1", "File2"],
    "Folder2": ["Folder3"],
    "Folder3": []
  }
  user_permissions = {
    "Team1": {"userA"},
    "Folder1": {"userA"},
    "Folder3": {"userA"},
    "File1": {"userA"}
  }

• 继承权限：遍历整个树，将 parent 的 user_ids 继承给 child。

---

2. get_fewest(user_id) 逻辑

• 目标：找到最少的 Team / Folder / File，保证该 user_id 仍能访问所有需要的文件。
• 解法：
  • DFS / BFS 遍历 整个文件系统，记录 user_id 访问的所有 uuid。
  • 采用 贪心策略，从最高层级 (Team) 依次向下筛选，找出覆盖所有访问权限的最少集合。
  • 使用 Set 覆盖检查，确保选出的 Team / Folder / File 不会重复覆盖相同权限。

---

代码实现

class Team:
    def __init__(self, uuid, folder_ids, file_ids, user_ids):
        self.uuid = uuid
        self.folder_ids = folder_ids
        self.file_ids = file_ids
        self.user_ids = set(user_ids)

class Folder:
    def __init__(self, uuid, folder_ids, file_ids, user_ids):
        self.uuid = uuid
        self.folder_ids = folder_ids
        self.file_ids = file_ids
        self.user_ids = set(user_ids)

class File:
    def __init__(self, uuid, user_ids):
        self.uuid = uuid
        self.user_ids = set(user_ids)

# 全局存储结构
graph = {}
user_permissions = {}

def init_function(teams, folders, files):
    """ 初始化数据结构，构建文件系统权限树 """
    global graph, user_permissions

    # 1. 构建图结构
    graph.clear()
    user_permissions.clear()

    # 2. 解析 Teams
    for team in teams:
        graph[team.uuid] = team.folder_ids + team.file_ids
        user_permissions[team.uuid] = set(team.user_ids)

    # 3. 解析 Folders
    for folder in folders:
        graph[folder.uuid] = folder.folder_ids + folder.file_ids
        user_permissions[folder.uuid] = set(folder.user_ids)

    # 4. 解析 Files
    for file in files:
        graph[file.uuid] = []
        user_permissions[file.uuid] = set(file.user_ids)

    # 5. 继承权限
    def propagate_permissions(node, inherited_users):
        user_permissions[node] |= inherited_users
        for child in graph[node]:
            propagate_permissions(child, user_permissions[node])

    for team in teams:
        propagate_permissions(team.uuid, user_permissions[team.uuid])

def get_fewest(user_id):
    """ 找到最少的 Team / Folder / File，使 user_id 可以访问所有文件 """
    accessible_nodes = {node for node, users in user_permissions.items() if user_id in users}

    # 贪心策略：从高层级节点开始，寻找最小集合
    result_set = set()
    sorted_nodes = sorted(accessible_nodes, key=lambda x: -len(graph.get(x, [])))

    for node in sorted_nodes:
        if accessible_nodes.issubset(result_set):
            break
        if not any(child in result_set for child in graph.get(node, [])):
            result_set.add(node)

    return list(result_set)

# 示例测试
init_function(
    [Team("Team1", ["Folder1", "Folder2"], [], ["userA"])],
    [Folder("Folder1", [], ["File1", "File2"], ["userA"]),
     Folder("Folder2", ["Folder3"], [], []),
     Folder("Folder3", [], [], ["userA"])],
    [File("File1", ["userA"]), File("File2", [])]
)

print(get_fewest("userA"))  # 预期输出: ["Folder1", "Folder3"]
···