最近硬刚了TikTok的一轮远程VO,过程还算顺利,希望能给正在求职路上的小伙伴们一些参考,特别是对字节(TikTok母公司)面试风格感兴趣的同学。这次面试经历感觉挺有代表性的,尤其是碰到的一道算法题,感觉是他们家常考的类型,这里重点分享一下。
面试官小哥上来先是常规地聊了聊项目,然后就直接进入了做题环节。题目直接贴在了共享文档里,这个在大厂面试中也算是标配了。
Question description
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries
, where queries[j] = [Cj, Dj]
represents the jth
query where you must find the answer for Cj / Dj = ?
.
Return the answers to all queries
. If a single answer cannot be determined, return -1.0
.
Note: The input is always valid. You may assume that evaluating the queries
will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations
are undefined, so the answer cannot be determined for them.
Input:
equations = [["a","b"],["b","c"]],
values = [2.0,3.0],
queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output:
[6.00000,0.50000,-1.00000,1.00000,-1.00000]
Explanation:
Given: a / b = 2.0, b / c = 3.0
queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
看到题目,我心里大概有了点数,这题有点图的味道。为了稳妥起见,我先跟面试官确认了一下:“咱们可以假设所有输入都是有效的,比如不会出现除以零或者其他无效值的情况对吧?” 面试官很干脆地回复说可以这么假设,这让我对接下来的思路更有把握。
核心思路是将变量关系视为一个图:变量是节点,A / B = val
意味着 A 到 B 有权重为 val
的边,B 到 A 则有权重 1/val
的边。求解 C / D
就变成了在图中找到从 C 到 D 的路径,并计算路径上权重的乘积。若无路径或变量不存在,则为 -1.0。
实现上,我先用字典构建图,然后对每个查询跑一次深度优先搜索 (DFS) 来找路径和计算结果,同时注意处理环路和节点不存在的情况。当起点和终点相同时,结果为1.0。
面试官在我阐述完思路和DFS框架后,追问了优化方案,特别是在查询量大的场景下。我提到了可以预处理(类似Floyd-Warshall)或者在查询过程中缓存已计算的结果,将新的直接关系也加入图中,用空间换时间,有点动态规划或记忆化的意思。
整个过程下来,感觉TikTok面试还是挺看重对算法基本功的考察,尤其是图相关的题目,以及候选人是否能清晰地表达自己的思考过程,并对方案的扩展性和优化有自己的想法。希望这次的面经能帮到大家,祝各位早日拿到心仪的Offer,顺利上岸!
本文的作者 石老师,在这里给大家打个硬广,csoahelp.com每日分享北美大厂面经,小红书也有更新,我们还提供种类多样的收费服务协助您进入北美科技大厂,有意向的微信扫码联系我,或者也可以通过其他方式联系我
