Legiana, a Lyft user, is reviewing his rides from a specific day. However, the application is not retrieving the complete data for the rides, and they are not listed in the correct order. Can you help resolve this issue?
You are given a list of routes, where each route is represented as a pair of cities [start, end]. Each route connects two cities directly. Your task is to reconstruct the entire route from the given segments so that the route is continuous and includes all the segments exactly once.
Input
A list of lists named routes, where each element is a list of two strings [start, end] representing a direct route from start to end.
Output
A single string representing the reconstructed route with cities joined by " -> ".
Example 1:
Input: [["SFO", "LA"], ["NYC", "SFO"], ["OAK", "NYC"]]
Output: "OAK -> NYC -> SFO -> LA"
Example 2:
Input: [["A", "E"], ["M", "B"], ["C", "A"], ["B", "C"]]
Output: "M -> B -> C -> A -> E"
Example 3:
Input: [["Taco Bell", "Shake Shack"], ["Starbucks", "Wingstop"], ["Wingstop", "Taco Bell"]]
Output: "Starbucks -> Wingstop -> Taco Bell -> Shake Shack"
Example 4:
Input: [["NYC", "NJ"]]
Output: "NYC -> NJ"
面试官给了一个业务背景，Lyft 的订单顺序出现问题，需要把用户一天的行程拼回去。
候选人先把题目抽象成结构问题，把每一段 [start, end] 看成一条有向边。
“是否保证所有片段能拼成一条完整路径？”
“每一段只能使用一次吗？”
面试官确认条件成立。
问题模型在这一刻已经确定下来，就是一条链式路径重建。
一个很关键的规律：
路径中只有一个真正的起点，这个点只会出现在 start，从不出现在 end。
举例说明：
OAK → NYC
NYC → SFO
SFO → LA
OAK 从来没有被指向，这个就是起点。
思路自然展开成三个动作：
找到起点
建立映射关系
一路往后串起来
整个过程非常接近“链表拼接”。
候选人这样描述自己的方案：
“我会用一个哈希表记录 start 到 end 的映射，再用一个集合记录所有 end。
然后找到那个没有出现在 end 里的 start，当作起点。
从起点开始不断查映射，把路径串起来。”
面试官认可这个思路。
写代码时的行为描述
候选人写代码的过程很流畅。
他先快速构建了映射表，同时把所有终点放进集合。
接着扫一遍所有起点，找出那个唯一的起点。
随后从起点出发，一步一步往后走，每走一步就把城市加入结果。
最后把整个路径拼接成字符串输出。
整个实现过程没有额外复杂结构，逻辑非常干净。
复杂度说明
候选人主动补充：
时间复杂度是 O(n)，每条路径只处理一次
空间复杂度是 O(n)，用于存储映射关系
面试官记录了这一点。
Follow-up 继续深入
面试官继续扩展场景：
现在这些路径不保证连成一条，有可能是多条独立路线，需要把所有路线都还原出来。
候选人继续沿用原有思路：
找到所有起点
从每个起点出发生成一条路径
收集所有结果
面试官补充了一个要求：
结果需要排序
优先按路径长度（长的在前）
长度相同按起点字母顺序
候选人把路径结果收集后统一排序，逻辑依然清晰。
如果这是你在面试现场
你会发现一个现实情况：
题目本身不难，真正难的是在压力下快速抓住关键点。
很多候选人会卡在：
不知道该从哪里入手
或者思路对了，说不清楚
或者写的时候节奏混乱
这也是为什么越来越多人开始用 面试辅助。
我们也有代面试，面试辅助，OA代写等服务助您早日上岸~
