5
\$\begingroup\$

Problem statement is

Write a method that can take an unordered list of airport pairs visited during a trip and return the list in order.

{"ITO", "KOA"}, {"SFO", "SEA"}, {"LGA", "CDG"}, {"KOA", "LGA"}, {"PDX", "ITO"}, {"SEA", "PDX"}

should return:

(SFO,SEA)(SEA,PDX)(PDX,ITO)(ITO,KOA)(KOA,LGA)(LGA,CDG)

I have come up with this O(n^2) algorithm. I wanted to know if it can be done better than this:

private static void sortPairs(String[][] input)
    {

        for (int i = 0; i < input.length; i++) {
            int j = 1;
            for (; j < input.length; j++) {
                if (input[i][0].equals(input[j][1])) {
                    break;
                }
            }
            if (j == input.length) {
                swapPairs(i, 0, input);
                break;
            }
        }


        for (int i = 0; i < input.length; i++) {
            int j = 1;
            for (; j < input.length; j++) {
                if (input[i][1].equals(input[j][0])) {
                    break;
                }
            }
            if (j == input.length) {
                swapPairs(i, input.length - 1, input);
                break;
            }
        }


        for (int i = 2; i < input.length - 1; i++) {
            int j = i - 1;
            for (; j >= 0; j--) {
                if (input[j + 1][0].equals(input[j][1])) {
                    break;
                }
                swapPairs(j, j + 1, input);
                if (input[j + 1][0].equals(input[j][1])) {
                    break;
                }
            }

        }
    }

    private static void swapPairs(int i, int j, String[][] pairs)
    {
        String[] temp = pairs[i];
        pairs[i] = pairs[j];
        pairs[j] = temp;
    }
\$\endgroup\$
4
\$\begingroup\$

Welcome to corereview.se and thanks for sharing your code.

general coding

avoid odd ball solutions

In your inner and outer loop, you use different methods to declare the loop counter variable. The better way would have bee to find a solution that does not need this odd cod style.

But since you decided to do so you should have placed a comment why you had to do this.

Same is with opening braces {: In your method signature, you place them at a new line, in the rest of the code you put them on the same line as the preceding statement.

THere is a hot discussion out there where to put these opening braces. I don't want to contribute to that argument, but all agree that you should decide on either one place and stick to that throughout your code.

business approach

The code does basically three things:

  1. find start point
  2. connect elements
  3. reorder the input array

You chose a procedural approach to the problem. This is not bad by itself, but since Java is an object oriented language you should start looking for OO approaches.

But OOP doesn't mean to "split up" code into random classes.

The ultimate goal of OOP is to reduce code duplication, improve readability and support reuse as well as extending the code.

Doing OOP means that you follow certain principles which are (among others):

  • information hiding / encapsulation
  • single responsibility
  • separation of concerns
  • KISS (Keep it simple (and) stupid.)
  • DRY (Don't repeat yourself.)
  • "Tell! Don't ask."
  • Law of demeter ("Don't talk to strangers!")

A more OOish approach could look like this:

private static void sortPairs(String[][] input) {
    Map<String,String> routes = convertToMap(input);
    String start =  findFirstStart(routes);
    reorderArray(routes, start, input);
}
private static Map<String,String> convertToMap(
         String[][] input) {
    Map<String,String> routes = new HashMap();
    for(String[] route : input)
       routes.put(route[0][1]);
    return routes;
}
private static String findFirstStart( 
        Map<String,String> routes) {
     return routes.keySet()
          .stream()
          .filter(city->!routes.values().contains(city))
          .findAny()
          .get();
}
private static void reorderArray(
        Map<String,String> routes, 
        String start, 
        String[][] input) {
     for(int i = 0 ; i < input.length) {
         String end = routes.get(start);
         input[i][0]=start;
         input[i][1]=end;
         start = end;
     }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Whichever city is not in the values side of any of the pairs is the starting city? That's clever.. \$\endgroup\$ – Teddy Jul 24 '18 at 4:22
  • 1
    \$\begingroup\$ In fact, you approach is still procedural, but it is a nice demonstration of how to split a problem into sub-problems and methods that solve a single sub-problem. Every code benefits from that ;-) \$\endgroup\$ – mtj Jul 24 '18 at 5:31
  • 1
    \$\begingroup\$ @Teddy this is exactly what the OP did. My approach made it more obvious. That is what I mean with the "readability" goal. \$\endgroup\$ – Timothy Truckle Jul 24 '18 at 9:24
2
\$\begingroup\$

This kind of problem seems like it could benefit from using a link list. This will shorten your code quite a bit and, if I'm not mistaken improve your time complexity quite a bit too:

class Node {

    public String[] pair = new String[2];
    public Node next = null;

    public Node() {
    }

    public Node(String[] pair) {
        this.pair = Arrays.copyOf(pair, 2);
    }
}

static void sortPairs(String[][] pairs) {
    Node root = new Node(pairs[0]);
    Node end = root;
    int size = 1;
    int limit = pairs.length - 1;
    swap(pairs,0, limit);
    int start = 0;
    while (size < pairs.length) {
        for (int i = start; i < limit; ++i) {
            if (pairs[i][0].equals(end.pair[1])) {
                end.next = new Node(pairs[i]);
                end = end.next;
                swap(pairs,i, --limit);
                ++size;
            }
            if (pairs[i][1].equals(root.pair[0])) {
                Node temp = new Node(pairs[i]);
                temp.next = root;
                root = temp;
                swap(pairs,i, --limit);
                ++size;
            }
        }
    }
    for(int i =0;i < pairs.length; ++i){
        pairs[i] = root.pair;
        root = root.next;
    }
}

private static void swap(String[][] arr, int indexA, int indexB) {
    String[] temp = arr[indexA];
    arr[indexA] = arr[indexB];
    arr[indexB] = temp;
}

The main part of this basically starts with the first pair and looks for either a match to the front or the end. whenever it finds a match it's added to the link list and swapped to the bottom of the array.

As swaps occur the numerical limit of the loop keeps getting adjusted shorter, until the link list size matches the array.

Each ordered pair is, then, written back to the array in order. If your end goal is just to print out the pairs, you could omit this step and return the root Node.

Your problem statement didn't mention one way or the other, so I assumed, as per your example, that no airport gets visited twice.

Note for brevity sake I kept the properties of the Node class public, instead of using getters/setters.

2.0

I did some more studying of the problem and came up with, what appears to me, a O(n) solution. Basically I combined the creation of the HashMap and filtering of the start city in one loop and rebuilding the array in a second loop:

static void sortPairs2(String[][] pairs) {
        TreeMap<String, Integer> startCity = new TreeMap<>();
        HashMap<String, String[][]> cities = new HashMap<>();
        for (String[] pair : pairs) {
            if (!cities.containsKey(pair[0])) {
                cities.put(pair[0], new String[2][]);
            }
            cities.get(pair[0])[1] = pair;
            if (!cities.containsKey(pair[1])) {
                cities.put(pair[1], new String[2][]);
            }
            cities.get(pair[1])[0] = pair;
            startCity.compute(pair[0], ((t, u) -> (u == null) ? 1 : ++u));
            if(startCity.get(pair[0]) == 2) {
                startCity.remove(pair[0]);
            }
            startCity.compute(pair[1], ((t, u) -> (u == null) ? 1 : ++u));
            if(startCity.get(pair[1]) == 2) {
                startCity.remove(pair[1]);
            }               
        }
        String[][] firstTemp = cities.get(startCity.firstKey());
        String[][] lastTemp = cities.get(startCity.lastKey());
        if(firstTemp[1] == null) {
            pairs[0] = lastTemp[1];
        }
        else {
            pairs[0] = firstTemp[1];
        }
        int limit = pairs.length;           
        for(int i = 1;i < limit;++i) {
            String[][] tempList = cities.get(pairs[i-1][1]);
            pairs[i] = tempList[1];
        }
    }
\$\endgroup\$
  • \$\begingroup\$ "if I'm not mistaken improve your time complexity quite a bit too" well - you do. Time complexity of your approach is also O(n²) because is requires to combine each start city with each destination city. Yes, in average the lookup in the other list takes 0,5n but constant factors are ignored. To reduce the time complexity you need a data structure with a better access profile like a binary tree (O(ln(n))) or a Hash set (O(sqr(n))) \$\endgroup\$ – Timothy Truckle Jul 24 '18 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.