Competitive Programmer Hit With the Hardest Algorithmic Problem
Billed as the hardest coding interview by Clément Mihailescu, an ex-Google employee now at AlgoExpert, a high school student, William Lin, the interviewee, was given an algorithmic problem you might have been given at Google. William is not just any high schooler though, he is a competitive programmer, who expectedly would do well. Quite enticing, you might say.
Interviewee Schools Interviewer
Turns out William, the interviewee, teaches Clément, the interviewer, about Kosaraju's algorithm, directed graph, strongly connected components, condensed graph and so on. The guy knows algorithms and makes lots of little drawings. Clément (the interviewer) follows along, doing his best to keep up and complement with his own knowledge where he can.
Viewers Discouraged and Disgusted
The bad part of this YouTube video and the reason I'm writing down my thoughts on this lies in the YouTube comments. Almost everyone is bummed out. Some say they got some of it, some say they got the gist of it, but the solution William came up with, basically flew over everyone's head. Many commenters tell you that flat out.
This video now has over 2 million views. A large part of the thousands of comments is people getting turned off to programming.
And that's so sad! Comment after comment was that they took a look, as I did, and got more and more discouraged as one concept after the next was introduced and explanations for those concepts were being given, for loops were being added and variable names with little meaning were used to feed an algorithm.
But Don't Give Up! There Is a Way
I'm a senior IT professional, who loves software development and has done his fair share of it, but I like to solve issues and work on projects that are beyond software: Understand the actual business problem, propose innovative solutions to solve it, hire the people, write the software, procure the hardware, configure it and ultimately deliver a solution that hopefully everyone is happy with, can run for years, scales and is easy to maintain.
Maybe that gives me a different perspective.
How did I take the onslaught of algorithms, graphs and explanations? I stopped watching. 😁 After William started drawing circles and arrows pointing at other circles and arrows, I gave up. Why? I wasn't getting anything out of it, plus thought I understood the problem (not true after my first round of thinking, but true after two more) and I wanted to give it a shot myself. I felt that unconsciously my gears had started turning trying to tackle the problem.
The Problem
The following are the input parameters from used in the mock interview.
let airports = ["BGI", "CDG", "DEL", "DOH", "DSM", "EWR", "EYW", "HND", "ICN", "JFK", "LGA",
"LHR", "ORD", "SAN", "SFO", "SIN", "TLV", "BUD"] // 18 airports, including the starting airport
let routes = [
["DSM", "ORD"],
["ORD", "BGI"],
["BGI", "LGA"],
["SIN", "CDG"],
["CDG", "SIN"],
["CDG", "BUD"],
["DEL", "DOH"],
["DEL", "CDG"],
["TLV", "DEL"],
["EWR", "HND"],
["HND", "ICN"],
["HND", "JFK"],
["ICN", "JFK"],
["JFK", "LGA"],
["EYW", "LHR"],
["LHR", "SFO"],
["SFO", "SAN"],
["SFO", "DSM"],
["SAN", "EYW"]
] // 19 one-way routes
let startingAirport = "LGA"
Use Logic (Not Algorithms)
What if I can solve this with pure logic? No learned algorithms. Just logic. What would I do if I was given the task to add the least amount of routes to an existing set of routes having to serve a list of airports from one given airport? What would I do manually at first?
Break Down the Problem by Asking Questions
What's the worst case?
There are no routes and I have to add a route to each airport. In this case, as the starting airport is one of 18 airports, I'd have to add one route from the starting airport to each other airport, so I would have to add 17 routes.
What's the best case?
There already is a route from the starting airport to each of the other airports, so I don't have to do anything, add 0 routes.
Somewhere in-between is the real situation, there are some routes connecting some of the airports. So, next question would be:
What would be the most beneficial route to add?
One to an airport that has routes to all other airports. Then I'd only have to add that single route and would be done. That airport is a hub, all I have to do is connect to that hub from the starting airport and I'm done.
The Solution
So, then, building on the answers to the above questions, this should work:
- Make a list of airports with all the airports they connect to. Generally airlines are based out of one or more "hubs", which connect to most of their destinations
- Find the biggest hub, the airport that will give me the most connections to other airports. That's my first connection. Then…
- Look for the next biggest hub, the airport that gives me the most connections to airports the first airport didn't connect me to.
- Add a connection to that airport and
- Move on to the next biggest hub and so on.
- And each time after adding a connection to a hub, check if I have connections to all airports, because if I do I'm done.
- Count the connections. Done!
Let's Try This Programmatically
I have to know, for each airport, what all the airports are that connect to it. Data structure-wise a map with the airport name as the key and an array of airports that connect to it as the value seems perfect. I’m going to use Swift, because I like it 😀.
This is how you declare and initialize the map (it’s called a dictionary in Swift), that is going to hold the list of all airports and all airports that they are reachable from.
var airportsReachableFrom = [String: [String]]()
1. Make an Airport List
Building the list actually takes the most code, so I broke it down into three parts:
- to make a list of airports and where they're reachable from and
- from that list to make a list of airports and the airports they can reach, essentially inverting the list and
- to sort the list, so it'll be easy to find the biggest hub (the one that can reach the most airports) and then the next one down and so on
1a. Make a List of Airports and Where They're Reachable From
To populate this map I’m going to read the routes one by one and make map entries by taking the destination, let’s call that the “to” as the key and the starting airport, the “from”, as the value of each map entry. So the first key/value pair I’m adding is:
Key: "ORD", Value "DSM"
Then I have to backtrack into all the airports that point at “ORD”, because if there is a route that leads to “ORD”, then the from airport of that route leads to “DSM” as well (via “ORD”). Those would now be chained
Some other airport => ORD => DSM
And there could be many other airports that lead to “ORD”, so I have to recurse thought them. Let's write a function and call it buildAirportsReachableFrom and code it as below. It has a nested function and code that calls that nested function.
// go backwards from the route's tos
func buildAirportsReachableFrom(_ airports: [String], _ routes: [[String]], _ startingAirport: String) -> [String: [String]] {
// nested recursion function
func airportReachableFrom(_ airportsReachableFromKey: String, _ airport: String, _ routes: [[String]], _ airportsReachableFrom: inout [String]) {
for route in routes {
if route[1] == airport {
if !airportsReachableFrom.contains(route[0]) && route[0] != airportsReachableFromKey {
airportsReachableFrom.append(route[0])
airportReachableFrom(airportsReachableFromKey, route[0], routes, &airportsReachableFrom)
}
}
}
return
}
var airportsReachableFrom = [String: [String]]()
for airport in airports {
if airport != startingAirport { // don't bother looking at routes to the starting airport
airportsReachableFrom[airport] = [String]()
// recurse
airportReachableFrom(airport, airport, routes, &airportsReachableFrom[airport]!)
}
}
return airportsReachableFrom
}
That gives me this map, a list of airports (minus the starting airport), each with all the airports that can possibly lead to them.
"SIN": ["CDG", "DEL", "TLV"]
"TLV": []
"DOH": ["DEL", "TLV"]
"CDG": ["SIN", "DEL", "TLV"]
"SAN": ["SFO", "LHR", "EYW"]
"HND": ["EWR"]
"DEL": ["TLV"]
"EWR": []
"LHR": ["EYW", "SAN", "SFO"]
"ICN": ["HND", "EWR"]
"BGI": ["ORD", "DSM", "SFO", "LHR", "EYW", "SAN"]
"DSM": ["SFO", "LHR", "EYW", "SAN"]
"BUD": ["CDG", "SIN", "DEL", "TLV"]
"SFO": ["LHR", "EYW", "SAN"]
"EYW": ["SAN", "SFO", "LHR"]
"ORD": ["DSM", "SFO", "LHR", "EYW", "SAN"]
"JFK": ["HND", "EWR", "ICN"]
Which is a pretty good expression of the connections graph of the problem.
1b. Invert the List to Get a List of Airports and All The Airports They Can Reach
I want to read the map and "invert" it, so I get the same list of airports, but not with each airport showing all the airports that connect to them, instead with all the airports that they connect to. So I have to go through the map above one key/value pair at a time and scan through each of the airports (in the values) that connect to them and create a new list with those airports as the keys. So the first key/value pair
"SIN": ["CDG", "DEL", "TLV"]
turns into 3 pairs
"CDG": ["SIN"] is added,
"DEL": ["SIN"] is added and
"TLV": ["SIN"] is added
the next line
"TLV": []
has no connections (no routes to that airport), but the next one
"DOH": ["DEL", "TLV"]
will add "DOH" to the value of the already created "DEL" key, created from the first key/value pair above and create a new key/value pair for "TLV"
"DEL": ["SIN"] gets "DOH" added to it to become "DEL": ["SIN", "DOH"]
"TLV": ["DOH"] is added
Here's the code that does that. Let's call this function buildAirportsServingRoutesTo.
// invert the list
func buildAirportsServingRoutesTo(_ airportsReachableFrom: [String: [String]]) -> [String: [String]] {
var airportsTo = [String: [String]]()
for airportFrom in airportsReachableFrom {
for airport in airportFrom.value {
if airportsTo[airport] == nil {
airportsTo[airport] = [String]()
}
var airports = airportsTo[airport]!
airports.append(airportFrom.key)
airportsTo[airport] = airports
}
}
return airportsTo
}
Now we have the "inverted" list, witch contains all the airports with the all the airports they connect to.
"EWR": ["HND", "ICN", "JFK"]
"CDG": ["SIN", "BUD"]
"EYW": ["SAN", "LHR", "BGI", "DSM", "SFO", "ORD"]
"TLV": ["SIN", "DOH", "CDG", "DEL", "BUD"]
"SIN": ["CDG", "BUD"]
"SAN": ["LHR", "BGI", "DSM", "SFO", "EYW", "ORD"]
"SFO": ["SAN", "LHR", "BGI", "DSM", "EYW", "ORD"]
"DEL": ["SIN", "DOH", "CDG", "BUD"]
"LHR": ["SAN", "BGI", "DSM", "SFO", "EYW", "ORD"]
"ORD": ["BGI"]
"HND": ["ICN", "JFK"]
"ICN": ["JFK"]
"DSM": ["BGI", "ORD"]
1c. Sort the List
Look for the airport that connects to the most other airports. Add it to a new list and remove it from consideration. Also, remove all airports it connects to in all other key/value pairs. Then look for the next airport with the most connections (that's a recursion), until we have a sorted list starting with the airport with the most routes to the other airports.
Being that it also is a recusring function, it has the same structure as the buildAirportsReachableFrom function above, with a nested function and the code that calls it. Let's call this function orderAirportsServingRoutesTo. Here is the code:
// order the list by biggest hub first
func orderAirportsServingRoutesTo(_ airportsServingRoutesTo: [String: [String]]) -> [(String, [String])] {
// nested recursion function
func orderAirports(_ airportsByNumberOfTos: inout [(String, [String])], _ airportsServingRoutesTo: inout [String: [String]]) {
// get airport that serves most routes
var airportWithMostRoutes = ("", [String]()) // lame initialization
for airport in airportsServingRoutesTo {
if airport.value.count > airportWithMostRoutes.1.count {
airportWithMostRoutes = (airport.key, airport.value)
}
}
if airportWithMostRoutes.1.count == 0 {
return
}
airportsByNumberOfTos.append(airportWithMostRoutes)
// remove tos that are already covered in airport with more routes
for airportServingRoutesTo in airportsServingRoutesTo {
if airportServingRoutesTo.key != airportWithMostRoutes.0 {
// append the airport in the key
var airportWithMostRoutesInclKey = airportWithMostRoutes.1
airportWithMostRoutesInclKey.append(airportWithMostRoutes.0)
airportsServingRoutesTo[airportServingRoutesTo.key] = Array(Set(airportServingRoutesTo.value).subtracting(airportWithMostRoutesInclKey))
}
}
airportsServingRoutesTo.removeValue(forKey: airportWithMostRoutes.0)
if airportsServingRoutesTo.count > 0 {
orderAirports(&airportsByNumberOfTos, &airportsServingRoutesTo)
}
}
var airportsByNumberOfTos = [(String, [String])]() // array of tuples
var airportsServingRoutesToCopy = airportsServingRoutesTo
orderAirports(&airportsByNumberOfTos, &airportsServingRoutesToCopy)
return airportsByNumberOfTos
}
2.-6. Read the List and Create the Routes to Add
Now we can read this list and create a new list of routes, by adding routes to it for each of the airports until we've covered all the destinations or we're through the list. If we've run through all the airports, but have not covered all destinations yet, we have to create individual routes to all the missing airports. Let's write a function that's called determineRoutesToAdd. Here is the code:
func determineRoutesToAdd(_ startingAirport: String, _ airports: [String], _ orderedAirportsServingRoutesTo: [(String, [String])]) -> [[String]] {
var routesToAdd = [[String]]()
var airportsCopy = airports
// remove starting airport
airportsCopy = airportsCopy.filter {$0 != startingAirport}
// add routes to all airports that have tos
for orderedAirportsServingRouteTo in orderedAirportsServingRoutesTo {
routesToAdd.append([startingAirport, orderedAirportsServingRouteTo.0])
// remove the airport that a route was added to from the copy
airportsCopy = airportsCopy.filter {$0 != orderedAirportsServingRouteTo.0}
// if all airports are covered
if airportsCopy.isEmpty {
break
}
// remove airports that have routes to them from the copy
for airportServed in orderedAirportsServingRouteTo.1 {
airportsCopy = airportsCopy.filter {$0 != airportServed}
}
}
// add direct routes to the tos that have no routes to them
for airport in airportsCopy {
routesToAdd.append([startingAirport, airport])
}
return routesToAdd
}
The result of this function is the routes we have to add, so that the starting airport is connected to all other airports. It is the answer to our problem.
7. Present the Results
All we have left to do is call each function we've created above and print the result.
let airportsReachableFrom = buildAirportsReachableFrom(airports, routes, startingAirport)
var airportsServingRoutesTo = buildAirportsServingRoutesTo(airportsReachableFrom)
let orderedAirportsServingRoutesTo = orderAirportsServingRoutesTo(airportsServingRoutesTo)
let routesToAdd = determineRoutesToAdd(startingAirport, airports, orderedAirportsServingRoutesTo)
print("minimum routes to add: \(routesToAdd.count)")
print("routes:\n\(routesToAdd)")
Done! Try It Yourself
That's all the code! And below is a playground for it. The code is written in Swift version 5. Download the playground, which you can run in Xcode or in the Swift Playgrounds app (which runs on Mac or iPad). If you don't have a Mac or an iPad or just prefer to do this online, you can go to replit.com, where I've shared the code as well. On replit, you can run and edit it as you please, but to edit you have to fork the code (make your own copy of the code) and to do that you have to create an account. But it's free and easy to setup!
Final Thoughts
Even this write up is long and maybe difficult to understand. Don't be discouraged. Use the download and play with it in Xcode or Swift Playgrounds and/or try the replit link. You can contact me here if you like or you can reply to my comment in YouTube.
Yvan, 1/3/2021
 |