Jumping the queue? Yes, but in constant time

- 5 minutes read - 858 words

The Problem

Classic interview setup: you walk in, sit down, and the interviewer says:

“Design a FastQueue class. It stores entries, where each entry has a long id and a String family.

You need three operations, all in O(1) time: add(entry), removeLast(), and removeLast(family).

Space complexity is O(N) for all operations.”

Let’s unpack that. You have a queue of entries, each tagged with a family group. At any point, you can eject the oldest entry within a given family, all in constant-time.

Initial Thoughts

Let’s draft the initial Entry class as below.

public class EntryImpl implements Entry {

    private final long id;
    private final String family;

    public EntryImpl(long id, String family) {
        this.id = id;
        this.family = family;
    }

    @Override
    public long getId() {
        return id;
    }

    @Override
    public String getFamily() {
        return family;
    }
}

Adding an entry in constant time is straightforward with a list.

Removing the last entry (regardless of family) is equally easy if the list is doubly-linked: holding direct references to head and tail, with each node linked both ways, makes removal at either end - or at any known position O(1) - since you only need to update two pointers.

Removing the last entry of a given family is trickier: you first need to locate the node to evict. That’s where a map keyed by family comes in: it gives you constant-time lookup to find the relevant entry.

First Naive Implementation

public class NaiveQueue {

        private final int maxSize;
        private LinkedList<Entry> queue;
        private Map<String, List<Entry>> map;

        public NaiveQueue(int maxSize) {
            this.maxSize = maxSize;
            this.map = new HashMap<>();
            this.queue = new LinkedList<>();
        }

        public void add(Entry element) throws QueueSizeException {
            if (queue.size() + 1 > maxSize) {throw new QueueSizeException();}

            queue.addLast(element);
            map.computeIfAbsent(element.getFamily(), value -> new ArrayList<>());
            map.get(element.getFamily()).add(element);
        }

        public Entry removeLast() throws QueueSizeException {
            if (queue.isEmpty()) {
                throw new QueueSizeException("Operation not permitted: the queue is empty.");
            }

            Entry removed = queue.removeLast();
            map.get(removed.getFamily()).remove(map.get(removed.getFamily()).size()-1);
            return removed;
        }

        public Entry removeLast(String family) {

            if (Objects.isNull(map.get(family))) throw new IllegalArgumentException("Family does not exists!");
            Entry removed = map.get(family).remove(map.get(family).size()-1);

            // this operation remains O(n)
            queue.remove(removed);

            return removed;
        }

    public static class QueueSizeException extends Exception {
        public QueueSizeException() {
            super("Queue size limit exceeded");
        }

        public QueueSizeException(String message) {
            super(message);
        }

        public QueueSizeException(String message, Throwable cause) {
            super(message, cause);
        }
    }
}

This implementation provides the below specs:

  • add(entry): HashMap.computeIfAbsent is O(1) & ArrayList.add is O(1) amortized.
  • removeLast(): removing the last element of an ArrayList or LinkedList is O(1).
  • removeLast(family): map.get is O(1) but its eviction from the LinkedList is an O(n) operation, oops!

Two out of three operations hit the target but removeLast(family) blows our complexity budget.

Back to the drawing board.

Reframing the Problem

This problem felt a lot like an LRU cache style of question. LRU Cache (Least Recently Used) is a classic design pattern that achieves O(1) get and put by combining two structures: a doubly-linked list to maintain order and allow O(1) removal from any position, and a HashMap for O(1) lookup by key.

Alright, we have the right set of elements but the trick to remain O(1) here is for the map to give you directly which node from the linkedlist needs to be evicted!

How about the HashMap just holds a list of nodes rather than entries?

Each node lives in two places at once: the global doubly-linked list for order, and a per-family bucket for lookup.

Landing Implementation

With minimal changes to the initial implementation, we end up with a data structure that is built to spec!

public class FastQueue {

    private final int maxSize;
    private int size;
    private Node head;
    private Node tail;
    private final Map<String, List<Node>> familyMap = new HashMap<>();

    public FastQueue(int maxSize) {
        this.maxSize = maxSize;
    }

    private static class Node {
        Entry entry;
        Node prev;
        Node next;

        Node(Entry entry) {
            this.entry = entry;
        }
    }

    public void add(Entry entry) throws QueueSizeException {
        if (size + 1 > maxSize) {
            throw new QueueSizeException();
        }

        Node node = new Node(entry);

        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }

        familyMap
                .computeIfAbsent(entry.getFamily(), f -> new ArrayList<>())
                .add(node);
        size++;
    }

    public Entry removeLast() throws QueueSizeException {
        if (tail == null) {
            throw new QueueSizeException("Operation not permitted: the queue is empty.");
        }

        Node node = tail;
        return removeLast(node.entry.getFamily());
    }

    public Entry removeLast(String family) {
        List<Node> familyNodes = familyMap.get(family);
        
        if (familyNodes == null || familyNodes.isEmpty()) {
            throw new IllegalArgumentException("Family does not exist!");
        }

        Node node = familyNodes.remove(familyNodes.size()-1);
        removeNode(node);

        if (familyNodes.isEmpty()) {
            familyMap.remove(family);
        }

        size--;
        return node.entry;
    }

    private void removeNode(Node node) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }

        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
    }

    public static class QueueSizeException extends Exception {
        public QueueSizeException() {
            super("Queue size limit exceeded");
        }

        public QueueSizeException(String message) {
            super(message);
        }

        public QueueSizeException(String message, Throwable cause) {
            super(message, cause);
        }
    }
}

We’ll note the removeLast() method simply wraps the more complex removeLast(family) method because the global tail is always the last element of its own family’s bucket.

Now, all three operations are O(1). ✓

References