Snowflake Kanban：左右箭头移动、目标列置底与 10 万任务

题目重点：Fullstack 题目要求 React+TypeScript 小看板、无拖拽、越界箭头隐藏、移动任务置底，并追问 10 万任务；本文拆状态模型和渲染成本。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练版三列 todo/doing/done，任务 ID 唯一，一次点击只左右移动一列；“置底”指移动后追加到目标列的当前末尾，之后其他任务移动进来会排在它后面。
展示代码实现独立 BoardStore，React 组件可通过 useSyncExternalStore(store.subscribe,store.getSnapshot) 订阅版本号；完整 JSX、键盘交互和后端保存未在题目详细说明。
任务标题/内容另由 id→task 资料表提供，列顺序单独维护；隐藏越界箭头也需给键盘用户可理解的焦点行为。

解题路线

把 taskId→节点索引与每列双向链表分开，节点持 prev/next/status，列持 head/tail；左右移动时 O(1) 从旧列摘下并追加到新列尾。
canMove 根据当前列序号决定按钮是否显示，点击时再次检查，避免状态变化后的陈旧按钮执行非法移动。
状态变更增 version 并通知监听者；React 组件通过稳定的订阅函数拿快照，再读取可见列任务。不要把 10 万条原数组每次 filter 三遍。
100k 任务时仅渲染视口及 overscan；但示例链表的 list(status,offset,limit) 为到 offset 需 O(offset)，大偏移频繁滚动要加按位置索引、块链/分页或虚拟列表库维护的索引。
用独立数组模型随机移动 10,000 次，核箭头合法性、每列顺序、置底与通知版本；再测试首列/末列和唯一 ID。

手动走一遍

todo=[A,B]、doing=[C]、done=[]。点击 B 的右箭头后，todo=[A]、doing=[C,B]；再把 A 右移，doing=[C,B,A]。B 在其移动时被放在底部，后来 A 进来后 A 成为新的底部。done 列右箭头隐藏。

TypeScript 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

type Status = "todo" | "doing" | "done";
type Direction = -1 | 1;
const STATUSES: Status[] = ["todo", "doing", "done"];

type TaskNode = { id: string; status: Status; prev: string | null; next: string | null };
type Column = { head: string | null; tail: string | null; count: number };

export class BoardStore {
  private nodes = new Map<string, TaskNode>();
  private columns: Record<Status, Column> = {
    todo: { head: null, tail: null, count: 0 },
    doing: { head: null, tail: null, count: 0 },
    done: { head: null, tail: null, count: 0 },
  };
  private version = 0;
  private listeners = new Set<() => void>();

  constructor(tasks: Array<{ id: string; status: Status }>) {
    for (const task of tasks) {
      if (this.nodes.has(task.id)) throw new Error("duplicate task id");
      const node: TaskNode = { ...task, prev: null, next: null };
      this.nodes.set(task.id, node);
      this.append(node, task.status);
    }
  }

  subscribe = (listener: () => void): (() => void) => {
    this.listeners.add(listener);
    return () => this.listeners.delete(listener);
  };
  getSnapshot = (): number => this.version;

  canMove(id: string, direction: Direction): boolean {
    const node = this.nodes.get(id);
    if (!node) throw new Error("unknown task");
    const nextIndex = STATUSES.indexOf(node.status) + direction;
    return nextIndex >= 0 && nextIndex < STATUSES.length;
  }

  move(id: string, direction: Direction): boolean {
    if (!this.canMove(id, direction)) return false;
    const node = this.nodes.get(id)!;
    const destination = STATUSES[STATUSES.indexOf(node.status) + direction];
    this.detach(node);
    this.append(node, destination); // changed task is always at bottom
    this.version++;
    for (const listener of this.listeners) listener();
    return true;
  }

  list(status: Status, offset = 0, limit = Infinity): string[] {
    if (offset < 0 || limit < 0) throw new Error("invalid pagination");
    const result: string[] = [];
    let id = this.columns[status].head;
    while (id !== null && offset-- > 0) id = this.nodes.get(id)!.next;
    while (id !== null && result.length < limit) {
      result.push(id);
      id = this.nodes.get(id)!.next;
    }
    return result;
  }

  private detach(node: TaskNode): void {
    const column = this.columns[node.status];
    if (node.prev !== null) this.nodes.get(node.prev)!.next = node.next;
    else column.head = node.next;
    if (node.next !== null) this.nodes.get(node.next)!.prev = node.prev;
    else column.tail = node.prev;
    column.count--;
    node.prev = node.next = null;
  }

  private append(node: TaskNode, status: Status): void {
    const column = this.columns[status];
    node.status = status;
    node.prev = column.tail;
    node.next = null;
    if (column.tail !== null) this.nodes.get(column.tail)!.next = node.id;
    else column.head = node.id;
    column.tail = node.id;
    column.count++;
  }
}

复杂度

任务数 N，双向链表节点和 id Map O(N) 空间；canMove/move O(1) 状态操作，通知 L 个订阅者 O(L)。当前 list(offset,limit) 为 O(offset+limit)，若渲染整个列仍 O(列长)；10 万任务优化必须同时处理视口渲染和大偏移索引。

易错点与追问

容易失分的边界

移动时每列都对全部 tasks 做 filter，单次操作与渲染随 10 万条增长。
只更新 status 不维护列内顺序，无法保证移动任务置底。
越界箭头仅视觉灰掉但仍可触发，或无键盘焦点语义。
声称虚拟滚动本身让从链表读取第 90,000 项也变 O(1)。
外部可变 store 更新后不通知 React，界面不重绘。

继续深挖

按列分页从服务端加载时，移动任务的顺序键如何分配与持久化？
若允许拖拽到列中任意位置，链表和可视索引怎样变？
多人同时移动同任务，如何做版本冲突或最终一致合并？
10 万任务但只展示筛选结果时，索引如何维护而不全量 filter？