最近我们收到了一组 TikTok(字节跳动)Software Engineer 岗位的 Coding 面试真题,涉及两道算法题:Merge Sorted Arrays 和 Currency Exchange Rate Conversion。
这两道题分别考察数组双指针操作和图搜索算法。第一题重点是空间复杂度优化,第二题则要求候选人将实际业务场景抽象成图结构,并处理间接转换与反向转换。
Question 1: Merge Two Sorted Arrays In-Place
Original Question
Given two sorted arrays A and B, where A has enough empty space to hold B, merge B into A in sorted order without using extra space.
中文题目
给定两个已经排好序的数组 A 和 B,其中数组 A 预留了足够的空闲空间来容纳数组 B。
要求将 B 中的元素合并到 A 中,使最终数组仍然保持升序排列,并且不能使用额外的数组空间。
Example
Input:
- A = [1, 3, 5, 0, 0, 0]
- B = [2, 4, 6]
- A 中有效元素数量 m = 3
- B 中元素数量 n = 3
Output:
A = [1, 2, 3, 4, 5, 6]
解题思路
这道题属于经典的双指针问题。
最直接的方案是创建一个新数组,依次比较 A 和 B 中的元素并完成合并。但题目明确要求不使用额外空间,因此这种方法不满足要求。
更合适的方案是从后往前进行合并。
由于 A 的末尾已经预留空间,可以使用三个指针:
- i:指向 A 的最后一个有效元素
- j:指向 B 的最后一个元素
- k:指向 A 的最后一个位置
比较 A[i] 和 B[j],把较大的元素放入 A[k],然后移动对应指针。
重复这个过程,直到 B 中所有元素都完成合并。
由于每次都是从数组末尾填充,原有的有效元素不会被尚未处理的数据覆盖。
Complexity Analysis
Time Complexity: O(m + n)
Space Complexity: O(1)
面试官主要关注候选人能否利用已有空间完成原地操作,以及是否能够正确处理边界情况。
例如 A 为空、B 为空、两个数组存在重复元素,或者 A 中所有有效元素都大于 B 中元素时,算法都需要正常运行。
另外,数组末尾的 0 在示例中代表预留空间,不能简单依靠数值是否为 0 判断有效元素,必须明确有效长度 m。
Question 2: Currency Exchange Rate Conversion
Original Question
Given a list of exchange rates between currencies and a list of conversion queries, calculate the exchange rate for each query, including indirect and reverse conversions. Return -1 if no conversion path exists.
中文题目
给定一组货币之间的汇率关系,以及多个货币转换查询。
对于每个查询,需要计算两种货币之间的兑换汇率。
系统必须支持直接兑换、通过其他货币进行间接兑换,以及反向兑换。
如果两种货币之间不存在可行的转换路径,则返回 -1。
Example
已知汇率关系:
- USD → EUR = 0.9
- EUR → JPY = 160
- GBP → USD = 1.25
查询:
| Query | Result |
|---|---|
| USD → EUR | 0.9 |
| USD → JPY | 144 |
| JPY → USD | 1 / 144 |
| GBP → JPY | 180 |
| AUD → JPY | -1 |
例如 USD → JPY 可以通过 EUR 进行间接转换:
USD → EUR → JPY
最终汇率为 0.9 × 160 = 144。
解题思路
这道题的核心在于将货币兑换关系建模成带权图(Weighted Graph)。
每一种货币代表图中的一个节点,每条汇率关系代表两个节点之间的边,汇率数值作为边的权重。
例如 USD → EUR = 0.9,可以建立两条有向边:
- USD → EUR,权重 0.9
- EUR → USD,权重 1 / 0.9
这样就同时支持了正向和反向兑换。
完成图结构构建之后,可以使用 DFS 或 BFS 查找两种货币之间的转换路径。
在搜索过程中,维护当前路径上所有汇率的乘积。一旦找到目标货币,就返回累计汇率。
如果搜索结束后仍然无法找到目标,则返回 -1。
需要使用 visited 集合记录已经访问过的货币,避免在双向兑换关系中出现循环搜索。
Complexity Analysis
假设 V 为货币数量,E 为汇率关系数量,Q 为查询数量:
- Building Graph: O(V + E)
- Each Query: O(V + E)
- Total Time: O(V + E + Q × (V + E))
- Graph Space: O(V + E)
这里假设提供的汇率关系一致,不存在相互矛盾的兑换路径。
对于正在准备 TikTok Software Engineer 面试的候选人,建议重点复习 Two Pointers、Array Manipulation、Graph Traversal、DFS、BFS 以及 Weighted Graph 等知识点。
更多 TikTok 真实面试题与 AI 模拟面试
CSOAHelp 持续整理 TikTok、Google、Amazon、Meta、Stripe 等科技公司的真实 Coding 面试题,帮助候选人了解最新面试考察方向。
通过我们的真题训练与 AI 模拟面试系统,可以进行算法练习、模拟追问和解题复盘,提前熟悉真实面试流程。
我们也有代面试,面试辅助,OA代写等服务助您早日上岸~

