| HashSet | Backed by HashMap; O(1) add/contains; no order guarantee |
| TreeSet | Red-Black tree; NavigableSet + SortedSet; O(log n) ops; sorted order |
| LinkedHashSet | HashMap + doubly-linked list; insertion-order iteration; O(1) ops |
| EnumSet | Bit-vector backed; enum-only; O(1) all ops; most compact Set |
| Set.of() (Java 9+) | Immutable; throws UnsupportedOperationException on mutation; no nulls |
| Queue offer/poll/peek | Returns false/null on failure — no exceptions thrown |
| Queue add/remove/element | Throws NoSuchElementException / IllegalStateException on failure |
| ArrayDeque | Resizable array; faster than LinkedList as Deque; no null elements |
| PriorityQueue | Binary min-heap by default; O(log n) offer/poll; O(1) peek |
| BlockingQueue | Thread-safe; blocks on put/take; used for producer-consumer pattern |
SortedSet/NavigableSet
Immutable
Queue+Deque
variants
Set Implementations — Interview Questions & Answers
Q1. How is HashSet internally implemented in Java?
A: HashSet is backed by a HashMap. Every element added to a HashSet is stored as a key in the underlying HashMap, and the value is a constant dummy object called PRESENT (a static final Object). When you call add(e), it delegates to map.put(e, PRESENT). Because HashMap keys are unique, HashSet guarantees element uniqueness. This means HashSet inherits all of HashMap's characteristics: O(1) average add/remove/contains, no guaranteed iteration order, and uses hashCode()/equals() for element identity.
// Simplified HashSet internals
public class HashSet<E> {
private static final Object PRESENT = new Object();
private transient HashMap<E, Object> map;
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}
Q2. What is the initial capacity and load factor of HashSet?
A: HashSet delegates to HashMap, so the default initial capacity is 16 and the default load factor is 0.75. When the number of elements exceeds capacity * loadFactor (i.e., 12 elements by default), the internal HashMap rehashes and doubles the array size. You can provide custom capacity and load factor via the constructor new HashSet<>(initialCapacity, loadFactor).
Q3. Does HashSet allow null elements?
A: Yes. HashSet allows exactly one null element because the underlying HashMap allows one null key. The null is stored at bucket index 0. In contrast, TreeSet does not allow null (it throws NullPointerException because it cannot compare null using Comparable/Comparator), and Set.of() also disallows null.
Q4. Is HashSet thread-safe?
A: No. HashSet is not synchronized. For concurrent access, use Collections.synchronizedSet(new HashSet<>()) or ConcurrentHashMap.newKeySet(). The latter is preferred because it provides better concurrency by using segment-level locking (or CAS in Java 8+) rather than a single monitor lock.
Q5. What is the internal data structure used by TreeSet?
A: TreeSet is backed by a TreeMap, which uses a Red-Black Tree (a self-balancing BST). Every element in TreeSet is a key in the underlying TreeMap, and the value is again a constant PRESENT object. The Red-Black Tree maintains elements in their natural sorted order (or a custom Comparator order), guaranteeing O(log n) for add, remove, and contains operations.
Q6. What interfaces does TreeSet implement?
A: TreeSet implements NavigableSet, which extends SortedSet, which extends Set. Being a NavigableSet means TreeSet supports navigation methods like lower(e), floor(e), ceiling(e), higher(e), pollFirst(), pollLast(), and range views via subSet(), headSet(), and tailSet().
Q7. How does TreeSet determine element order?
A: TreeSet uses two mechanisms: (1) Natural ordering — elements must implement Comparable, and the compareTo() method is used. (2) Custom ordering — you provide a Comparator to the TreeSet constructor. If neither is provided and the elements don't implement Comparable, a ClassCastException is thrown at runtime when the second element is inserted.
// Natural order
TreeSet<String> natural = new TreeSet<>();
natural.add("banana"); natural.add("apple"); natural.add("cherry");
// Iterates: apple, banana, cherry
// Custom order (reverse)
TreeSet<String> reversed = new TreeSet<>(Comparator.reverseOrder());
reversed.add("banana"); reversed.add("apple");
// Iterates: banana, apple
// Range operations
NavigableSet<Integer> nums = new TreeSet<>(Set.of(1,3,5,7,9));
System.out.println(nums.headSet(5)); // [1, 3]
System.out.println(nums.tailSet(5)); // [5, 7, 9]
System.out.println(nums.subSet(3, 8)); // [3, 5, 7]
System.out.println(nums.floor(6)); // 5
System.out.println(nums.ceiling(6)); // 7
Q8. What is LinkedHashSet and how does it differ from HashSet?
A: LinkedHashSet extends HashSet but maintains a doubly-linked list running through its entries, recording the insertion order. This means iteration over a LinkedHashSet returns elements in the order they were inserted. Performance is slightly worse than HashSet due to the extra linked list maintenance, but still O(1) for add/remove/contains. It is backed by a LinkedHashMap (which itself extends HashMap and adds a linked list).
Q9. When would you choose LinkedHashSet over HashSet or TreeSet?
A: Choose LinkedHashSet when you need: (1) uniqueness of elements, (2) insertion-order iteration, and (3) O(1) operations. HashSet is faster but unordered. TreeSet maintains sorted order but costs O(log n) per operation. LinkedHashSet is the middle ground — predictable iteration order at near-HashSet speed. A common use case is an LRU cache or deduplicating a list while preserving order.
Q10. What is EnumSet and why is it the most efficient Set for enums?
A: EnumSet is a specialized Set implementation for enum types. Internally it uses a bit-vector (long bitmask): each enum constant is assigned an ordinal (0, 1, 2...), and a bit at that position in the long is set to 1 if the element is present. This gives O(1) for all operations with extremely low memory usage. For enums with up to 64 constants, a single long suffices (RegularEnumSet); for larger enums, JumboEnumSet uses a long[]. EnumSet does not allow null elements and is not thread-safe.
enum Day { MON, TUE, WED, THU, FRI, SAT, SUN }
EnumSet<Day> weekdays = EnumSet.range(Day.MON, Day.FRI);
EnumSet<Day> weekend = EnumSet.complementOf(weekdays);
EnumSet<Day> allDays = EnumSet.allOf(Day.class);
EnumSet<Day> none = EnumSet.noneOf(Day.class);
System.out.println(weekdays); // [MON, TUE, WED, THU, FRI]
System.out.println(weekend); // [SAT, SUN]
Q11. What are immutable Sets created by Set.of() (Java 9)?
A: Set.of(e1, e2, ...) returns an immutable Set with fixed elements. Attempting to add, remove, or clear throws UnsupportedOperationException. Null elements are not allowed (NullPointerException). Duplicate elements throw IllegalArgumentException at construction time. The iteration order is unspecified and may change between JVM runs. The returned Set is not serializable in the same way as HashSet.
Q12. What is the difference between Set.of() and Collections.unmodifiableSet()?
A: Both return sets that cannot be mutated through the returned reference. The key difference is that Collections.unmodifiableSet(s) wraps a mutable set — if the underlying set s is modified, the unmodifiable view reflects those changes. Set.of() creates a truly immutable set that cannot change at all. Also, Set.of() rejects nulls and duplicates, while unmodifiableSet allows whatever the backing set allows.
Q13. Provide a time complexity comparison of Set implementations.
A: The table below summarizes average-case time complexities:
| Operation | HashSet | LinkedHashSet | TreeSet | EnumSet |
|---|---|---|---|---|
| add() | O(1) avg | O(1) avg | O(log n) | O(1) |
| remove() | O(1) avg | O(1) avg | O(log n) | O(1) |
| contains() | O(1) avg | O(1) avg | O(log n) | O(1) |
| iteration | O(n+capacity) | O(n) | O(n) | O(n) |
| Null allowed? | Yes (1 null) | Yes (1 null) | No | No |
| Ordering | None | Insertion | Sorted | Enum ordinal |
Q14. How does HashSet handle hash collisions?
A: HashSet delegates to HashMap, which uses chaining for collision resolution. In Java 8+, when the number of entries in a bucket exceeds a threshold of 8 and the overall table size is at least 64, the linked-list chain in that bucket is converted to a balanced Red-Black Tree (treeified), reducing worst-case lookup from O(n) to O(log n). When elements are removed and the bucket size drops below 6, it reverts to a linked list.
Q15. What happens if you add a mutable object to a HashSet and then mutate it?
A: If you mutate an object in a way that changes its hashCode() after it has been added to a HashSet, the HashSet becomes corrupt. The object will still be stored in the bucket corresponding to the old hashCode, but when you call contains() with the mutated object, it computes the new hashCode, looks in the wrong bucket, and returns false — even though the object is in the set. This is a well-known gotcha; always use immutable objects as Set elements, or ensure that the fields used in hashCode/equals are not mutated after insertion.
Queue Operations — Interview Questions & Answers
Q16. What is the Queue interface in Java and what are its two families of operations?
A: Queue is a FIFO (First-In-First-Out) data structure interface extending Collection. It provides two families of methods for each operation: (1) Exception-throwing: add(e), remove(), element(). (2) Special-value (return null/false on failure): offer(e), poll(), peek(). In capacity-constrained queues, add() throws IllegalStateException if full, while offer() returns false. remove() and element() throw NoSuchElementException if empty, while poll() and peek() return null.
Q17. When should you use offer/poll/peek instead of add/remove/element?
A: Prefer offer/poll/peek in most cases: (1) When using capacity-bounded queues (ArrayBlockingQueue, etc.), add() throws on overflow — offer() or put() (blocking) is more appropriate. (2) When you expect the queue to be empty at times, poll() and peek() returning null is cleaner than catching NoSuchElementException. Exception-throwing methods are useful for programming-error detection in contexts where an empty or full queue is truly unexpected.
Q18. What does poll() return when a Queue is empty?
A: poll() returns null when the Queue is empty — it does not throw any exception. This distinguishes it from remove(), which throws NoSuchElementException when the Queue is empty. Similarly, peek() returns null when empty, while element() throws NoSuchElementException.
Q19. Explain the Queue methods comparison in a table.
A:
| Action | Throws Exception | Returns Special Value |
|---|---|---|
| Insert | add(e) — throws IllegalStateException if full | offer(e) — returns false if full |
| Remove head | remove() — throws NoSuchElementException if empty | poll() — returns null if empty |
| Examine head | element() — throws NoSuchElementException if empty | peek() — returns null if empty |
Q20. What is the Deque interface and how does it relate to Queue?
A: Deque (Double-Ended Queue) extends Queue and allows insertion and removal from both ends. It provides: addFirst(e)/offerFirst(e), addLast(e)/offerLast(e), removeFirst()/pollFirst(), removeLast()/pollLast(), peekFirst(), peekLast(). It can serve as both a Queue (FIFO) using addLast/pollFirst, and as a Stack (LIFO) using push()/pop() (which delegate to addFirst/removeFirst).
Q21. How does Deque function as a Stack?
A: Deque has push(e) and pop() methods that make it a stack. push(e) is equivalent to addFirst(e) — it places the element at the front. pop() is equivalent to removeFirst() — it removes and returns the front element, throwing NoSuchElementException if empty. The Java documentation recommends using ArrayDeque (implementing Deque) instead of the legacy Stack class for stack operations.
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10); // addFirst
stack.push(20); // addFirst
stack.push(30); // addFirst
System.out.println(stack.pop()); // 30 (LIFO)
System.out.println(stack.peek()); // 20
// Using as Queue (FIFO):
Deque<Integer> queue = new ArrayDeque<>();
queue.offerLast(1);
queue.offerLast(2);
queue.offerLast(3);
System.out.println(queue.pollFirst()); // 1 (FIFO)
Q22. What is ArrayDeque and why is it preferred over LinkedList as a Deque?
A: ArrayDeque is a resizable array-based implementation of the Deque interface. It is preferred over LinkedList because: (1) No per-node memory overhead — LinkedList allocates a Node object for every element (with prev/next pointers), while ArrayDeque uses a contiguous array. (2) Better cache locality — array elements are adjacent in memory, reducing cache misses. (3) Faster in practice — ArrayDeque benchmarks significantly faster than LinkedList for both stack and queue operations. Caveats: ArrayDeque does not allow null elements; LinkedList does.
Q23. How does ArrayDeque resize internally?
A: ArrayDeque uses a circular array with head and tail indices. The default initial capacity is 16. When the array is full (head == tail after an add), it doubles the capacity. It allocates a new array of twice the size and copies elements. The amortized cost of add operations is O(1). The circular design means elements can wrap around the end of the array back to the beginning, avoiding costly shifts.
Q24. Can ArrayDeque contain null elements?
A: No. ArrayDeque prohibits null elements and throws a NullPointerException if you try to add null. This is by design: since poll() and peek() return null to signal an empty deque, allowing null elements would create ambiguity — you couldn't tell if null means "empty" or "a legitimate null element." LinkedList, by contrast, allows null elements but shares this ambiguity problem with its queue methods.
Q25. Compare ArrayDeque and LinkedList as a Deque.
A:
| Feature | ArrayDeque | LinkedList |
|---|---|---|
| Internal structure | Circular array | Doubly-linked list |
| Null elements | Not allowed | Allowed |
| Memory per element | Low (array slot) | High (Node + 2 pointers) |
| Cache locality | Excellent | Poor (scattered nodes) |
| Random access (get by index) | Not supported by Deque API | O(n) via List API |
| Thread-safe | No | No |
| Preferred for stack/queue | Yes (recommended) | No (legacy use) |
PriorityQueue — Interview Questions & Answers
Q26. What is the internal data structure of PriorityQueue?
A: PriorityQueue uses a binary heap stored in an array. By default it is a min-heap, meaning the element with the smallest value (according to natural ordering or a provided Comparator) is always at the root (index 0), which is what peek() and poll() return. For an element at index i, its children are at 2i+1 and 2i+2, and its parent is at (i-1)/2.
Q27. What are the time complexities of PriorityQueue operations?
A: PriorityQueue time complexities: offer(e) / add(e): O(log n) — element is inserted at the end of the array then sifted up. poll(): O(log n) — root is removed, the last element replaces it, then sifts down. peek(): O(1) — returns the root (array[0]). remove(Object): O(n) — must scan the array to find the element, then O(log n) to re-heapify. contains(Object): O(n) — linear scan. Building a PriorityQueue from a collection: O(n) (Floyd's algorithm).
Q28. How do you create a max-heap PriorityQueue in Java?
A: Pass Comparator.reverseOrder() to the PriorityQueue constructor to create a max-heap.
// Min-heap (default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
System.out.println(minHeap.poll()); // 1
// Max-heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3);
System.out.println(maxHeap.poll()); // 5
// Custom Comparator (sort by string length)
PriorityQueue<String> byLength = new PriorityQueue<>(Comparator.comparingInt(String::length));
byLength.offer("banana"); byLength.offer("fig"); byLength.offer("cherry");
System.out.println(byLength.poll()); // "fig"
Q29. Does PriorityQueue guarantee sorted order during iteration?
A: No. The iterator of PriorityQueue does not traverse elements in priority order. It iterates over the internal array in arbitrary (heap) order. If you need sorted output, repeatedly call poll() until the queue is empty — each poll() gives you the next-minimum element. Alternatively, drain into a List and sort, but that defeats the purpose.
Q30. Does PriorityQueue allow null elements?
A: No. PriorityQueue does not permit null elements and throws NullPointerException if you try to add null. This is because comparison (via Comparable or Comparator) cannot be done on null without a NullPointerException.
Q31. Is PriorityQueue thread-safe?
A: No. PriorityQueue is not synchronized. For concurrent scenarios, use PriorityBlockingQueue from java.util.concurrent, which provides the same heap-based priority ordering but with blocking operations and thread safety.
Q32. What is the initial capacity and how does PriorityQueue grow?
A: The default initial capacity is 11. When the array is full, PriorityQueue grows: if the current capacity is less than 64, it grows by (capacity + 2); otherwise it grows by 50% (capacity / 2). This growth strategy is more conservative than ArrayList's doubling, since heap operations are O(log n) regardless of array size.
Q33. Explain the sift-up and sift-down operations in PriorityQueue.
A: Sift-up (used in offer/add): The new element is placed at the last position in the array. It is then repeatedly compared with its parent at (i-1)/2. If it is smaller than its parent (in a min-heap), they are swapped and the process continues up the tree until the heap property is restored or we reach the root. Sift-down (used in poll): The root is removed and replaced by the last element. This element is then compared with its smaller child. If it is larger, they swap and the process continues down the tree until the heap property is restored or no children remain.
Q34. How do you use PriorityQueue with a custom object?
A: Either make your object implement Comparable, or provide a Comparator to the PriorityQueue constructor.
class Task implements Comparable<Task> {
int priority;
String name;
Task(int p, String n) { this.priority = p; this.name = n; }
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
}
PriorityQueue<Task> taskQueue = new PriorityQueue<>();
taskQueue.offer(new Task(3, "Low"));
taskQueue.offer(new Task(1, "High"));
taskQueue.offer(new Task(2, "Medium"));
System.out.println(taskQueue.poll().name); // "High" (priority=1)
// Or with Comparator:
PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));
Q35. What is the difference between Comparable and Comparator in the context of PriorityQueue?
A: Comparable (java.lang) defines the natural ordering of a class. The class itself implements compareTo(T other). This is the intrinsic ordering and can only be defined once per class. Comparator (java.util) is an external strategy object that defines a custom ordering. You can have multiple Comparators for the same class. In PriorityQueue: if no Comparator is provided, elements must implement Comparable and natural ordering is used. If a Comparator is provided in the constructor, it takes precedence and elements need not implement Comparable.
Q36. How would you find the k-th largest element using PriorityQueue?
A: Use a min-heap of size k. Iterate through the array: add each element; if the heap size exceeds k, poll the minimum. After processing all elements, the heap's root (peek) is the k-th largest element. Time: O(n log k). Space: O(k).
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
for (int num : nums) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek(); // k-th largest
}
BlockingQueue & Concurrent Queues — Interview Questions & Answers
Q37. What is BlockingQueue and what problem does it solve?
A: BlockingQueue (java.util.concurrent) is a thread-safe queue that additionally supports blocking operations: put(e) — blocks if the queue is full until space becomes available. take() — blocks if the queue is empty until an element becomes available. This makes it ideal for the producer-consumer pattern without explicit synchronization. The producer calls put() and blocks if the buffer is full; the consumer calls take() and blocks if the buffer is empty. Timed variants: offer(e, timeout, unit) and poll(timeout, unit).
Q38. What are the four sets of operations in BlockingQueue?
A: BlockingQueue supports four operation categories: (1) Throws exception: add/remove/element. (2) Returns special value: offer/poll/peek. (3) Blocks indefinitely: put/take. (4) Blocks with timeout: offer(e, time, unit) / poll(time, unit). The blocking operations are the key addition over plain Queue.
Q39. What is LinkedBlockingQueue?
A: LinkedBlockingQueue is a BlockingQueue backed by linked nodes. It can be optionally bounded (by specifying capacity in the constructor) or unbounded (default Integer.MAX_VALUE capacity). It uses two separate locks: one for put operations (putLock) and one for take operations (takeLock), allowing puts and takes to proceed concurrently as long as the queue is neither full nor empty. This gives higher throughput than ArrayBlockingQueue in high-concurrency scenarios.
Q40. What is ArrayBlockingQueue?
A: ArrayBlockingQueue is a bounded BlockingQueue backed by a fixed-size circular array. Capacity must be specified at construction and cannot change. It uses a single ReentrantLock for both put and take operations, meaning puts and takes cannot proceed concurrently. It supports a fairness policy (FIFO among waiting threads if fair=true, but at the cost of throughput). Use when you need a fixed-size buffer and predictable memory usage.
Q41. What is PriorityBlockingQueue?
A: PriorityBlockingQueue is an unbounded BlockingQueue that uses a binary min-heap (same as PriorityQueue) for priority ordering. It is thread-safe and supports blocking take(). Since it is unbounded, put() never actually blocks (though it may throw OutOfMemoryError). Elements must implement Comparable or a Comparator must be provided. Null elements are not permitted.
Q42. What is SynchronousQueue?
A: SynchronousQueue is a special BlockingQueue with zero internal capacity. Each put() must wait for a corresponding take(), and vice versa — the producer and consumer must synchronize (rendezvous) directly. It is used in thread pool implementations (e.g., Executors.newCachedThreadPool() uses SynchronousQueue) where tasks are handed off directly to worker threads without buffering. It is not suitable for buffered producer-consumer scenarios.
Q43. What is DelayQueue?
A: DelayQueue is an unbounded BlockingQueue that orders elements by their delay expiration time. Elements must implement the Delayed interface, which provides a getDelay(TimeUnit) method. poll() and take() only return elements whose delay has expired. It is used for scheduling: task schedulers, session expiry, cache eviction. A common example is a scheduled future task where the element is available only after a specified delay.
Q44. What is TransferQueue and how does it differ from BlockingQueue?
A: TransferQueue (Java 7+) extends BlockingQueue with a transfer(e) method. Unlike put() which simply enqueues and returns, transfer() blocks until another thread takes the element. This provides a stronger handoff guarantee. The most common implementation is LinkedTransferQueue, which also provides tryTransfer(e) (returns false immediately if no consumer is waiting) and tryTransfer(e, timeout, unit). It is useful when the producer needs confirmation that the consumer actually received the element.
Q45. What is ConcurrentLinkedQueue?
A: ConcurrentLinkedQueue is a non-blocking, thread-safe, unbounded queue based on a lock-free linked node algorithm (Michael-Scott queue algorithm using CAS — Compare-And-Swap). It does not block on offer or poll. When the queue is empty, poll() returns null immediately. It is suitable for high-throughput, non-blocking producer-consumer scenarios where you do not need the queue to block. Unlike BlockingQueue variants, it has no put/take blocking semantics.
Q46. Compare the concurrent queue implementations.
A:
| Class | Bounded | Blocking | Ordered By | Use Case |
|---|---|---|---|---|
| LinkedBlockingQueue | Optional | Yes | FIFO | General producer-consumer |
| ArrayBlockingQueue | Yes (fixed) | Yes | FIFO | Fixed buffer, predictable memory |
| PriorityBlockingQueue | No | take() blocks | Priority | Priority-based task scheduling |
| SynchronousQueue | 0 (no buffer) | Yes | Direct handoff | Cached thread pool |
| DelayQueue | No | Yes | Delay expiry | Scheduled tasks, cache expiry |
| ConcurrentLinkedQueue | No | No | FIFO | Non-blocking, high-throughput |
| LinkedTransferQueue | No | Yes (transfer) | FIFO | Guaranteed handoff |
Algorithms with Set, Queue & Deque — Interview Questions & Answers
Q47. How is Queue used in BFS (Breadth-First Search)?
A: BFS uses a Queue to explore nodes level by level. Start by enqueuing the source node and marking it visited. Dequeue a node, process it, then enqueue all its unvisited neighbors. Repeat until the queue is empty. ArrayDeque is the preferred Queue implementation for BFS.
public void bfs(Map<Integer, List<Integer>> graph, int start) {
Queue<Integer> queue = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.getOrDefault(node, List.of())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
Q48. How is Deque used for palindrome checking?
A: Add all characters to a Deque. Then compare pollFirst() and pollLast() in a loop. If all pairs match, it is a palindrome.
public boolean isPalindrome(String s) {
Deque<Character> deque = new ArrayDeque<>();
for (char c : s.toCharArray()) deque.offer(c);
while (deque.size() > 1) {
if (!deque.pollFirst().equals(deque.pollLast())) return false;
}
return true;
}
Q49. How is Deque used in the sliding window maximum problem?
A: Use a monotonic deque (decreasing from front to back) that stores indices. For each new element: remove from the back any indices whose elements are smaller than the current (they can never be the window max). Remove the front if it falls outside the current window. The front always holds the index of the current window maximum.
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new ArrayDeque<>(); // stores indices
for (int i = 0; i < n; i++) {
// Remove elements outside window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1)
deque.pollFirst();
// Remove smaller elements from back
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
deque.pollLast();
deque.offerLast(i);
if (i >= k - 1)
result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}
Q50. How do you implement a min-stack using Deque?
A: Maintain two deques: the main stack and an auxiliary min-deque. On push, push to the main stack; push to min-deque only if the new element is less than or equal to the current minimum. On pop, pop from main stack; if the popped element equals the top of min-deque, also pop min-deque. peek-min returns the top of min-deque.
Q51. How is a Queue used to implement BFS for shortest path in an unweighted graph?
A: Unweighted shortest path via BFS: maintain a distance array initialized to -1. Set distance[source] = 0. When dequeuing node u and discovering neighbor v, set distance[v] = distance[u] + 1 and enqueue v. Since BFS explores level by level, the first time a node is reached gives the shortest distance.
Q52. What is a monotonic queue and how does it differ from a standard queue?
A: A monotonic queue maintains elements in a monotonically increasing or decreasing order. It is typically implemented using a Deque. Elements are removed from one end when the invariant is violated. Standard queues (FIFO) don't enforce any ordering of elements. Monotonic queues are used in problems requiring range minimum/maximum efficiently, like the sliding window maximum.
Advanced Set Operations — Interview Questions & Answers
Q53. How do you perform set intersection, union, and difference in Java?
A: Use retainAll for intersection, addAll for union, and removeAll for difference. Note these mutate the set.
Set<Integer> a = new HashSet<>(Set.of(1, 2, 3, 4));
Set<Integer> b = new HashSet<>(Set.of(3, 4, 5, 6));
// Union
Set<Integer> union = new HashSet<>(a);
union.addAll(b); // {1,2,3,4,5,6}
// Intersection
Set<Integer> intersection = new HashSet<>(a);
intersection.retainAll(b); // {3,4}
// Difference (a - b)
Set<Integer> diff = new HashSet<>(a);
diff.removeAll(b); // {1,2}
Q54. What is the CopyOnWriteArraySet?
A: CopyOnWriteArraySet is a thread-safe Set backed by a CopyOnWriteArrayList. On every write (add/remove), a fresh copy of the array is made, so reads never need locking. It is suitable for use cases where reads are far more frequent than writes, and the set is small. Iteration is safe even during concurrent modification (iterates over a snapshot). Uniqueness is maintained by linear scan — add is O(n).
Q55. How does TreeSet's subSet() differ from its headSet() and tailSet()?
A: All three return a view (not a copy) of a portion of the TreeSet. subSet(fromElement, toElement): elements from fromElement (inclusive) to toElement (exclusive). headSet(toElement): all elements strictly less than toElement. tailSet(fromElement): all elements greater than or equal to fromElement. Java 6+ NavigableSet variants allow specifying inclusivity: subSet(from, fromInclusive, to, toInclusive). The views are backed by the original set — changes to the view are reflected in the original and vice versa.
Q56. What is the difference between TreeSet.floor() and TreeSet.lower()?
A: Both return the greatest element less than or equal to / less than the given element. floor(e): returns the greatest element less than or equal to e (inclusive of e). lower(e): returns the greatest element strictly less than e (exclusive). Similarly, ceiling(e) returns the least element >= e, and higher(e) returns the least element strictly > e. All return null if no such element exists.
Q57. What is the WeakHashMap-based Set?
A: There is no WeakHashSet in the JDK, but you can create one with Collections.newSetFromMap(new WeakHashMap<>()). The resulting Set holds weak references to elements, so elements can be garbage-collected if no other strong references exist. This is useful for tracking live objects (e.g., listeners) without preventing GC.
Q58. What is IdentityHashSet?
A: There is no IdentityHashSet, but you can create one with Collections.newSetFromMap(new IdentityHashMap<>()). Elements are compared using reference equality (==) instead of equals(), and identity hash code (System.identityHashCode) instead of hashCode(). Useful for tracking object identity, e.g., detecting object graph cycles.
Q59. How does Set.copyOf() differ from new HashSet(collection)?
A: Set.copyOf(collection) (Java 10+) returns an unmodifiable Set containing the elements of the given collection. Null elements throw NullPointerException. The result is not guaranteed to be a HashSet — it is an implementation-specific unmodifiable set. new HashSet(collection) creates a mutable HashSet with the same elements, allows nulls, and has HashSet-specific characteristics.
Q60. How do you remove duplicates from a List while preserving order using Sets?
A: Use LinkedHashSet: pass the list to its constructor, then convert back to List. LinkedHashSet maintains insertion order and removes duplicates in O(n) time.
List<Integer> withDups = List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3);
List<Integer> unique = new ArrayList<>(new LinkedHashSet<>(withDups));
System.out.println(unique); // [3, 1, 4, 5, 9, 2, 6]
More PriorityQueue & Deque Deep-Dive — Interview Questions & Answers
Q61. How do you merge k sorted lists using PriorityQueue?
A: Create a min-heap. Add the first element of each list along with the list index and element index. Poll the min element, add it to the result, then add the next element from the same list to the heap. Repeat. Time: O(N log k) where N is total elements and k is number of lists.
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>(
Comparator.comparingInt(n -> n.val)
);
for (ListNode node : lists) if (node != null) pq.offer(node);
ListNode dummy = new ListNode(0), cur = dummy;
while (!pq.isEmpty()) {
cur.next = pq.poll();
cur = cur.next;
if (cur.next != null) pq.offer(cur.next);
}
return dummy.next;
}
Q62. What is the time complexity of building a PriorityQueue from an existing collection?
A: O(n) using Floyd's heapify algorithm. When you call new PriorityQueue<>(collection), Java uses the heapify operation which starts from the middle of the array and sifts down each element. This is more efficient than inserting n elements one by one (which would be O(n log n)).
Q63. How does ArrayDeque handle the circular array wrap-around?
A: ArrayDeque maintains head and tail pointers into the internal array. Elements are stored between head (inclusive) and tail (exclusive). When tail reaches the end of the array, it wraps to 0 using modular arithmetic: (tail + 1) & (elements.length - 1). Since the array size is always a power of two, bitwise AND is used instead of modulo for efficiency. Elements wrap around the end of the array to the beginning.
Q64. Can PriorityQueue be used for Dijkstra's algorithm?
A: Yes. Dijkstra's shortest path algorithm uses a min-heap to greedily pick the unvisited node with the smallest tentative distance. PriorityQueue with a custom Comparator (or Comparable) on distance works well. However, standard PriorityQueue does not support decrease-key (updating an existing element's priority) efficiently (O(n) remove + O(log n) add). For performance-critical code, use a Fibonacci heap or work around decrease-key by adding duplicate entries and ignoring stale ones.
// Dijkstra with PriorityQueue (lazy deletion approach)
public int[] dijkstra(int n, List<int[]>[] graph, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, src}); // {distance, node}
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue; // stale entry, skip
for (int[] edge : graph[u]) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}
Q65. What is a Double-Ended Priority Queue?
A: A Double-Ended Priority Queue (DEPQ) supports efficient access to both the minimum and maximum element. Java does not have a built-in DEPQ, but you can simulate one using two PriorityQueues (one min-heap, one max-heap) kept in sync, or by using a TreeMap which provides O(log n) firstKey() and lastKey().
Q66. How is PriorityQueue different from TreeSet for maintaining sorted elements?
A: TreeSet maintains all elements sorted at all times and supports O(log n) access to any element, range queries, floor/ceiling operations. PriorityQueue only guarantees that the minimum (or maximum) is at the top; the remaining elements are not necessarily sorted. PriorityQueue allows duplicates; TreeSet does not. PriorityQueue poll() removes the min in O(log n); TreeSet pollFirst()/pollLast() also O(log n). For streams of data where you only care about the top element, PriorityQueue is more memory-efficient and simpler.
Q67. How can you make a thread-safe PriorityQueue in Java?
A: Options: (1) Use PriorityBlockingQueue from java.util.concurrent — directly equivalent to PriorityQueue but thread-safe with blocking operations. (2) Wrap with Collections.synchronizedSortedSet() applied to a TreeSet — not exactly a queue but gives sorted concurrent access. (3) Use an explicit ReentrantLock around PriorityQueue operations in your own class. PriorityBlockingQueue is the recommended approach.
Q68. Explain the producer-consumer pattern using BlockingQueue.
A: The producer-consumer pattern separates data production from consumption. A BlockingQueue acts as the buffer. Producers call put() (blocks when full) and consumers call take() (blocks when empty). This eliminates the need for explicit wait/notify synchronization.
BlockingQueue<Integer> queue = new LinkedBlockingQueue<>(10);
// Producer thread
Thread producer = new Thread(() -> {
for (int i = 0; i < 20; i++) {
try {
queue.put(i);
System.out.println("Produced: " + i);
} catch (InterruptedException e) { Thread.currentThread().interrupt(); }
}
});
// Consumer thread
Thread consumer = new Thread(() -> {
while (true) {
try {
int val = queue.take();
System.out.println("Consumed: " + val);
} catch (InterruptedException e) { Thread.currentThread().interrupt(); break; }
}
});
producer.start(); consumer.start();
Q69. What is the difference between put() and offer() in BlockingQueue?
A: put(e) blocks indefinitely if the queue is full, waiting until space becomes available. offer(e) without timeout returns false immediately if full. offer(e, time, unit) waits up to the given timeout and returns false if still full after the timeout. Use put() when the producer must wait; use offer() when you want non-blocking behavior or bounded waiting time.
Q70. What is the difference between take() and poll() in BlockingQueue?
A: take() blocks indefinitely until an element is available. poll() without timeout returns null immediately if empty. poll(time, unit) waits up to the given timeout. Use take() in a persistent consumer loop; use poll(timeout) when you need the consumer to exit or do other work if no element arrives within a time limit.
Comparable vs Comparator Deep-Dive — Interview Questions & Answers
Q71. What is the difference between Comparable and Comparator in Java?
A: Comparable (java.lang.Comparable) is an interface with a single method compareTo(T o), implemented by the class itself to define its natural ordering. It couples the ordering logic to the class. Comparator (java.util.Comparator) is a separate strategy interface with compare(T o1, T o2). It decouples ordering from the class, allowing multiple orderings. Comparator is also a functional interface, so lambdas work. TreeSet and PriorityQueue use Comparable by default or accept a Comparator in their constructors.
Q72. What does compareTo() return and what are the contracts?
A: compareTo(T other) must return: negative integer if this is less than other, zero if equal, positive integer if greater. Contracts: (1) Antisymmetry: sgn(x.compareTo(y)) == -sgn(y.compareTo(x)). (2) Transitivity: if x.compareTo(y) > 0 and y.compareTo(z) > 0 then x.compareTo(z) > 0. (3) Consistency with equals (recommended): x.compareTo(y) == 0 implies x.equals(y). Violation can cause incorrect behavior in sorted collections.
Q73. What happens if compareTo() is inconsistent with equals() in a TreeSet?
A: The TreeSet will treat two objects as equal (and not store both) if compareTo() returns 0, even if equals() says they are different. Since TreeSet uses compareTo() for all comparisons (not equals()), this means objects that compareTo() considers equal will be deduplicated. The SortedSet contract states: "the behavior of a sorted set is well-defined even if its ordering is inconsistent with equals" — but it will behave differently from a HashSet, which uses equals().
Q74. How do you chain Comparators in Java 8+?
A: Use Comparator.thenComparing() to create a composite comparator.
class Employee {
String name;
int dept;
double salary;
Employee(String n, int d, double s) { name=n; dept=d; salary=s; }
}
Comparator<Employee> comp = Comparator
.comparingInt((Employee e) -> e.dept)
.thenComparing(e -> e.name)
.thenComparingDouble(e -> e.salary);
PriorityQueue<Employee> pq = new PriorityQueue<>(comp);
// Sorts first by dept, then by name, then by salary
Q75. What is Comparator.naturalOrder() and Comparator.reverseOrder()?
A: Comparator.naturalOrder() returns a Comparator that imposes natural ordering (same as Comparable's compareTo). It requires elements to implement Comparable. Comparator.reverseOrder() returns a Comparator that imposes the reverse of natural ordering. Both are useful with collections and streams. They are equivalent to (a, b) -> a.compareTo(b) and (a, b) -> b.compareTo(a) respectively.
Q76. How does Comparator.comparing() work with key extractors?
A: Comparator.comparing(keyExtractor) creates a Comparator that compares objects by applying a key-extraction function. The extracted keys must implement Comparable. Specialized versions: comparingInt(), comparingLong(), comparingDouble() avoid boxing overhead. Example: Comparator.comparing(String::length) compares strings by their length.
Q77. How would you implement a frequency-sorted PriorityQueue?
A: Count frequencies using a HashMap, then use a PriorityQueue sorted by frequency.
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
// Min-heap of size k sorted by frequency
PriorityQueue<Integer> pq = new PriorityQueue<>(
Comparator.comparingInt(freq::get)
);
for (int key : freq.keySet()) {
pq.offer(key);
if (pq.size() > k) pq.poll();
}
List<Integer> result = new ArrayList<>();
while (!pq.isEmpty()) result.add(pq.poll());
return result;
}
Q78. What is the null-safe comparator in Java 8?
A: Comparator.nullsFirst(comparator) returns a Comparator that considers null less than non-null. Comparator.nullsLast(comparator) considers null greater than non-null. Example: Comparator.nullsFirst(Comparator.naturalOrder()) sorts null values first. These are useful when sorting collections that may contain null.
Additional Set, Queue, Deque Questions — Interview Q&As
Q79. What is the fail-fast behavior of HashSet's iterator?
A: HashSet's iterator is fail-fast. If the set is structurally modified (elements added or removed) after the iterator is created — except through the iterator's own remove() method — a ConcurrentModificationException is thrown. This is detected via a modCount counter in the underlying HashMap. This is a best-effort behavior, not a guaranteed contract — it should not be relied upon for correctness in concurrent programs.
Q80. How do you safely remove elements from a Set during iteration?
A: Use the iterator's remove() method, or use removeIf() (Java 8+), or collect elements to remove and call removeAll() after iteration.
Set<Integer> set = new HashSet<>(Set.of(1,2,3,4,5,6));
// Option 1: iterator remove
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
if (it.next() % 2 == 0) it.remove();
}
// Option 2: removeIf (cleaner)
set.removeIf(n -> n % 2 == 0);
Q81. What is the difference between Queue and Deque in terms of interface hierarchy?
A: Queue extends Collection. Deque extends Queue. So Deque has all Queue methods plus additional methods for double-ended access. ArrayDeque implements Deque (and thus also Queue). LinkedList implements both List and Deque (and thus also Queue). PriorityQueue implements Queue but not Deque.
Q82. What is the Stack class in Java and why is it discouraged?
A: java.util.Stack extends Vector (which is synchronized) and provides push(), pop(), peek(), empty(), search() methods. It is discouraged because: (1) It extends Vector (legacy synchronized class) which adds synchronization overhead even in single-threaded use. (2) Since it extends Vector, it exposes index-based access which violates the stack abstraction. (3) Deque (ArrayDeque) is recommended instead: faster, no unnecessary synchronization, cleaner API.
Q83. What is the difference between LinkedBlockingDeque and ArrayDeque?
A: LinkedBlockingDeque is a thread-safe, optionally bounded, doubly-linked node-based Deque that supports blocking operations (putFirst/putLast/takeFirst/takeLast). ArrayDeque is a non-thread-safe, resizable circular array Deque with no blocking. Use LinkedBlockingDeque for concurrent producer-consumer scenarios needing both ends of the deque; use ArrayDeque for single-threaded stack/queue operations.
Q84. How does ConcurrentLinkedDeque differ from LinkedBlockingDeque?
A: ConcurrentLinkedDeque is a non-blocking, lock-free thread-safe Deque using CAS operations. It does not support blocking operations. LinkedBlockingDeque supports blocking (putFirst/takeFirst etc.) using a ReentrantLock. Use ConcurrentLinkedDeque for non-blocking concurrent access; use LinkedBlockingDeque when you need producers/consumers to wait.
Q85. What is the relationship between Set and Map in the Java Collections Framework?
A: Every Set implementation in Java is backed by a corresponding Map: HashSet uses HashMap, LinkedHashSet uses LinkedHashMap, TreeSet uses TreeMap. The Set elements are stored as Map keys with a dummy PRESENT value. This design reuses the Map's key-uniqueness guarantee. EnumSet is the exception — it uses a bit-vector without a backing Map.
Q86. What is the ConcurrentSkipListSet?
A: ConcurrentSkipListSet is a thread-safe, sorted NavigableSet backed by a ConcurrentSkipListMap (which uses a skip list data structure). It provides O(log n) add/remove/contains. Unlike TreeSet (which requires external synchronization), ConcurrentSkipListSet is safe for concurrent access without locking. It is the concurrent alternative to TreeSet when sorted, concurrent access is needed.
Q87. What is a skip list and why is it used in ConcurrentSkipListSet?
A: A skip list is a probabilistic data structure with multiple linked list levels. The bottom level has all elements; upper levels are express lanes with fewer elements. Search, insert, delete are O(log n) on average. Skip lists are amenable to lock-free concurrent algorithms using CAS, which is why they are used in ConcurrentSkipListMap/Set rather than Red-Black trees (which are harder to make lock-free).
Q88. When should you choose HashSet vs TreeSet vs LinkedHashSet?
A: Choose HashSet when you need uniqueness and O(1) operations and don't care about iteration order. Choose TreeSet when you need uniqueness and sorted iteration, or need range operations (floor/ceiling/subSet), at the cost of O(log n) per operation. Choose LinkedHashSet when you need uniqueness, insertion-order iteration, and O(1) operations — essentially a deduplication list. For enum types, always use EnumSet — it is the most performant option.
Q89. What are the navigation methods available on NavigableSet?
A: NavigableSet extends SortedSet and adds: lower(e) — greatest element < e. floor(e) — greatest element <= e. ceiling(e) — least element >= e. higher(e) — least element > e. pollFirst() — removes and returns minimum. pollLast() — removes and returns maximum. descendingSet() — reverse-order view. descendingIterator() — reverse iterator. subSet(from, fromInclusive, to, toInclusive) — flexible range view.
Q90. What is the difference between SortedSet.first() and NavigableSet.pollFirst()?
A: SortedSet.first() (or TreeSet.first()) returns the minimum element without removing it. NavigableSet.pollFirst() removes and returns the minimum element (returns null if empty). Similarly, SortedSet.last() reads the max while pollLast() removes and returns it.
Q91. How does Java's PriorityQueue handle elements with equal priority?
A: PriorityQueue does not guarantee any particular ordering among elements with equal priority. When multiple elements compare as equal (compareTo returns 0 or Comparator returns 0), their relative order in the heap is unspecified. If you need stable ordering among equal-priority elements (FIFO within same priority), you must add a secondary tiebreaker in your Comparator, such as an insertion sequence number.
// Stable PriorityQueue: FIFO within same priority
AtomicLong seq = new AtomicLong();
PriorityQueue<long[]> stablePQ = new PriorityQueue<>(
Comparator.comparingLong((long[] a) -> a[0]) // priority
.thenComparingLong(a -> a[1]) // insertion order
);
// a[0] = priority, a[1] = sequence number
stablePQ.offer(new long[]{2, seq.getAndIncrement()});
stablePQ.offer(new long[]{2, seq.getAndIncrement()});
stablePQ.offer(new long[]{1, seq.getAndIncrement()});
// Polls: priority=1 first, then priority=2 in FIFO order
Q92. How is Deque used in the "Design a Browser History" problem?
A: Use two stacks (back-stack and forward-stack): visit clears the forward-stack and pushes to back-stack. back(steps) pops from back-stack to forward-stack. forward(steps) pops from forward-stack to back-stack. With ArrayDeque as the stack implementation, all operations are O(1) amortized.
Q93. Describe a use case where DelayQueue is appropriate.
A: A session expiry system: when a user session is created, wrap it in a Delayed object with an expiry time and put it in a DelayQueue. A background thread loops calling take() (blocks until the next session expires), then marks that session as expired. No polling or timers needed — the queue handles the timing. Other use cases: retry queues with exponential backoff, scheduling future events, rate limiting.
Q94. What is the isEmpty() vs size()==0 concern with ConcurrentLinkedQueue?
A: In ConcurrentLinkedQueue (and some other concurrent collections), size() is O(n) — it traverses the linked list to count elements. Using size()==0 in a loop is therefore expensive. isEmpty() is O(1) and should always be preferred for emptiness checks in concurrent queues. This is a documented gotcha in the Java API.
Q95. How do you implement a task scheduler using DelayQueue?
A: Implement Delayed for your task, specifying the delay. Enqueue tasks into the DelayQueue. A scheduler thread calls take() — it blocks until the soonest task is ready, then executes it. Java's own ScheduledThreadPoolExecutor uses a similar internal DelayedWorkQueue (a custom heap-based delay queue) for scheduling.
class ScheduledTask implements Delayed {
private final long triggerTime;
private final Runnable task;
ScheduledTask(long delayMs, Runnable task) {
this.triggerTime = System.currentTimeMillis() + delayMs;
this.task = task;
}
public long getDelay(TimeUnit unit) {
return unit.convert(triggerTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
public int compareTo(Delayed other) {
return Long.compare(this.triggerTime,
((ScheduledTask) other).triggerTime);
}
public void run() { task.run(); }
}
DelayQueue<ScheduledTask> scheduler = new DelayQueue<>();
scheduler.put(new ScheduledTask(5000, () -> System.out.println("After 5s")));
scheduler.put(new ScheduledTask(2000, () -> System.out.println("After 2s")));
// Scheduler thread:
// while(true) { ScheduledTask t = scheduler.take(); t.run(); }
Q96. What is the drainTo() method in BlockingQueue?
A: drainTo(Collection c) removes all available elements from the BlockingQueue and adds them to the given collection. It is atomic for each element transfer and is more efficient than repeatedly calling poll() in a loop. drainTo(c, maxElements) drains at most the specified number of elements. Useful for batch processing: drain a bounded number of tasks from a work queue and process them together.
Q97. How does SynchronousQueue support the cached thread pool?
A: Executors.newCachedThreadPool() uses a SynchronousQueue as its work queue. When a task is submitted, it attempts offer() on the SynchronousQueue. If a thread is waiting (take()), the handoff succeeds immediately and the task is executed. If no thread is waiting, offer() fails and a new thread is created. This means tasks are never buffered — they are always handed off directly to a worker thread, and the pool grows as needed. This is why cached thread pools can grow unboundedly under high load.
Q98. How would you implement a bounded blocking stack using Deque and ReentrantLock?
A: Wrap an ArrayDeque with a ReentrantLock and two Conditions (notFull, notEmpty). push() acquires the lock, awaits notFull if full, pushes, then signals notEmpty. pop() acquires the lock, awaits notEmpty if empty, pops, then signals notFull.
class BoundedStack<T> {
private final Deque<T> deque = new ArrayDeque<>();
private final int capacity;
private final ReentrantLock lock = new ReentrantLock();
private final Condition notFull = lock.newCondition();
private final Condition notEmpty = lock.newCondition();
BoundedStack(int cap) { this.capacity = cap; }
public void push(T item) throws InterruptedException {
lock.lock();
try {
while (deque.size() == capacity) notFull.await();
deque.push(item);
notEmpty.signal();
} finally { lock.unlock(); }
}
public T pop() throws InterruptedException {
lock.lock();
try {
while (deque.isEmpty()) notEmpty.await();
T item = deque.pop();
notFull.signal();
return item;
} finally { lock.unlock(); }
}
}
Q99. How does Java's LinkedList implement both List and Deque?
A: LinkedList is a doubly-linked list. As a List, it provides index-based access (get(i) is O(n)). As a Deque, it provides O(1) add/remove at both ends via head and tail node references. The same node structure serves both purposes. However, because LinkedList sacrifices random-access performance to support both interfaces, it is generally suboptimal for both uses: ArrayList is better as a List, and ArrayDeque is better as a Deque.
Q100. What is the overall design principle behind Java's Queue interface method pairs?
A: The Queue interface provides two method variants for each logical operation to support different error-handling strategies: exception-throwing methods (add/remove/element) for cases where failure signals a programming error or unexpected state, and null/false-returning methods (offer/poll/peek) for cases where failure is a normal part of flow control. BlockingQueue adds two more variants (blocking and timed blocking). This layered API design allows the same Queue interface to be used across unbounded, bounded, blocking, and non-blocking contexts with consistent semantics.
Q101. What is the time complexity of contains() in PriorityQueue vs TreeSet?
A: PriorityQueue.contains() is O(n) — it performs a linear scan of the internal array because the heap structure does not support efficient arbitrary-element lookup. TreeSet.contains() is O(log n) — it navigates the Red-Black tree using comparisons. If frequent contains() checks on arbitrary elements are needed alongside priority ordering, consider using a HashMap alongside a PriorityQueue (mapping element to its position for O(1) lookup, though updates become complex).
Q102. Explain how to implement an LRU cache using LinkedHashSet (or LinkedHashMap).
A: LinkedHashMap with access-order mode (third constructor argument = true) automatically moves accessed entries to the tail. Override removeEldestEntry() to evict the head (oldest accessed) when capacity is exceeded. LinkedHashSet alone cannot do this since it doesn't track access order. The canonical LRU cache uses LinkedHashMap directly.
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxSize;
LRUCache(int maxSize) {
super(maxSize, 0.75f, true); // accessOrder = true
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > maxSize;
}
}
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one"); cache.put(2, "two"); cache.put(3, "three");
cache.get(1); // access 1, now tail
cache.put(4, "four"); // evicts 2 (least recently used)
Q103. When does PriorityQueue NOT guarantee correct ordering?
A: PriorityQueue ordering is violated in these cases: (1) You mutate an element after insertion (changing the field used for comparison). PriorityQueue does not detect this and the heap property becomes invalid. (2) Your Comparator or compareTo violates its contract (e.g., not transitive or not antisymmetric). (3) You access elements via iterator or toArray() — these do not return elements in priority order.
Q104. How does offer() differ from add() in a PriorityQueue?
A: For PriorityQueue specifically, there is no functional difference — PriorityQueue is unbounded, so neither offer() nor add() will ever fail due to capacity. Both throw NullPointerException if the element is null and ClassCastException if the element is not comparable. The semantic difference (add throws on failure, offer returns false) only matters for bounded queues like ArrayBlockingQueue.
Q105. How can you implement a two-stack queue (using two stacks to simulate a queue)?
A: Maintain two ArrayDeques used as stacks: inbox and outbox. enqueue pushes to inbox. dequeue: if outbox is empty, pour all elements from inbox to outbox (reversing the order), then pop from outbox. Amortized O(1) per dequeue operation.
class QueueWithTwoStacks<T> {
Deque<T> inbox = new ArrayDeque<>();
Deque<T> outbox = new ArrayDeque<>();
public void enqueue(T item) { inbox.push(item); }
public T dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) outbox.push(inbox.pop());
}
if (outbox.isEmpty()) throw new NoSuchElementException();
return outbox.pop();
}
public T peek() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) outbox.push(inbox.pop());
}
return outbox.peek();
}
}
Post a Comment
Add