Upgrade interview question: Find the valid 'journeys' for src/dest including connecting flights.

UpgradeJourneyFinder.java

package com.stanlemon;

import java.text.SimpleDateFormat;
import java.time.LocalDateTime;
import java.time.ZoneId;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.List;
import java.util.Map;

/*

A - Fights
List<Flight>
 SF ---> Washington (9am-->11.30am)
 Washington ----> New  York (12.30pm -->4.30pm)
 SF -----> New York (10am ---> 3pm)
 SF -----> Seattle (10.30am ---> 2.30pm)
 Seattle -----> New  York (1.30pm ---> 4.30pm)
 SF -----> New York (12pm ---> 5pm)

findJourneyOptions(flights, SF, New York);

Output -
 List<Journey>
 Journey-1
      SF ---> Washington (9am-->11.30am)
      Washington ----> New  York (12.30pm -->4.30pm)
 Journey-2
      SF -----> New York (10am ---> 3pm)
 Journey-3
      SF -----> New York (12pm ---> 5pm)



Scenario: 1 stop (direct flights)
Given: the flights A
When: a user wants to travel from SF to New York
Then: System returns )=

Journey  1 = SF -----> New York (10am ---> 3pm)
Journey 2 = SF -----> New York (12pm ---> 5pm)

**/

class Journey {
    List<Flight> flights;

    public Journey(final List<Flight> flights){
        this.flights = Collections.unmodifiableList(flights);
    }
}

class Flight {
    String source;
    String dest;
    Date startDate;
    Date endDate;
    String flightNumber;

    public Flight(String source, String dest, Date startDate, Date endDate, String flightNumber) {
        this.source = source;
        this.dest = dest;
        this.startDate = startDate;
        this.endDate = endDate;
        this.flightNumber = flightNumber;
    }
}

class Solution {
    Map<String, List<Flight>> flightSourceMap;

    public static void main(String[] args) {
        List<Flight> allFlights = List.of(
            new Flight("SF", "Washington", atTime(9, 0), atTime(11, 30), "1"),
            new Flight("Washington", "New York", atTime(12, 30), atTime(12+4, 30), "2"),
            new Flight("SF", "New York", atTime(10, 0), atTime(12+3, 0), "3"),
            new Flight("SF", "Seattle", atTime(10, 30), atTime(12+2, 30), "4"),
            new Flight("Seattle", "New York", atTime(12+1, 30), atTime(12+4, 30), "5"),
            new Flight("SF", "New York", atTime(12, 0), atTime(12+5, 0), "6")
        );

        Solution solution = new Solution();
        // Naive solution that only handles one connection
        //List<Journey> journeys = solution.findJourneyOptionsNaive(allFlights, "SF", "New York");
        // Solution allows for limitless connections (data set only connects once)
        List<Journey> journeys = solution.findJourneyOptions(allFlights, "SF", "New York");
        // Solutions allows for up to one connection
        //List<Journey> journeys = solution.findJourneyOptions(allFlights, "SF", "New York", 2);

        // Use the VM options -ea to enable assertions and run these
        assert journeys.size() == 3 : "We should have found three flights";
        assert journeys.get(0).flights.size() == 2 : "First journey should have two flights";
        assert journeys.get(0).flights.get(0).flightNumber.equals("1") : "First journey, first flight number does not match";
        assert journeys.get(0).flights.get(1).flightNumber.equals("2") : "First journey, second flight number does not match";
        assert journeys.get(1).flights.size() == 1 : "Second journey should have one flight";
        assert journeys.get(1).flights.get(0).flightNumber.equals("3") : "Second journey, first flight number does not match";
        assert journeys.get(2).flights.size() == 1 : "Third journey should have one flight";
        assert journeys.get(2).flights.get(0).flightNumber.equals("6") : "Third journey, first flight number does not match";

        System.out.println("Going from SF to New York:");
        System.out.println();

        journeys.forEach(Solution::printJourney);
    }

    public static void printJourney(final Journey journey) {
        System.out.println("Journey:");
        for (Flight flight: journey.flights) {
            System.out.printf(
                "%s -> %s (%s-%s) #%s\n",
                flight.source, flight.dest, getTime(flight.startDate), getTime(flight.endDate), flight.flightNumber
            );
        }
        System.out.println();
    }

    public static String getTime(final Date date) {
        SimpleDateFormat format = new SimpleDateFormat("hh:mma");
        return format.format(date);
    }

    private static Date atTime(final int hour, final int minute) {
        return Date.from(
            LocalDateTime.now().withHour(hour).withMinute(minute).atZone(ZoneId.systemDefault()).toInstant()
        );
    }

    // Finding flights that match
    // findJourneyOptions(flights, SF, New York);
    public List<Journey> findJourneyOptionsNaive(List<Flight> flights, String src, String dest) {
        List<Journey> journeys = new ArrayList<>();

        for (Flight flight : flights) {
            // Does not have the right starting point, skip over it
            if (!flight.source.equals(src)) {
                continue;
            }

            // Destination is our ending point, this is a direct flight
            if (flight.dest.equals(dest)) {
                journeys.add(
                    new Journey(List.of(flight))
                );
            }

            for (Flight connection: flights) {
                // If this flight is not starting where we've arrived it cannot be a connection
                if (!flight.dest.equals(connection.source)) {
                    continue;
                }

                journeys.add(
                    new Journey(List.of(flight, connection))
                );
            }
        }

        return journeys;
    }

    // Finding flights that match
    // findJourneyOptions(flights, SF, New York);
    public List<Journey> findJourneyOptions(List<Flight> flights, String src, String dest) {
        return findJourneyOptions(flights, src, dest, null);
    }

    public List<Journey> findJourneyOptions(List<Flight> flights, String src, String dest, Integer limit) {
        List<Journey> journeys = new ArrayList<>();

        for (Flight flight: flights) {
            // This flight is starting at the right place, find all the connections to the end
            if (!flight.source.equals(src)) {
                continue;
            }

            // Flight has the right starting point, let's get all the connections.
            List<Flight> found = new ArrayList<>();
            found.add(flight);

            findFlights(flight, flights, found);

            if (found.isEmpty()) {
                continue;
            }

            // If this exceeds the number of connections, skip it
            if (limit != null && found.size() > limit) {
                continue;
            }

            Flight last = found.get(found.size() - 1);

            // If the final destination is our destination, this was a valid route and we add it to our list of journeys
            if (last.dest.equals(dest)) {
                journeys.add(new Journey(found));
            }
        }

        return journeys;
    }

    public void findFlights(Flight src, List<Flight> flights, List<Flight> found) {
        for (Flight flight: flights) {
            // You cannot connect to your own flight
            if (src.flightNumber.equals(flight.flightNumber)) {
                continue;
            }

            // You must connect to a flight that sources from your destination
            if (!src.dest.equals(flight.source)) {
                continue;
            }

            // You cannot connect to a flight that leaves before you get there
            if (src.endDate.after(flight.startDate)) {
                continue;
            }

            // Add the flight we found
            found.add(flight);

            // Go look for some more flights
            findFlights(flight, flights, found);
        }
    }
}