5
\$\begingroup\$

Given a list of Employees ( name and grade). Output the names of the top 2 employees selected for a task(sorted based on grade and then alphabetically).

I am using a maxHeap and override the compareTo method of the Employee class to define the sorting order while initializing the heap .I would like to know if there is a more efficient way(space/time).

The Code:

//Employee class
class Employee implements Comparable<Employee>{
    String name;
    int grade;

    public Employee (String name,int grade){
        this.name = name;
        this.grade = grade;
    }

    @Override
    public int compareTo(Employee e) {
        if(this.grade == e.grade) {
            // if the grades are the same then alphabetical priority
            return e.name.compareTo(this.name);
        } 

        if(this.grade < e.grade) return -1;
            return 1;
        }
    }

Class to build max heap and print out two names

class EmployeePicker {
    public static void main(String[] args) {

        PriorityQueue<Employee> employeeHeap = new PriorityQueue<>(5,Collections.reverseOrder());

        // add 5 employees
        employeeHeap.add(new Employee("Adam", 5));
        employeeHeap.add(new Employee("Annie",7));
        employeeHeap.add(new Employee("Amit", 5));
        employeeHeap.add(new Employee("Carl", 5));
        employeeHeap.add(new Employee("Tom", 4));

        // print first two names 
        System.out.println(employeeHeap.poll().name);
        System.out.println(employeeHeap.poll().name);             
    }            
}
\$\endgroup\$
4
\$\begingroup\$

About performance

As a forewords, I'm not sure you should be obsessed with performance as a beginner (actually I'm pretty sure you should not but surely others will disagree).

Consider reading : https://softwareengineering.stackexchange.com/questions/80084/is-premature-optimization-really-the-root-of-all-evil

With that said...

In the Employee class :

As said by coderodde, your compareTo can't be made faster.

In the EmployeePicker class :

PriorityQueue isn't made with performance in mind. Seeing your code there is no point in using this class over a TreeSet and I'd really recommend using a TreeSet over anything else.

If you really are obsessed with performance, PriorityQueue may outperform a TreeSet when you have over 20_000 elements for your specific use case.

However, if you are really really obsessed with performance and you know all the employees as soon as the program starts (and then only have to retrieve some of them after that) then you should consider using an array that you sort once... it'll also be the most space-efficient solution of the three.

With less than a hundred elements, I'm pretty sure you can consider all solutions equals in performance.

Conclusion : IMO use TreeSet unless you have good reasons not to :)

About code format

You should make the fields of Employee private and final and create getters for them. When a method have multiple parameters, you should always follow the comma with a space (makes code more readable).

The indentation in compareTo is really confusing.

\$\endgroup\$
3
\$\begingroup\$

Your Employee.compareTo runs in worst case \$\Theta(\min(n_1, n_2))\$, where \$n_i\$ is the length of the \$i\$th string, and I am afraid that you cannot improve it.

Even though you did not request any other point to be review, I will take an initiative to review the code.

First of all, you should hide the fields via private keyword.

Add the getters (plus possibly setters) for the fields.

It would not hurt adding toString like this.

public toString() {
    return "[name = \"" + name + "\", grade = " + grade + "]";
}

Now, printing an employee is easy:

System.out.println(employee1);

Hope that helps.

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