Leetcode discuss: 332. Reconstruct Itinerary

Here is the link.

C# DFS algorithm with tough decisions to make

July 18, 2020

Introduction
It is my preparation for phone screen from Facebook on July 20, 2020. I like to work on leetcode mock interview phone screen mock interview nonstop for two days.

I came cross this algorithm, and it took me more than two hours to make it work. I want to say something: "Being a programmer, most important is to be patient, and also observe what happens using Visual Studio".

I learned so many lessons from those few hours. I like to write a simple solution, so I tried a few ideas and failed all the way until I figured out the simple one.

Here are highlights:

1. More than one ticket for same start and dest cities. For example, JFK to NRT, there are two tickets.
2. I tried to use C# Dictionary<string, SortedSet>, I ran into failed test case, so duplicate allows, SortedSet cannot be used;
3. I tried to use C# LinkedList, but I had problem to put it back after failed DFS search. I chose to use LinkedList RemoveFirst, AddFirst API, it does not work for back tracking.
4. I tried to use HashSet to make unique ticket like "JFK"+"NRT". Because two tickets are available for same ticket, I have to use original hashMap to mark visit.
5. I also spent over 15 minutes to figure out that variable found as List is empty and I have to add ref.
6. List is used, and then apply Sort API; Later List.RemoveAt index position, and then List.InsertAt index position position; So all destination are sorted in lexicographically order.
7. Play with base case - all tickets are used and only used once.

Performance
It should take me less than 25 minutes, but I took over 100 minutes to play with the code.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace airlineTickets
{
    class Program
    {
        static void Main(string[] args)
        {
            RunTestcase3(); 
        }

        public static void RunTestcase1()
        {
            // [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
            var tickets = new List<IList<string>>();

            tickets.Add(new List<string>() {"MUC", "LHR" });
            tickets.Add(new List<string>() {"JFK", "MUC" });
            tickets.Add(new List<string>() {"SFO", "SJC" });
            tickets.Add(new List<string>() {"LHR", "SFO" });

            var result = FindItinerary(tickets);
        }

        public static void RunTestcase2()
        {
            var tickets = new List<IList<string>>();

            tickets.Add(new List<string>() {"EZE","AXA" });
            tickets.Add(new List<string>() {"TIA","ANU" });
            tickets.Add(new List<string>() {"ANU","JFK" });
            tickets.Add(new List<string>() {"JFK","ANU" });

            tickets.Add(new List<string>() {"ANU","EZE" });
            tickets.Add(new List<string>() {"TIA","ANU" });
            tickets.Add(new List<string>() {"AXA","TIA" });
            tickets.Add(new List<string>() {"TIA","JFK" });
            tickets.Add(new List<string>() {"ANU","TIA" });
            tickets.Add(new List<string>() {"JFK","TIA" });            

            var result = FindItinerary(tickets);        
        }

        public static void RunTestcase3()
        {
            var tickets = new List<IList<string>>();

            // [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]

            tickets.Add(new List<string>() { "JFK","KUL" });
            tickets.Add(new List<string>() { "JFK","NRT" });
            tickets.Add(new List<string>() { "NRT","JFK" });                  

            var result = FindItinerary(tickets);
        }

        public static IList<string> FindItinerary(IList<IList<string>> tickets)
        {
            // the idea is to run a DFS search
            // keep all tickets into a hashmap
            // path - find first path then return
            // hashMap - C# Dictionary<string, SortedSet<string>>
            if (tickets == null || tickets.Count == 0)
            {
                return new List<string>();
            }

            var count = tickets.Count;
            // ANU->TIA two tickets
            var map = new Dictionary<string, List<string>>();
            foreach (var item in tickets)
            {
                var start = item[0];
                var dest  = item[1];
                if (!map.ContainsKey(start))
                {
                    map.Add(start, new List<string>());
                }

                map[start].Add(dest);
            }

            foreach(var key in map.Keys)
            {
                map[key].Sort();                 
            }

            var path = new List<string>();
            var found = new List<string>();
            
            path.Add("JFK");

            runDFSSearch(map, 0, count, "JFK", path, ref found);

            return found;
        }

        /// DFS - mark visited
        /// backtracking
        /// check the final length 
        private static void runDFSSearch(
            Dictionary<string, List<string>> map,
            int index,
            int total,
            string start,
            List<string> path,
            ref List<string> found)
        {            
            if (found.Count > 0)
            {
                return;
            }

            // all the tickets used once and only once
            if (map.Count == 0)
            {
                found = path.ToList();
                return;
            }

            if (!map.ContainsKey(start))
            {
                return;
            }

            var destCities = map[start];
            var copy = new List<string>(destCities);

            for (int i = 0; i < copy.Count; i++ )
            {
                var dest = copy.ElementAt(i);

                path.Add(dest);
                map[start].RemoveAt(i);
                if (map[start].Count == 0)
                {
                    map.Remove(start);
                }

                runDFSSearch(map, index + 1, total, dest, path, ref found);

                // backtracking
                path.RemoveAt(path.Count - 1);
                if (!map.ContainsKey(start))
                {
                    map.Add(start, new List<string>());
                }

                map[start].Insert(i,dest);
            }
        }
    }
}