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();
}
}
List prerequisitesshould beList<String> prerequisites. \$\endgroup\$ – Martin Schröder Apr 14 '12 at 10:14