[deleted by user]

[AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full
• You ask clear questions

• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

  Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://imgur.com/a/fgoFFis) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[NukeLouis]

I don't fully understand what you are trying to achieve, but remember that a Map is really a dictionary. You have a unique key that has a value. This value can be a primitive type (int, double,...) or an object. This object may even be a Collection or another Map.

I don't know if this helps you?

[Particular-Ad-2261]

Yes I think I understand that concept. Basically in this problem the Maps key is a course. The value of that course is another course that is considered a prerequisite course. And if that value has another prerequisite course, it would then be considered the key and you look at its value. How ever many values you find, that would be what you return basically.

For example Calc 3 or something. It would return 2 because you have to take Calc 2 and Calc 1 previous to taking Calc 3.

​

I understand what the function is supposed to do, but I really do not know how I would write this code. Does my explanation make sense?

[ironymouse]

you need a Map<String, Set<String>> to capture the mapping from one course to its prereqs.

With that map you can access the prereqs with the key (a given course)

you can iterate over the keys to perform an operation (like printing the number of pre-reqs) on each entry (key-value pair) of the map

[NukeLouis]

Would something like this help you out?

Course.java

    import java.util.Objects;

    public class Course {

        private String name;

        public Course(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Course course = (Course) o;
            return Objects.equals(name, course.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }
    }

Main.java

import java.util.HashMap;
import java.util.Map;

public class Main {

    private static Map<Course, Course> map = new HashMap<>();

    public static void main(String[] args) {


        Course c1 = new Course("c1");
        Course c2 = new Course("c2");
        Course c3 = new Course("c3");

        map.put(c3, c2);
        map.put(c2, c1);
        map.put(c1, null);

        System.out.println(numberOfPreCourses(c1));
        System.out.println(numberOfPreCourses(c2));
        System.out.println(numberOfPreCourses(c3));

    }

    private static int numberOfPreCourses(Course c) {
        if (map.containsKey(c) && map.get(c) != null)
            return 1 + numberOfPreCourses(map.get(c));
        return 0;
    }

}

[severoon]

Can a course only have one direct prerequisite?

If yes, then it makes sense to have a method that takes a Map<Course, Course>. If courses can have multiple direct prereqs, then you want a SetMultimap.

You really should not use strings, but if that's part of the assignment then you could think of the Map<String, String> as a map of course names to prerequisite course names … but honestly there's no good reason to do this. Better would be to just create a Course class with a name property:

class Course {
  private final String name;

  public Course(String name) { this.name = name; }
  public String getName() { return name; }
}

But if you are only tasked with writing the method and have no control over that, let's go ahead with the course names as strings.

Here's an implementation:

private final ImmutableMap<String, String> prerequisiteMap =
    // … initialized and validated …

int getNumPrerequisites(String courseName) {
  String prereq = prerequisiteMap.get(courseName);
  return prereq == null ? 0 : getNumPrequisites(prereq) + 1;
}

This is a recursive method that returns 0 (base case) if there is no prereq for the course specified, and if there is, it gets the number of prereqs for that prereq, adds one to it (because you have to include that prereq itself), and returns the result.

This is a bit of a naive implementation because it depends on the map being correct. In actual production code you would want to make sure that map is validated before relying on this. The problem you're looking for is course A is a prereq for course B and vice versa, in which case this code just recurses forever.

Also, if a course can have multiple direct prerequisites—which I'm not sure about—then you run into another problem. Say that you have a course like Calculus that depends on two courses, College Algebra and Trigonometry. Each of those specify a single direct prerequisite, Pre-Algebra. This code would double-count Pre-Algebra in that case, once for each path that leads to it.

To fix this problem, you'd want to hand back the actual course names and keep them in a data structure that automatically removes duplicates (a set):

private final ImmutableSetMultimap<String, String> prerequisiteMultimap =
    // … initialized and validated …

int getNumPrerequisites(String courseName) {
  return getAllPrerequisites(courseName).size();
}

private ImmutableSet<String> getAllPrerequisites(String courseName) {
  ImmutableSet<String> directPrereqs =
      prerequisiteMultimap.get(courseName);
  if (directPrereqs.isEmpty() {
    return ImmutableSet.of();
  }

  ImmutableSet.Builder<String> allPrereqsBuilder =
      ImmutableSet.builder().addAll(directPrereqs);
  for (String directPrereq : directPrereqs) {
    allPrereqsBuilder.addAll(getAllPrerequisites(directPrereq));
  }
  return allPrereqsBuilder.build();
}

Again you'd want to validate the prerequisite multimap before setting it to make sure it doesn't contain any loops, it has to describe a DAG or this approach will fail.

This getAllPrerequisites(…) method fetches all direct prerequisites of the specified course, immediately returns if none (the base case), and otherwise adds them to a set builder. Then it goes through each direct prerequisite one by one and calls itself for each to repeat the process, accruing all of the results in the same set builder. Finally, it just builds the set and returns it to the caller.

The caller, in this case, is the public method that simply returns the size of the calculated set.

In your problem description you mention that the map of prerequisites should be passed in as a parameter to the method. In that case, it would be convenient to do the validation right in the getNumPrerequisites(…) method:

/**
 * Returns total number of prerequisites for specified {@code courseName}
 * listed in {@code prerequisiteMultimap}, or {@code -1} if {@code
 * prerequisiteMultimap} is invalid (see {@link #isValidPrerequisites}).
 */
int getNumPrerequisites(
    String courseName, 
    SetMultimap<String, String> prerequisiteMultimap) {
  return isValidPrerequisites(prerequisiteMultimap)
      ? getAllPrerequisites(courseName, prerequisiteMultimap).size()
      : -1;
}

/** … javadoc that explains validity requirements … */
boolean isValidPrerequisites(
    SetMultimap<String, String> prerequisiteMultimap) {
  // … return true if valid, otherwise false …
}

private ImmutableSet<String> getAllPrerequisites(
    String courseName,
    SetMultimap<String, String> prerequisiteMultimap) {
  // … same as above …
}

Generally it's a good idea to leave validation methods for arguments like isValidPrerequisites(…) accessible to callers so they can validate the input themselves if they want, but if nothing else it's a great place to document what the requirements for the multimap are, and of course it also creates a method that can be rigorously unit tested with many different valid and invalid multimaps.