Jumping the queue? Yes, but in constant time
- 5 minutes read - 858 wordsThe Problem
Classic interview setup: you walk in, sit down, and the interviewer says:
“Design a
FastQueueclass. It stores entries, where each entry has along idand aString family.You need three operations, all in O(1) time:
add(entry),removeLast(), andremoveLast(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.computeIfAbsentis O(1) &ArrayList.addis O(1) amortized.removeLast(): removing the last element of anArrayListorLinkedListis O(1).removeLast(family):map.getis O(1) but its eviction from theLinkedListis 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). ✓