// 1.
Detect and Remove Loop in Linked List
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
next = null;
class LoopDetection {
public ListNode detectAndRemoveLoop(ListNode head) {
if (head == null || head.next == null) return head;
// Detect loop using Floyd's algorithm
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
// If no loop exists
if (fast == null || fast.next == null) return head;
// Find loop starting point
slow = head;
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
// Remove loop
fast.next = null;
return head;
// Test
public static void main(String[] args) {
LoopDetection solution = new LoopDetection();
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = head.next; // Creating loop
head = solution.detectAndRemoveLoop(head);
// Now list should be: 1->2->3->4->null
// 2. Segregate Even and Odd nodes in Linked List
class EvenOddList {
public ListNode segregateEvenOdd(ListNode head) {
if (head == null || head.next == null) return head;
ListNode evenHead = null, evenTail = null;
ListNode oddHead = null, oddTail = null;
ListNode curr = head;
while (curr != null) {
if (curr.val % 2 == 0) {
if (evenHead == null) {
evenHead = evenTail = curr;
} else {
evenTail.next = curr;
evenTail = curr;
} else {
if (oddHead == null) {
oddHead = oddTail = curr;
} else {
oddTail.next = curr;
oddTail = curr;
curr = curr.next;
}
if (evenHead == null) return oddHead;
if (oddHead == null) return evenHead;
evenTail.next = oddHead;
oddTail.next = null;
return evenHead;
// 3. Stock Span Problem with Follow-up
class StockSpan {
// Basic solution
public int[] calculateSpan(int[] prices) {
int n = prices.length;
int[] spans = new int[n];
Stack<Integer> stack = new Stack<>();
spans[0] = 1;
stack.push(0);
for (int i = 1; i < n; i++) {
while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
stack.pop();
spans[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
stack.push(i);
}
return spans;
// Follow-up: Calculate span with streaming data
class StockSpanner {
Stack<int[]> stack; // [price, span]
public StockSpanner() {
stack = new Stack<>();
public int next(int price) {
int span = 1;
while (!stack.isEmpty() && stack.peek()[0] <= price) {
span += stack.pop()[1];
stack.push(new int[]{price, span});
return span;
// 4. The Celebrity Problem with O(n) time and O(1) space
class Celebrity {
boolean knows(int a, int b) {
// This would be provided by the system
return true;
public int findCelebrity(int n) {
int candidate = 0;
// Find candidate
for (int i = 1; i < n; i++) {
if (knows(candidate, i)) {
candidate = i;
// Verify candidate
for (int i = 0; i < n; i++) {
if (i != candidate) {
if (knows(candidate, i) || !knows(i, candidate)) {
return -1;
return candidate;
}
// 5. Maximum Sliding Window with Follow-up
class MaxSlidingWindow {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) return new int[0];
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> deque = new LinkedList<>();
for (int i = 0; i < n; i++) {
// Remove elements outside window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
// Remove smaller elements
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;
// Follow-up: Handle streaming data
class SlidingWindowMaximum {
private Deque<Integer> deque;
private Queue<Integer> window;
private int k;
public SlidingWindowMaximum(int k) {
this.k = k;
this.deque = new LinkedList<>();
this.window = new LinkedList<>();
public int add(int num) {
// Add new element
window.offer(num);
// Remove smaller elements
while (!deque.isEmpty() && deque.peekLast() < num) {
deque.pollLast();
deque.offerLast(num);
// Remove element if window exceeds size k
if (window.size() > k) {
int removed = window.poll();
if (removed == deque.peekFirst()) {
deque.pollFirst();
return deque.peekFirst();
// 6. Stack Permutations Checker
class StackPermutation {
public boolean checkPermutation(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>();
int j = 0;
for (int num : pushed) {
stack.push(num);
while (!stack.isEmpty() && j < popped.length && stack.peek() == popped[j]) {
stack.pop();
j++;
}
return j == popped.length;
[Previous content remains the same...]
## Additional Topic-Specific Questions
### Loop Detection in Linked List
51. What happens to Floyd's cycle detection algorithm if the loop starts at the first node?
a) It fails to detect the loop
b) It works normally but takes more iterations
c) It detects the loop in the first iteration
d) It causes an infinite loop
Answer: c
52. In a linked list with a loop, if the loop length is L and distance to loop start is K, when will the
pointers meet?
a) After exactly K steps
b) After exactly L steps
c) After K+L steps
d) After K+nL steps (where n is some positive integer)
Answer: d
53. What is the minimum number of nodes required to form a loop in a linked list?
a) 1
b) 2
c) 3
d) 4
Answer: b
### Bitonic DLL
54. In a bitonic doubly linked list of length n, where can the peak element be located?
a) Only at n/2
b) Only at first or last position
c) At any position from 2 to n-1
d) At any position from 1 to n
Answer: c
55. What is the minimum number of comparisons needed to find the peak element in a bitonic
DLL?
a) O(1)
b) O(log n)
c) O(n)
d) O(n/2)
Answer: c
### Even/Odd Node Segregation
56. When segregating even and odd nodes, what should happen to nodes with value 0?
a) Always treat as even
b) Always treat as odd
c) Can be treated as either
d) Should be removed
Answer: a
57. In a linked list with all odd values, after segregation:
a) The list remains unchanged
b) The list gets reversed
c) The list becomes empty
d) None of the above
Answer: a
### Merge Sort for DLL
58. What is the advantage of using merge sort specifically for a doubly linked list?
a) Lower space complexity
b) Easier backtracking during merging
c) Faster sorting time
d) Simpler implementation
Answer: b
59. During merge sort of DLL, when finding the middle node:
a) We must count total nodes first
b) We can use fast and slow pointers
c) We must store all nodes in array
d) We need extra space proportional to list length
Answer: b
### Minimum Stack
60. If we implement minimum stack using two stacks, what happens when we pop an element?
a) Both stacks must pop
b) Only main stack pops
c) Only min stack pops
d) Either one or both stacks pop depending on the value
Answer: d
61. In a minimum stack, if we push the same minimum value multiple times:
a) We must store it in min stack every time
b) We store it only once with a counter
c) We store it only the first time
d) We never store duplicate values
Answer: a
### Celebrity Problem
62. In a group of n people, what is the maximum number of possible celebrities?
a) n
b) n/2
c) 1
d) n-1
Answer: c
63. In the celebrity problem, if person A knows person B:
a) A cannot be celebrity
b) B must be celebrity
c) Neither can be celebrity
d) Either could be celebrity
Answer: a
### Iterative Tower of Hanoi
64. In iterative Tower of Hanoi, why do we use stacks?
a) To maintain disk order
b) To reduce time complexity
c) To save space
d) All of the above
Answer: a
65. What is the pattern of disk movements in iterative solution?
a) Random
b) Clockwise only
c) Alternating between three possible moves
d) Counter-clockwise only
Answer: c
### Stock Span Problem
66. The stock span on any day is:
a) Number of consecutive days before current day with lower price
b) Number of consecutive days after current day with higher price
c) Total number of days with lower price
d) Average of prices for last n days
Answer: a
67. Why is stack preferred for stock span calculation?
a) Maintains sorted order
b) Provides O(1) access to previous greater element
c) Reduces space complexity
d) Allows duplicate elements
Answer: b
### Priority Queue using DLL
68. When implementing priority queue using DLL, insertion at beginning is done when:
a) New element has highest priority
b) New element has lowest priority
c) Queue is empty
d) Both a and c
Answer: d
69. In a priority queue using DLL, what is the best case time complexity for insertion?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
Answer: a
### Maximum Sliding Window
70. In the maximum sliding window problem, what happens when window size equals array
length?
a) Returns original array
b) Returns maximum element
c) Returns array with single element
d) Returns empty array
Answer: c
