Найти стартовый город путешествия

Question

Недавно у меня было интервью, где я спросил, дали ли мне набор поездок, которые составили путешествие, какой будет отправная точка всего путешествия?

Например, я предоставляю несколько случайных поездок в виде списка ниже, где путешествие начинается с "A" и заканчивается "B" и так далее.В конце концов, все поездки образуют целое путешествие, где "A" будет началом всего путешествия, а "C" будет пунктом назначения.Вопрос в том, как найти начальную точку (город)?

Trips := [ ["A","B"], ["B", "C"], ["C", "D"] ]

Я предоставил приведенное ниже решение с O(n) и получил отклонение в течение 10 минут.У меня было ощущение, что я сделал что-то очень неправильное, что они должны были принять решение как можно скорее.Вот мое первоначальное решение:

/*
     * function to find the starting city of a
     * given journey from a list of trips
     *
     * time complexity for the solution is O(n)
     * */
    private static String findStartCity(Map<String, String> trips) {

        Map<String, String> reverseTrips = new HashMap<String, String>();


        /*
         * create a reverse map for the trips where
         * start and destination inter-changed
         * */
        for (Map.Entry<String, String> entry : trips.entrySet()) {
            reverseTrips.put(entry.getValue(), entry.getKey());
        }

        String startCity = null;

        /*
         * if a start city for a trip is not present as the destination
         * of any other trip, the city of the starting point for the whole
         * journey
         * */
        for (Map.Entry<String, String> entry : trips.entrySet()) {

            if (!reverseTrips.containsKey(entry.getKey())) {
                startCity = entry.getKey();
                break;
            }
        }

        // the inputs are not valid
        if (startCity == null) {
            return null;
        }

        return startCity;
    }

Я думаю о решении позже, которое работает с удвоенной скоростью, чем предыдущее.Это приведено ниже,

private static class Pair<A, B> {

    private final A start;
    private final B destination;

    public Pair(A start, B destination) {
        super();
        this.start = start;
        this.destination = destination;
    }

    public A getStart() {
        return start;
    }

    public B getDestination() {
        return destination;
    }

    public int hashCode() {

        int hashFirst = start != null ? start.hashCode() : 0;
        int hashSecond = destination != null ? destination.hashCode() : 0;

        return (hashFirst + hashSecond) * hashSecond + hashFirst;
    }

    public boolean equals(Object other) {

        if (other instanceof Pair) {
            Pair otherPair = (Pair) other;
            return
                    ((this.start == otherPair.start ||
                            (this.start != null && otherPair.start != null &&
                                    this.start.equals(otherPair.start))) &&
                            (this.destination == otherPair.destination ||
                                    (this.destination != null && otherPair.destination != null &&
                                            this.destination.equals(otherPair.destination))));
        }

        return false;
    }

    public String toString() {
        return "(" + start + ", " + destination + ")";
    }

}


private static String findStartCity1(List<Pair<String, String>> trips) {

    List<String> cities = new ArrayList<>();

    trips.forEach(trip -> {

        String start = trip.getStart();
        String destination = trip.getDestination();

        if (cities.contains(start)) {
            cities.remove(start);
        } else {
            cities.add(0, start);
        }

        if (cities.contains(destination)) {
            cities.remove(destination);
        } else {
            cities.add(destination);
        }

    });

    return cities.get(0);
}

Однако существует ли экспоненциальное решение для данной проблемы?Я не предоставляю звонки, но легко предположить.