Program to find whether the destination is reachable or not

Question

I was asked in an interview the below question

Given a list of Flights and a starting point and destination print out all possible combination of flights which can be used to reach destination from starting point.

example : Given the list of flights like

A -> B
A -> D
B -> C
B -> D
B -> H
D -> A
C -> E
E -> F
E -> G
G -> H

Given start point as A and endpoint as H the program should output

A -> B -> H

A -> B -> C -> E -> G -> H

The program I wrote is like below

package flight;

import java.util.List;

public class Flights {

    private String start;
    private List<String> destinations;

    public Flights(String start, List<String> destinations) {
        this.start = start;
        this.destinations = destinations;
    }

    public String getStart() {
        return start;
    }

    public void setStart(String start) {
        this.start = start;
    }

    public List<String> getDestinations() {
        return destinations;
    }

    public void setDestinations(List<String> destinations) {
        this.destinations = destinations;
    }

    public boolean containsDestination(String city){
        return getDestinations().contains(city);
    }
}

package flight;

import java.util.ArrayList;
import java.util.List;

public class Test {

    public static void main(String[] args) {
        List<String> fList = new ArrayList<>();
        fList.add("B");
        fList.add("D");
        Flights f1 = new Flights("A",fList);

        fList = new ArrayList<>();
        fList.add("C");
        fList.add("D");
        fList.add("H");
        Flights f2 = new Flights("B",fList);

        fList = new ArrayList<>();
        fList.add("A");
        Flights f3 = new Flights("D",fList);


        fList = new ArrayList<>();
        fList.add("E");
        Flights f4 = new Flights("C",fList);

        fList = new ArrayList<>();
        fList.add("F");
        fList.add("G");
        Flights f5 = new Flights("E",fList);

        fList = new ArrayList<>();
        fList.add("H");
        Flights f6 = new Flights("G",fList);

        List<Flights> flights = new ArrayList<>();
        flights.add(f1);
        flights.add(f2);
        flights.add(f3);
        flights.add(f4);
        flights.add(f5);
        flights.add(f6);

        String start = "A";
        String end = "H";

        getFlights(flights,start,end,end);

    }


    private static void getFlights(List<Flights> flights,String start,String destination,String flightResult){
        if (start.equals(destination)){
             flightResult = flightResult+"-"+start;
        }
        List<String> ls = new ArrayList<>();
        for (int i=0;i<flights.size();i++){
            Flights f = flights.get(i);
            if(f.containsDestination(destination)){
                ls.add(flightResult+"-"+f.getStart());
            }
        }
        for (int i=0;i<ls.size();i++){
            String as = ls.get(i);
            String[] s = as.split("-");
            String lastCity = s[s.length-1];
            if (!lastCity.equals(start)){
                getFlights(flights,start,lastCity,as);
            }

        }

        System.out.println(ls);
    }
}

The program is outputting like

[H-B-A]
[H-G-E-C-B-A]
[H-G-E-C-B]
[H-G-E-C]
[H-G-E]
[H-B, H-G]

I only want the first two ones which are valid, how can i do that ? Also is there an optimized way ?

Answer 1

Your code has problem with

if (!lastCity.equals(start)){
     getFlights(flights,start,lastCity,as);
}

After returning from the recursive call it still has System.out.println(ls) below it, So it print's everything you save in the list, you can overcome this problem by having your result stored in another list, i checked it's working, here's the code and i mentioned changes in the code with side comments, you need to change only your test class

package flight;
import java.util.*;

public class Test {

    public static void main(String[] args) {
        List<String> fList = new ArrayList<>();
        fList.add("B");
        fList.add("D");
        Flights f1 = new Flights("A",fList);

        fList = new ArrayList<>();
        fList.add("C");
        fList.add("D");
        fList.add("H");
        Flights f2 = new Flights("B",fList);

        fList = new ArrayList<>();
        fList.add("A");
        Flights f3 = new Flights("D",fList);


        fList = new ArrayList<>();
        fList.add("E");
        Flights f4 = new Flights("C",fList);

        fList = new ArrayList<>();
        fList.add("F");
        fList.add("G");
        Flights f5 = new Flights("E",fList);

        fList = new ArrayList<>();
        fList.add("H");
        Flights f6 = new Flights("G",fList);

        List<Flights> flights = new ArrayList<>();
        flights.add(f1);
        flights.add(f2);
        flights.add(f3);
        flights.add(f4);
        flights.add(f5);
        flights.add(f6);

        String start = "A";
        String end = "H";

        getFlights(flights,start,end,end);

        for(int i=0;i<answerlist.size();i++){   // print here
            String s = answerlist.get(i);
            StringBuilder x = new StringBuilder(); // stringbuilder to reverse the result
            x.append(s);
            x = x.reverse();
            System.out.println(x);
        }
    }
    public static List<String> answerlist = new ArrayList<>();   //list to store result

    private static void getFlights(List<Flights> flights,String start,String destination,String flightResult){
        if (start.equals(destination)){
             flightResult = flightResult+"-"+start;
        }
        List<String> ls = new ArrayList<>();
        for (int i=0;i<flights.size();i++){
            Flights f = flights.get(i);
            if(f.containsDestination(destination)){
                ls.add(flightResult+"-"+f.getStart());
            }
        }
        for (int i=0;i<ls.size();i++){
            String as = ls.get(i);
            String[] s = as.split("-");
            String lastCity = s[s.length-1];
            if (!lastCity.equals(start)){
                getFlights(flights,start,lastCity,as);
            }
            else{
                answerlist.add(as);        //store in a newlist
            }       
        }
    }
}