字节VO面经:一道图论题带你摸清TikTok面试套路 -TikTok面经 -大厂攻略 -求职分享 -TikTok Interview -ByteDance Coding

最近硬刚了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每日分享北美大厂面经,小红书也有更新,我们还提供种类多样的收费服务协助您进入北美科技大厂,有意向的微信扫码联系我,或者也可以通过其他方式联系我

Leave a Reply

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