在面试开发者职位时,我被问到这个问题.
任务：将航空路线存储在sql Server表写入查询中,将查找从A城市到B城市的所有路线,无需转移,即可进行一次或两次转移.例如你有路线：
| From | To ---------------------- Los Angeles London Los Angeles New York New York London Los Angeles Seattle Seattle Paris Paris London
你需要找到从洛杉矶到伦敦的所有路线.结果应该是这样的
Route ------------------------ Los Angeles->London Los Angeles->New York->London Los Angeles->Seattle->Paris->London
我的解决方案是这样的
select [From] + '->' + [To] as [Route] from Routes where [From] = 'Los Angeles' and [To] = 'London' union select r1.[From] + '->' + r1.[To] + '->' + r2.[To] as [Route] from Routes as r1 join Routes as r2 on r1.[To] = r2.[From] where r1.[From] = 'Los Angeles' and r2.[To] = 'London' union select r1.[From] + '->' + r1.[To] + '->' + r2.[To] + '->' + r3.[To] as [Route] from Routes as r1 join Routes as r2 on r1.[To] = r2.[From] join Routes as r3 on r2.[To] = r3.[From] where r1.[From] = 'Los Angeles' and r3.[To] = 'London'
工作但看起来不是很好,如果我们需要找到3,4,5或更多的转移路线,我们需要添加更多复杂选择的新工会.
对于这个特定的例子,这是很好的,因为人们对于超过2次转机的航班不感兴趣.但一般来说,我认为这个查询可以看起来更好.也许有人可以用更一般的查询来解决这个任务.谢谢.
解决方法
对,您为所有RDB提供了工作通用的sql解决方案.我看到你有一个提示 – sql Server.它支持可用于解决此任务的递归CTE.
with RoutesCTE as
(
select CAST([From] + '->' + [To] as nvarchar(max)) as [Route],0 as TransfersCount,[From],[To]
from Routes
union all
select r.[Route] + '->' + r1.[To],TransfersCount + 1,r.[From],r1.[To]
from RoutesCTE r
join Routes r1
on r.[To] = r1.[From]
and r1.[To] <> r.[From]
and PATINDEX('%'+r1.[To]+'%',r.[Route]) = 0
)
select [Route]
from RoutesCTE
where [From] = 'Los Angeles'
and [To] = 'London'
and TransfersCount <= 2
