I met this question in an interview. The interviewer gave me an class Student like following:

class Student {
    int age;
    String name;

    public Student(int age, String name) {
        this.age = age;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Student{"  
                "age="   age  
                ", name='"   name   '\''  
                '}';
    }
}

He wanted me to implement a PriorityQueue with smallest student's age be highest priority. If there is a tier, he wanted me to use insertion order to break tier, i.e. earliest element with highest priority.

My idea is to use following warper class to encode infomation of timestamp.

class Element implements Comparable<Element> {
    Student student;
    long timestamp = System.currentTimeMillis();

    public Element(Student student) {
        this.student = student;
    }

    @Override
    public int compareTo(Element o) {
        int cmp = Integer.compare(student.age, o.student.age);
        return cmp == 0 ? Long.compare(timestamp, o.timestamp) : cmp;
    }
}

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Element> pq = new PriorityQueue<>();
        Student t1 = new Student(2, "a");
        Student t2 = new Student(2, "b");
        Student t3 = new Student(1, "c");

        pq.offer(new Element(t1));
        pq.offer(new Element(t2));
        pq.offer(new Element(t3));

        System.out.println(pq.poll().student);
        System.out.println(pq.poll().student);
        System.out.println(pq.poll().student);
    }
}

However, the interviewer wanted me not to use timestamp infomation, then I cannot come up with a concrete solution in interview. I can only guess some ideas:

(1) it may require me to use hybrid data structure(combine something like LinkedHashMap/LinkedList and PriorityQueue)

(2) it may require me to implement personal binary minHeap which can break tier by using insertion order. I know how to implement minHeap using percolateUp and percolateDown. However, I never heard I can just hack the binary heap's implemention to use insertion order in algorithm class.

CodePudding user response：

Assign a sequence number in order of arrival. This requires just replacing the line where you assign 'timestamp' with assigning the next value of a monotonically increasing sequence number.

static long nextSequence = 0;
long sequence = nextSequence  ;

and replace your use of 'timestamp' with 'sequence'.

I regard this as superior to use of currentTimeMillis since (a) it allows processing of arrival rates higher than one every millisecond, and (b) the current time is not guaranteed against going backwards.

CodePudding user response：

I've come to the following solution:

• implement a container that wraps a PriorityQueue and track the count of element added to the queue;
• create wrapper over the Student class, which I implemented as a record.

public class OrderedQueue {
    private static final Comparator<StudentWrapper> BY_AGE_AND_QUEUE_ID =
            Comparator.<StudentWrapper>comparingInt(studWr -> studWr.student().getAge())
                    .thenComparingLong(StudentWrapper::queueId);

    private Queue<StudentWrapper> queue;
    private long count;

    public OrderedQueue() {
        this.queue = new PriorityQueue<>(BY_AGE_AND_QUEUE_ID);
    }

    public void addStudent(Student student) {
        queue.offer(new StudentWrapper(student, count  ));
    }

    public Optional<Student> removeStudent() {
        return Optional.ofNullable(queue.poll())
                .map(StudentWrapper::student);
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }

    public static void main(String[] args) {
        OrderedQueue orderedQueue = new OrderedQueue();
        orderedQueue.addStudent(new Student(1, "foo"));
        orderedQueue.addStudent(new Student(2, "a"));
        orderedQueue.addStudent(new Student(2, "b"));
        orderedQueue.addStudent(new Student(1, "bar"));
        orderedQueue.addStudent(new Student(1, "c"));

        while (!orderedQueue.isEmpty()) {
            orderedQueue.removeStudent().ifPresent(System.out::println);
        }
    }
}

record StudentWrapper(Student student, long queueId) {}

Output

Student{age=1, name='foo'}
Student{age=1, name='bar'}
Student{age=1, name='c'}
Student{age=2, name='a'}
Student{age=2, name='b'}