上周刚面完Centific，感觉他家面试风格还挺务实的，题目出得也很有意思，赶紧趁热把面经写下来，主要是分享一下其中一道让我印象深刻的算法题，希望能给后面要面他家或者类似科技厂的小伙伴们一点参考。

讲真，每次面试前那几天，心情都跟过山车似的，既期待又有点小焦虑。这次约的是下午，我提前把咖啡续上，深呼吸了好几次，才点进了会议链接。面试官是个小哥，口音听着挺舒服，寒暄几句后，屏幕一共享，题目就来了。

面试官给出的问题是这样的：

`You are driving a vehicle that has to pass several traffic lights. You are given:

1. distances: An array of integers where distances[i] is the distance from your starting position to the i-th traffic light. These are strictly increasing.
2. clock: An array of integers where clock[i] is the time duration for which the i-th traffic light stays red, and also the time it stays green. So, a full cycle for light i is 2 * clock[i]. At time 0, all lights have just turned red. Light i will be red from [0, clock[i]), green from [clock[i], 2clock[i]), red from [2clock[i], 3*clock[i]), and so on.
3. max_time: An integer representing the maximum allowed time to reach the last traffic light.

You must travel at a constant velocity. Find out if it's possible to choose such a constant velocity that allows you to pass all traffic lights when they are green and reach the final traffic light (the one at distances[distances.length - 1]) at or before max_time. If it is possible, return true. Otherwise, return false.`

他给了一个例子：distances = [10, 17, 25], clock = [3, 5, 10], max_time = 1200.

看到这个题，我心里第一反应是，这不就是规划个速度一路绿灯嘛。但细想一下，这个“恒定速度”是关键，而且速度的选择会直接影响到达每个红绿灯的时间点。我先跟面试官确认了几个细节，比如是不是只要找到任何一个可行的速度就行，他说对，只要存在这么一个速度能满足条件就行。

我的思路是这样的：首先得有个办法判断，在某个特定的到达时间，某个红绿灯是不是绿灯。这个不难，根据clock的定义，用取余运算就能搞定每个灯在特定到达时间的颜色。然后，如果我选定了一个速度，我就能算出到达每个红绿灯的时间，进而检查在这些时间点，灯是不是绿的。

最核心的问题就变成了，怎么找到那个“天选之速”呢？总不能瞎猜吧。我琢磨着，速度肯定不能太慢，慢到最后一个灯都超时了还到不了；也不能太快，快到第一个灯还没变绿你就冲过去了。所以，可以先大致匡算出速度的一个合理上下限。上限大概是根据第一个灯的距离和它的红灯时长来定，下限则是根据最远那个灯的距离和max_time来定。

有了这个大致的速度区间，接下来的挑战就是在这个区间里找到那个能让你一路绿灯的速度。我想的是，这个可行的速度区间可能不是连续的，也就是说，可能某些小段的速度可以，其他就不行。所以不能简单地只试探区间的中间值。得有一种方法去系统地、更细致地探索这个速度区间，看看是否存在至少一个速度能让所有红绿灯都恰好是绿灯。我的想法是不断地把当前的速度搜索范围切分，然后去测试这些切分点附近的速度是否可行，直到找到一个解，或者确信在这个范围内找不到为止。

写代码的过程中，面试官小哥还挺耐心。中间我本地测试的时候，似乎出了点小问题，他还提示我说：“你现在的error是什么, 我这边能run出来”，又问“你是不是indentation哪里有问题”。果然，调整了一下缩进和函数调用的位置，就跑通了。他还给了另一个例子让我测试，确保逻辑的鲁棒性。整个过程感觉更像是一起解决一个实际问题，而不是单纯的拷问。

面完感觉Centific这道题主要考察的是问题分解能力，以及在约束条件下寻找可行解的系统性思维。题目本身不涉及什么特别偏僻的算法，但要把各种边界条件和判断逻辑理清楚还是需要费点脑筋的。

总的来说，这次Centific的面试体验还不错，题目质量也挺好。希望这点面经能帮到正在求职路上的各位，祝大家都能顺利拿到心仪的Offer！刷题不易，共勉！

本文的作者 石老师，在这里给大家打个硬广，csoahelp.com每日分享北美大厂面经，小红书也有更新，我们还提供种类多样的收费服务协助您进入北美科技大厂，有意向的微信扫码联系我，或者也可以通过其他方式联系我