Anthropic Fellows OA 面试真题解析：Extremely Randomized Trees（极随机树）

You are given a partially implemented algorithm for Extremely Randomized Trees, a decision-tree ensemble method introduced by Geurts et al. (2006).

Your task is to debug the implementation so that all unit tests pass.

The algorithm is described in the source code of trees.py. Unit tests are provided in test_trees.py. You are encouraged to read the tests and write additional tests, but do not modify the existing tests or docstrings.

You should not hack the tests by hardcoding checks for certain input data or overriding assertion methods to always pass.

Permitted resources:

• You may web search and consult documentation.
• The NumPy documentation may be useful.

You may not use or refer to:

• any other 3rd-party libraries such as scikit-learn
• existing decision tree implementations
• AI assistance (except that AI overview search results in Google are permitted)

Debugging methods:

• You may use print statements, the REPL, and terminal-based debuggers.
• Do not use the graphical debugger.
• To use breakpoints with pdb, add breakpoint() to your source code and run a specific test with pytest -k test_name --pdb, or run all tests with pytest --pdb.
• The RUN button will hang if it hits a breakpoint.
• To use the REPL, run ipython in the terminal.

Hint: all test cases are of equal point value, but test_small_features and test_ensemble are the most difficult, so you may want to leave them until the end.

Time limit: 30 seconds
Memory limit: 4g

这道题考查的是极随机树（Extremely Randomized Trees）/ 随机森林风格的分类器实现调试。核心思路是检查决策树的递归建树、特征随机采样、阈值切分、叶子节点多数表决，以及集成模型中多棵树的训练与预测输出是否符合测试约定。解题时要特别注意：当样本数不足、特征全相同或切分后左右子集为空时，应正确返回叶子；同时要保证 `predict_single` 按“严格小于走左边，否则走右边”的规则遍历树。整体属于 NumPy + 递归 + 随机化算法的综合调试题，重点是修复边界条件和索引逻辑，而不是重新实现模型。