1
\$\begingroup\$

Solving this problem:

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

I have used topological sorting to solve this problem. So, for every node I am calculating in-degree and picking the lowest node whose in-degree is zero. This will be the first node and who doesn't have any prerequisite. After that I am decrementing the child node in-degree and then repeating the same process until i am out of nodes.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Course_Schedule_II_210 {

    public static void main(String[] args) {
        int[][] arr = {};
        int totalCourse = 0;
        int[] totalCourseInOrder = findTotalCourseInOrder(totalCourse, arr);

        for (int i=0; i < totalCourseInOrder.length; i++) {
            System.out.println("The totalCourseInOrder element is : "+totalCourseInOrder[i]);
        }
    }

    private static int[] findTotalCourseInOrder(int totalCourse, int[][] arr) {

        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        int[] a1 = new int[totalCourse];
        int var = 0;

        for (int i=0; i < arr.length; i++) {
            int[] a = arr[i];
            int k = a[1];
            int v = a[0];
            if (!map.containsKey(k)) {
                map.put(k, new ArrayList<Integer>());
            } 
            map.get(k).add(v);
            a1[v]++;    
        }
        for (int j=0; j < a1.length; j++) {
            if (a1[j] == 0) {
                var = j;
                break;
            }
        }

        return findOrderInSeries(map, a1, var, totalCourse);
    }

    private static int[] findOrderInSeries(HashMap<Integer, ArrayList<Integer>> map, int[] a1, int var, int totalCourse) {

        int[] arr1 = new int[totalCourse]; 
        Queue<Integer> queue = new LinkedList<Integer>();

        int index = 0;
        for (int i = 0; i < a1.length; i++) {
            if (a1[i] == 0) {
                queue.add(i);
                arr1[index++] = i;
            }
        }
        while (!queue.isEmpty()) {
            int firstElement = queue.poll();
            if (map.get(firstElement) != null) {
                for (int ar : map.get(firstElement)) {
                    a1[ar]--;
                    if (a1[ar] == 0) {
                        queue.offer(ar);
                       arr1[index++] = ar;
                    }
                }
            }
        }
        for (int i = 0; i < a1.length; i++) {
            if (a1[i] != 0) {
                return new int[0];
            }
        }
        return arr1;
    }

}
\$\endgroup\$
  • \$\begingroup\$ "example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]" sure that this is correct? I'd expect the tuple to be [1,0] in that case which looks much more "natural". \$\endgroup\$ – Timothy Truckle Oct 7 '17 at 8:28
1
\$\begingroup\$

Thank you for sharing your code.

Here are my thought on it:

OOP

Your code is a procedural approach to the problem.

There is nothing wrong with procedural approaches in general, but Java is an object oriented (OO) programming language and if you want to become a good Java programmer then you should start solving problems in an OO way.

If you don't care about OOP you should look for a different programming language that better supports procedural or functional approaches.

Naming

Finding good names is the hardest part in programming, so always take your time to think about the names of your identifiers.

Naming Conventions

Please read (and follow) the Java Naming Conventions

Your class name violates the Java naming conventions. Maybe you got the name provided by your teacher. Then you have to use it of cause. But keep in mind that you should not use underscores in your own identifier names (except constants).

avoid single character names / abbreviations

Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable. And/or you have to "reuse" variable names in different contexts. Both makes your code hard to read and understand for other persons. (keep in mind that you are that other person yourself if you look at your code in a few month!) The same is true for (uncommon) abbreviations. You might find them being obvious today, while you're actively dealing with the problem, but You might have to "relearn" them if you worked on something else for a while.

On the other hand in Java the length of identifier names names is virtually unlimited. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

As usual there are some exceptions for this suggestion. E.g. the running index of loops is usually held in a single letter named variable like i in

for(int i =0; i<SOME_CONSTANT; i++)

But even there you should use more problem oriented names to support your readers, especially in nested loops like this:

for(int row =0; row<ENTRY_COUNT; row++)
   for(int column =0; column<ENTRY_FIELD_COUNT; column++)

Choose you names from the problem domain, not from the technical solution.

You have variable names like map, k (as for key) and v (as for value). Better names for them might be like

    int course = a[1];
    int prerequest = a[0];
    if (!prerequestsForCourse.containsKey(course)) {
        prerequestsForCourse.put(course, new ArrayList<Integer>());
    }
    prerequestsForCourse.get(course).add(prerequest);

Magic numbers

your code has some magic numbers. This are literal values with a special meaning like here:

int totalCourse = 0; 
//...
int k = a[1];
int v = a[0];

You should introduce constants with meaningful names:

int totalCourse = INITIAL_COUNT_IS_ZERO; 
//...
int k = a[INDEX_OF_COURSE];
int v = a[INDEX_OF_PREREQUEST];

Know your language / read the API

You are using an legacy pattern to ensure the existence of the the course in the map to the list of its prerequests. You may have found that or have been told to use it. But you should always look at the API of the class or interface you use if there is a better solution. You would have found this https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#computeIfAbsent-K-java.util.function.Function- which would simplify your code to this:

prerequestsForCourse.computeIfAbsent(course,()->new ArrayList()).add(prerequest);

Single Layer Of Abstraction

This principle states that a method (or class) should either do simple/primitive calculations or (exclusive) call other methods (on other objects).

The last line in your method findTotalCourseInOrder() is the call to findOrderInSeries() which let me assume that you already know how to extract a bunch of lines to a separate method. You should do this with the the for loop above too:

private static int[] findTotalCourseInOrder(int totalCourse, int[][] arr) {
    HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    int[] a1 = new int[totalCourse];
    int var = mapPrerequestsToCourses(arr, map, a1);
    return findOrderInSeries(map, a1, var, totalCourse);
}

private static int mapPrerequestsToCourses(int[][] arr, HashMap<Integer, ArrayList<Integer>> map, int[] a1) {
    int var = 0;

    for (int i = 0; i < arr.length; i++) {
        int[] a = arr[i];
        int k = a[1];
        int v = a[0];
        if (!map.containsKey(k)) {
            map.put(k, new ArrayList<Integer>());
        }
        map.get(k).add(v);
        a1[v]++;
    }
    for (int j = 0; j < a1.length; j++) {
        if (a1[j] == 0) {
            var = j;
            break;
        }
    }
    return var;
}

avoid break

break (as well as continue) are javas substitute for goto. Using them leads to code that is both, hard to read and hard to maintain/refactor.

You should not use break outside of a switch block.

An alternative implementation without the break statement could be based on the previous suggestion. In that modification the value returned is the result of the for loop. So you could simply exchange break; by return j;

define variables as late as possible

In all you methods you define all variables right at the top of the method.

In Java this is not needed (as it is in C).

The problem with that is that it confuses your IDEs automated refactoring feature.

E.g.: Your variable var is only used in the last for loop in findTotalCourseInOrder(). If you want to apply the extract method refactoring to this last for loop you get the variable var as a parameter to the new method.

    var = extracted(a1, var);
    return findOrderInSeries(map, a1, var, totalCourse);
}

private static int extracted(int[] a1, int var) {
    for (int j = 0; j < a1.length; j++) {
        if (a1[j] == 0) {
            var = j;
            break;
        }
    }
    return var;
}

If you'd move the declaration of variable var right before the loop you could include this line in the selection and the new method would not have this extra parameter.
Your code:

    int var = 0;
    for (int j = 0; j < a1.length; j++) {
        if (a1[j] == 0) {
            var = j;
            break;
        }
    }
    return findOrderInSeries(map, a1, var, totalCourse);
}

would change to:

    int var = extracted(a1);
    return findOrderInSeries(map, a1, var, totalCourse);
}

private static int extracted(int[] a1) {
    int var = 0;
    for (int j = 0; j < a1.length; j++) {
        if (a1[j] == 0) {
            var = j;
            break;
        }
    }
    return var;
}
| improve this answer | |
\$\endgroup\$

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.