这是一道 TikTok 真实 Coding 面试题，主要考察贪心算法（Greedy Algorithm）以及回溯（Backtracking）的应用。
Original Question (English)
Given an integer n and a set of digits A, find the largest number strictly smaller than n that can be formed using only digits from A.
Digits can be reused multiple times.
Example:
Input:
- n = 23121
- A = {2, 4, 9}
Output: 22999
题目中文
给定一个整数 n 和一个数字集合 A，要求仅使用集合 A 中的数字，组成一个严格小于 n 的最大整数。
集合中的数字可以重复使用。
示例：
输入：n = 23121，A = {2, 4, 9}
输出：22999
Solution Approach（解题思路）
这道题的核心是贪心算法结合回溯。
从最高位开始，尽量选择集合中最大的合法数字。如果当前位选择的数字小于 n 对应位置的数字，后面的所有位置就可以直接填入集合中的最大数字。
以 23121 为例，第一位选择 2，第二位原本是 3，但集合中没有 3，因此选择小于 3 的最大数字 2。
此时前两位已经确定为 22，剩余三位全部填入最大的数字 9，最终得到 22999。
如果某一位无法找到合法数字，就需要回溯到前一位，尝试更小的数字。
如果无法构造相同位数的合法结果，还需要考虑使用更少位数的情况。
Key Takeaway
这道 TikTok 面试题看起来是简单的数字构造问题，实际需要处理贪心选择失败后的回溯，以及严格小于 n 的边界条件。
关键是找到第一个能够使结果小于 n 的位置，再将后续数字全部最大化。
CSOAHELP 持续整理真实科技公司面试题，也设计贴近业务场景的练习题，提供 Mock Interview、系统设计辅导和实时面试思路支持。
我们也有代面试，面试辅助，OA代写等服务助您早日上岸~
