8
\$\begingroup\$

I recently graduated from college and applied for a position with a company. I was sent a coding exercise as part of the process. After completing the exercise and submitting it I was told that the code provided the correct solution but was too hard to follow, the logic should be in the Course class, and "..due to refactoring requirements." (I'm not sure what that means).

I know that I have a lot to learn and that I am still a novice programmer, but I was wondering if I could get some constructive suggestions from more experienced developers as to what needs to be changed in my code?

The basic requirements are: Takes a String[] that contains the courses you must take and returns a String[] of courses in the order the courses should be taken so that all prerequisites are met. Validation is to be done on each course description and course names. Return an empty string[] if an error occurs.

Examples of valid input Strings are: "CSE111: CSE110 MATH101" "CSE110:"

public class Course {
    private String courseName;
    private List prerequisites;


    public Course() {
        this.prerequisites = new ArrayList();
    }

    public void setCourseName(String courseName) {
        this.courseName = courseName;
    }

    public String getCourseName() {
        return courseName;
    }

    public List getPrerequisites() {
        return prerequisites;
    }

    public void addPrerequisite(String prerequisite) {
        prerequisites.add(prerequisite);
    }

    public int getCourseNumber() throws InvalidCourseNameException {
        int courseNumber = -1;
        try {
            if (courseName != null && courseName.length() > 3) {
                courseNumber = Integer.parseInt(courseName.substring(courseName.length() - 3));
            }
        } catch (NumberFormatException e) {
            throw new InvalidCourseNameException(e.getMessage());
        }
        return courseNumber;
    }
}

public class CourseScheduler {
    private Map availableCourses;
    private List schedule;
    private static final int COURSE_NUMBER_LENGTH = 3;


    public CourseScheduler() {
        // use a treemap to attempt to order classes by course number, in ascending order
        // or if courses have the same course number, order alphabetically by course name
        this.availableCourses = new TreeMap(new Comparator() {
            public int compare(Object courseNameOne, Object courseNameTwo) {
                String courseOneNumber = ((String) courseNameOne).substring(((String) courseNameOne).length() - COURSE_NUMBER_LENGTH);
                String courseTwoNumber = ((String) courseNameTwo).substring(((String) courseNameTwo).length() - COURSE_NUMBER_LENGTH);
                int comparison = courseOneNumber.compareTo(courseTwoNumber);
                if (comparison == 0) {
                    return ((String) courseNameOne).compareTo((String) courseNameTwo);
                } else {
                    return comparison;
                }
            }
        });
    }

    /**
     * Create a schedule from the courses provided.
     * @param param0 The courses and there prerequisites that are required to be taken
     * @return an empty String array if an error occurs or a schedule can not be created,
     * a String array beginning with the first class to be taken and ending with the last class
     */
    public String[] scheduleCourses(String[] param0) {
        schedule = new ArrayList();

        if (param0 != null) {
            try {
                for (int i = 0; i < param0.length; i++) {
                    if (isValidCourseDescription(param0[i])) {
                        addCourseToAvailableCourses(param0[i]);
                    } else {
                        throw new InvalidCourseDescriptionException("Invalid course description: " + param0[i]);
                    }
                }

                buildSchedule();
            } catch (InvalidCourseNameException e) {
                System.out.println(e.getMessage());
            } catch (InvalidCourseDescriptionException e) {
                System.out.println(e.getMessage());
            }
        }

        String[] classes = new String[schedule.size()];
        classes = (String[]) schedule.toArray(classes);
        return classes;
    }


    ///////////////////////
    // private functions //
    ///////////////////////


    /**
     * Builds the class schedule from the available courses.
     * @throws InvalidCourseNameException if an invalid course name is found
     */
    private void buildSchedule() throws InvalidCourseNameException{
        Map temp = new TreeMap(availableCourses);
        int numberOfAvailableCourses = availableCourses.size();

        while (schedule.size() < numberOfAvailableCourses) {
            Course courseToAdd = null;
            Iterator it = temp.keySet().iterator();
            while (it.hasNext()) {
                String key = (String) it.next();
                Course course = (Course) temp.get(key);

                // the course has already been added to the schedule
                if (schedule.contains(course.getCourseName())) {
                    continue;
                }

                if (havePrerequisitesBeenTaken(course)) {
                    if (courseToAdd == null) {
                        courseToAdd = course;
                    } else if (course.getCourseNumber() < courseToAdd.getCourseNumber()) {
                        courseToAdd = course;
                    } else if (course.getCourseName().compareTo(courseToAdd.getCourseName()) < 0) {
                        courseToAdd = course;
                    }
                }
            }

            if (courseToAdd != null) {
                schedule.add(courseToAdd.getCourseName());
                // so we don't keep checking the available courses we have processed
                temp.remove(courseToAdd.getCourseName());
            } else {
                // we should always have a course to add after checking the classes
                // something is wrong so clear the schedule and return
                schedule.clear();
                return;
            }
        }
    }

    /**
     * Checks if the prerequisites for the course have been taken.
     * @param course The course to check
     * @return true if the course does not have prerequisites or the prerequisites
     * have been taken, false otherwise
     */
    private boolean havePrerequisitesBeenTaken(Course course) {
        List prerequisites = course.getPrerequisites();

        if (prerequisites == null || prerequisites.size() == 0) {
            return true;
        }

        for (int i = 0; i < prerequisites.size(); i++) {
            if (!schedule.contains(prerequisites.get(i)) || !havePrerequisitesBeenTaken((Course) availableCourses.get(prerequisites.get(i)))) {
                return false;
            }
        }
        return true;
    }

    /**
     * Add a course object to the available courses using the data from the course description.
     * @param courseDescription The course description to add 
     * @throws InvalidCourseNameException if an invalid course name is found for the course or its prerequisites
     */
    private void addCourseToAvailableCourses(String courseDescription) throws InvalidCourseNameException {
        Course course = new Course();
        int colonIndex = courseDescription.indexOf(':');

        String courseName = courseDescription.substring(0, colonIndex);

        if (isValidCourseName(courseName)) {
            course.setCourseName(courseDescription.substring(0, colonIndex));
            String prerequisites = courseDescription.substring(colonIndex);

            if (prerequisites.length() > 1) {
                prerequisites = prerequisites.substring(1);
                StringTokenizer tokenizer = new StringTokenizer(prerequisites, " ");
                while (tokenizer.hasMoreTokens()) {
                    String prerequisite = tokenizer.nextToken();
                    if (isValidCourseName(prerequisite)) {
                        course.addPrerequisite(prerequisite);
                    } else {
                        throw new InvalidCourseNameException("Invalid course name: " + courseName);
                    }
                }
            }
        } else {
            throw new InvalidCourseNameException("Invalid course name: " + courseName);
        }

        availableCourses.put(courseName, course);
    }

    /**
     * Determine if the course name follows the valid pattern -
     * 3-4 upper case characters followed by a number from 000 - 999.
     * @param courseName The course name to validate
     * @return true if the course name matches the pattern, false otherwise
     */
    private boolean isValidCourseName(String courseName) {
        // validate the course name - i.e. "CSE111" or "MATH999"
        Pattern courseNamePattern = Pattern.compile("^[A-Z]{3,4}[1-9][0-9]{2}$");
        Matcher matcher = courseNamePattern.matcher(courseName);

        return matcher.matches();
    }

    /**
     * Determine if the course description follows the valid pattern -
     * {course name}:[ {course name} {course name}].
     * @param courseDescription The course description to validate
     * @return true if the course description matches the pattern, false otherwise
     */
    private boolean isValidCourseDescription(String courseDescription) {
        // validate the course description - i.e. "CSE111: CSE110 MATH101"
        // or "CSE110:"
        Pattern courseDescriptionPattern = Pattern.compile("^[A-Z]{3,4}[1-9][0-9]{2}(:$|:(\\s[A-Z]{3,4}[1-9][0-9]{2})+)");
        Matcher matcher = courseDescriptionPattern.matcher(courseDescription);

        return matcher.matches();
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Please read again the section on generics in a recent Java book. You have it wrong. List prerequisites should be List<String> prerequisites. \$\endgroup\$ – Martin Schröder Apr 14 '12 at 10:14
  • \$\begingroup\$ please use "descriptive" title in future. \$\endgroup\$ – Aquarius_Girl May 21 '12 at 5:45
15
\$\begingroup\$

A class should know & do everything about itself

  • IsValidCourseName and isValidCourseDescription should be in the Course class

Design should reflect your domain

  • What are we talking about here? A University, yes? Use that to frame your design. What things are in there and what do we do with them? What attributes to these things have?

  • I think there should be a Schedule class. This schedule may be ordered, i.e. "scheduled" or it may be unordered, i.e. "just a list of courses I've signed up for."

  • Maybe a Schedule has a boolean to indicated that it's been scheduled, or maybe theres a separate class CourseLoad to encapsulate the idea that this is a list of courses not yet scheduled.

  • Maybe a CourseCatalog should encapsulate all the "available courses" stuff.

  • Then client code is necessarily written & reads in terms of your business model. e.g. compare: public String[] scheduleCourses(String[] param0) and public Schedule scheduleCourses(CourseLoad newCourseLoad). It becomes virtually self documenting.

  • You should get 10 lashes for every parameter name like param0

  • havePrerequisitesBeenTaken() is totally baffling. Where the hell did courseDescription come from? It's not in Course. The actual code suggests that if a course has a prerequisite then, by definition, it has not been taken. Yet your comments say otherwise. That makes no sense. And I had to study the code too much to figure that out.

I like the CourseScheduler as a separate class

  • Separating out complex algorithms is a good way to contain complexity and keep other classes cleaner and clearer. This separation enhances maintenance.

  • Single Responsibility Principle (SRP) says a class should do only one thing. In this case "schedule courses." It should not be building the available courses prerequisite map.

Design & coding principles are fractal

  • A fractal is a self-similar pattern, and likewise good design principles should be applied at all levels of your code. Abstraction and encapsulation apples at module, class, method, code block levels.

  • I.E. make classes, methods, code bits as needed to express things in business and process terms as much as practical. "Push details down". Otherwise you tend to obscure what's going on.

  • buildSchedule() is just one such method that is cluttered and it's function is not readily apparent without some deliberate diving into the details. Yes, at some point the code must do what it does, but at the conceptual level of "how to build a schedule" I want to see the conceptual steps expressed.

  • The CourseScheduler class is cluttered because it's doing more than just producing a schedule. Specifically it seems to be the course catalog as well.

Refactoring

Refactoring is a term with a technical meaning. Refactoring is the act of changing code without changing it's behavior (i.e. without breaking it!). There is an excellent book on the subject that should be on every programmer's bookshelf - hear me now and believe me later.

Good OO design significantly enhances your ability to refactor. So what, you say? Invariably code must be changed, either to fix bugs or add functionality. So the act of refactoring really starts with a software design that is flexible and extensible.

Refactoring is not a measure of design quality. It is not what you do only after you've delivered your final product. It is what you do from the very beginning of writing your code, staring with a blank sheet of paper (metaphorically speaking, of course). Continuous Refactoring means write what you need now. As you add stuff, refactor as needed to (a) not break what you have (b) apply and maintain good design and coding principles when adding code and (c) ultimately enhance future changes.

  • buildSchedule() should have the catalog & student's course list passed into it. Now buildSchedule can deal with any catalog and any course list. If the catalog mapping algorithm changes, buildSchedule() does not change.

  • When you have complex or obscure logic consider refactoring. Compare: if (prerequisites == null || prerequisites.size() == 0) vice if(course.prerequisitesAreMet()). Note that (a) As changed I can tell what's going and (b) the original code is not in the Course class, yet it has to know how to figure out prerequisites for the stupid course.

Good luck!

\$\endgroup\$
6
\$\begingroup\$

Yes, this code is hard to follow. Some thoughts:

  • use generics, e.g. private List<String> prerequisites
  • Provide useful constructors. E.g. Does a course without name make any sense? If not, the course name should be a constructor parameter
  • honour encapsulation, prefer immutable data. Is it ever required to rename an existing course? If not, setCourseName shouldn't be public
  • use the right representation. E.g. you often need the course prefix and the course number. Maybe it would be the best to split the course name already in the constructor, and store the parts, not the full name. This is also in the spirit of a "fail early" strategy.

If I have time, I'll look deeper in the code. I think there are probably much more things that could be improved.

\$\endgroup\$
  • \$\begingroup\$ Thanks Landei. On your comment regarding "..storing the parts, not the full name. This is also in the spirit of "fail early" strategy." Would it be correct to validate the incoming course name in the constructor? So would I throw an exception from the constructor if the course name was bad? \$\endgroup\$ – user1331369 Apr 13 '12 at 15:19
  • \$\begingroup\$ Yes. It's always good to check things, and to give an early and precise feedback about what's wrong with it, instead of letting it explode somwhere in the guts of your application. You should be especially cautious of null values. \$\endgroup\$ – Landei Apr 13 '12 at 19:04
2
\$\begingroup\$

It seems to me, that according to your use of Course the code would be better if you:

  1. add parameters to ctor (course name, and prerequisites)
  2. make courses Comparable

Then you can verify if the course name is in proper format and split it by parts (name and number) once and forever, and implement courses comparition logic inside the class, avoiding ugly code in client's classes. It will significantly improve encapsulation and release client's code from details of course class.

If ctor finds that something wrong with course name/number, whatever, it may throw an exception.

\$\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.