# Uber SQL Interview Question: Detect Circular Routes Using Recursive CTE ## Метаданные - **Канал:** Learn at Knowstar - **YouTube:** https://www.youtube.com/watch?v=QBiNjEweW8Y ## Содержание ### [0:00](https://www.youtube.com/watch?v=QBiNjEweW8Y) Segment 1 (00:00 - 05:00) Imagine you are an Uber driver in Chicago. You pick up a passenger and drive to New York. From New York, you get another ride to Boston. And from Boston, you get a ride back to Chicago. You just completed a circular route. Today, we're going to write a query to detect these circular routes automatically using SQL. Here's the problem statement. Uber has a table called roots. Each row represents a direct route between two cities. Your job is to find circular routes. A circular route means you start from a city, travel through a one or more cities, and eventually return to the starting city. Your output should show the starting city and the full circular path. For example, Chicago, New York, Boston, Chicago. This is a valid circular route. This exact type of problem detecting cycles in a graph is asked in many fang interviews. So we are going to use a recursive CTE to design our solution. We will start by designing the anchor part of the recursive CTE which is simply picking up the source the destination city identifying the source city as the start city and then creating a path from the source to the direct destination and back to the start city. So source city concatenated with we are going to use arrows to make it clear and this has to be concatenated with the destination city and we have to be mindful of casting it explicitly as well max because we're going to build a long concatenated string as the path. So let's just execute this and you will see that it's a simple path where your source city is simply concatenated with the destination city. So the direct first connection from source to the destination. Now we have to build on or extend this path to create a full cycle from the start traversing through the cities and back to the source city. So let's frame a structure of the recursive CTE call it as root path and this is the anchor part of the CTE and then we have to write the recursive part. So we use a union all to define a CD the recursive part and for the recursive part we are going to call upon our CTD root parts call it SRB and going to join it with the root table on RP destination city is equal to roots dots source city because now we are extending the path. So this anchor part for example let's take the example of Chicago New York the anchor query the first iteration would have created the direct path Chicago to New York. Now when this iteration will run what will happen is it will extend the path by looking for New York as a source city in the roots table. And what we will pull in our select query is the source city from the recursive call of the CTE the destination city from the roots table and we want to retain the start city again from the recursive call of the CDE. And next we are going to extend a path again. So cast the path from the previous iteration. So RP dot path concatenated again with arrows with the destination city from the current iteration. Again cast it as white max. So now a new path becomes Chicago, New York, Boston. Now for the next iteration it should return back to Chicago. So Chicago, New York, Boston, Chicago and that is where our iterations should stop. So that is where we have to put that limit condition to stop this recursive step. So most of the times when we are writing this kind of query, we just put a wear clause and try to define a logic for the recursive loop to stop when the destination city from the roots table. So R dot destination city becomes equal to the source city. So when the destination is equal to the source then we would think that the loop has been completed and we should stop a recursive cycle. So we'll put a condition like at the destination city is not equal to RP do. CD and till this condition is true only till then this loop should run. So let's ### [5:00](https://www.youtube.com/watch?v=QBiNjEweW8Y&t=300s) Segment 2 (05:00 - 07:00) try putting this and let's do a select star from the recursive CD that we created and execute. And what you will see in the output that you never have a complete loop that got generated. So here you have Chicago, Boston, Chicago, New York, Boston, but it doesn't come back to Chicago. So we block the cycle where the root returns back to the start cityd. And to fix our query, what we're going to do is introduce another variable called is cycle. So in the anchor part, it's always going to be zero. So when this flag is one that means the cycle has been completed. So zero as a cycle for the angle part and for the recursive part we are going to put a logic saying case when R dot destination city is equal to RB dot start city then one else zero and as cycle. So this flag will help us identify when the cycle has been completed and at the same time it will not block this last iterative run of the recursive block. And in our where filter criteria instead of putting this check we we're going to check this flag from the previous iteration and check its value to be zero. So if in the previous iteration the cycle flag was zero that means we still need to continue this cycle and execute this recursive block to complete the cycle. Now if you execute this and look at the results you will see that when your cycle is completed your flag is set to one. So to identify only the completed cycles we can finally filter on our last select query using this flag is cycle is equal to 1 which will give you the complete circular roots detecting the whole circular path. If you want more fang level SQL problems like this, don't forget to check out all the videos of a Fang SQL boot camp and subscribe for more advanced equal interview training. See you in the next video. --- *Источник: https://ekstraktznaniy.ru/video/44489*