TikTok 面试真题:两道经典算法题,考察数组操作与汇率转换 | TikTok Coding Interview Questions

最近我们收到了一组 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

查询:

QueryResult
USD → EUR0.9
USD → JPY144
JPY → USD1 / 144
GBP → JPY180
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代写等服务助您早日上岸~

Leave a Reply

Your email address will not be published. Required fields are marked *