Chapter•270 Minutes

Items per page

Java Progressive DSA Master Bank (25 Core Algorithmic Questions)

25 essential Java Data Structures & Algorithms interview questions complete with step-by-step logic, code implementations, asymptotic complexities, and interactive quizzes.

Q1: How do you count the number of set bits (1s) in an integer using Brian Kernighan's Algorithm?

Brian Kernighan's Algorithm repeatedly clears the lowest set bit of an integer n using the bitwise operation n = n & (n - 1). Each iteration flips the rightmost set bit to 0, running in $O(k)$ time where $k$ is the number of set bits.

Brian Kernighan's Bit Counting

public class BitCount {
    public static int countSetBits(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // Clears rightmost set bit
            count++;
        }
        return count;
    }
}

💡 Flips the lowest set bit in each iteration until the number becomes zero.

Key Takeaways

n & (n - 1) clears the rightmost set bit in $O(1)$ time.
Total iterations equal the count of set bits rather than total bits ($32$ or $64$).

Knowledge Check

What is the result of applying n & (n - 1) to n = 12 (binary 1100)?

Q2: How do you check if an integer is a Power of Two in O(1) time?

A positive integer is a power of two if it has exactly one set bit in its binary representation. Evaluating (n > 0) && ((n & (n - 1)) == 0) checks this property in constant time.

Power of Two Check

public class PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

💡 Returns true strictly for positive integers containing a single 1 bit.

Key Takeaways

Powers of 2 have exactly one bit set to 1 in binary.
(n & (n - 1)) == 0 clears that single set bit, resulting in 0.

Knowledge Check

Why is the condition n > 0 mandatory in the expression n > 0 && (n & (n - 1)) == 0?

Q3: Given an array where every element appears twice except one, how do you find the single number in O(n) time and O(1) space?

Use the properties of the bitwise XOR operator ($oplus$):

$x oplus x = 0$ (Self-inverse)
$x oplus 0 = x$ (Identity)
$x oplus y = y oplus x$ (Commutative) XORing all elements across the array cancels out all paired numbers, leaving the single unique number.

Single Number XOR Solution

public class SingleNumber {
    public static int findSingle(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

💡 Accumulates XOR results across the array to isolate the un-paired value.

Key Takeaways

XORing paired duplicate values reduces them to 0.
Executes in $O(n)$ time with $O(1)$ auxiliary space.

Knowledge Check

What is the result of evaluating 5 ^ 3 ^ 5?

Q4: How do you rotate an N x N 2D matrix 90 degrees clockwise in-place?

Rotating a matrix 90 degrees clockwise in-place involves two steps:

Transpose the matrix: Swap matrix[i][j] with matrix[j][i] for all $i < j$.
Reverse each row: Swap elements from outer columns inward (matrix[i][left] with matrix[i][right]).

Matrix 90 Degree Rotation

public class RotateMatrix {
    public static void rotate(int[][] matrix) {
        int n = matrix.length;
        // Step 1: Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Step 2: Reverse rows
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++; right--;
            }
        }
    }
}

💡 Transposes the grid matrix across its main diagonal and flips rows horizontally.

Key Takeaways

Step 1: Transpose matrix along the main diagonal.
Step 2: Reverse elements horizontally in each row.

Knowledge Check

How would you rotate an N x N matrix 90 degrees COUNTER-clockwise in-place?

Q5: How do you traverse an M x N 2D matrix in Spiral Order?

Maintain four boundary boundaries: top, bottom, left, and right. Traverse right along top, down along right, left along bottom (if top <= bottom), and up along left (if left <= right), shrinking boundaries inward after each direction traversal.

Spiral Matrix Traversal

import java.util.*;

public class SpiralMatrix {
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix == null || matrix.length == 0) return result;
        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;
        while (top <= bottom && left <= right) {
            for (int col = left; col <= right; col++) result.add(matrix[top][col]);
            top++;
            for (int row = top; row <= bottom; row++) result.add(matrix[row][right]);
            right--;
            if (top <= bottom) {
                for (int col = right; col >= left; col--) result.add(matrix[bottom][col]);
                bottom--;
            }
            if (left <= right) {
                for (int row = bottom; row >= top; row--) result.add(matrix[row][left]);
                left++;
            }
        }
        return result;
    }
}

💡 Scans grid perimeters clockwise while shrinking boundary limits.

Key Takeaways

Track four dynamic boundary boundaries.
Shrink boundaries inward and verify non-overlapping conditions before scanning reverse directions.

Knowledge Check

Why are the checks top <= bottom and left <= right required inside the spiral loop before processing bottom and left sweeps?

Q6: How do you implement a Queue using two Stacks (and analyze amortized time complexity)?

Maintain two stacks: inputStack and outputStack.

enqueue(x): Push x onto inputStack ($O(1)$).
dequeue(): If outputStack is empty, pop all elements from inputStack and push them onto outputStack (reversing their order). Pop top of outputStack ($O(1)$ amortized).

Queue Using Stacks Implementation

import java.util.ArrayDeque;
import java.util.Deque;

public class MyQueue {
    private final Deque<Integer> input = new ArrayDeque<>();
    private final Deque<Integer> output = new ArrayDeque<>();

    public void push(int x) {
        input.push(x);
    }
    public int pop() {
        peek();
        return output.pop();
    }
    public int peek() {
        if (output.isEmpty()) {
            while (!input.isEmpty()) {
                output.push(input.pop());
            }
        }
        return output.peek();
    }
    public boolean empty() {
        return input.isEmpty() && output.isEmpty();
    }
}

💡 Transfers items from input to output stack on demand to establish FIFO queue order.

Key Takeaways

inputStack accepts fresh incoming items.
outputStack provides FIFO ordering with amortized $O(1)$ operations.

Knowledge Check

What is the amortized time complexity of the pop() method in a queue built using two stacks?

Q7: How do you design a Min Stack that retrieves the minimum element in O(1) time?

Maintain an auxiliary stack (minStack) alongside the primary stack. When pushing value x, push Math.min(x, minStack.peek()) onto minStack. When popping from the primary stack, pop from minStack simultaneously.

Min Stack Implementation

import java.util.ArrayDeque;
import java.util.Deque;

public class MinStack {
    private final Deque<Integer> stack = new ArrayDeque<>();
    private final Deque<Integer> minStack = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        int currentMin = minStack.isEmpty() ? val : Math.min(val, minStack.peek());
        minStack.push(currentMin);
    }
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return minStack.peek();
    }
}

💡 Keeps stack min state in sync across every push and pop operation.

Key Takeaways

Auxiliary minStack tracks the current minimum value at every stack depth.
All operations (push, pop, top, getMin) run in $O(1)$ time.

Knowledge Check

What is the auxiliary space complexity of the Min Stack implementation?

Q8: How do you search for a target value in a Rotated Sorted Array in O(log n) time?

Use Modified Binary Search. In a rotated sorted array, at least one half (left to mid OR mid to right) is guaranteed to be strictly sorted. Determine which half is sorted, check if target lies within its bounds, and adjust binary search boundaries left / right accordingly.

Rotated Sorted Array Search

public class RotatedSearch {
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            if (nums[left] <= nums[mid]) { // Left half sorted
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else { // Right half sorted
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return -1;
    }
}

💡 Determines the sorted sub-array half to locate target boundaries in logarithmic time.

Key Takeaways

Identify the sorted half in each binary search step.
Narrows search range in $O(log n)$ time.

Knowledge Check

How do you calculate mid safely in Java binary search to prevent integer overflow?

Q9: How do you find the K Closest Points to the Origin (0,0)?

Calculate distance squared $x^2 + y^2$. Use a Max-Heap (PriorityQueue) of size $k$ ordered by Euclidean distance descending. Push points into the heap; if heap size exceeds $k$, pop the maximum distance point. Returns $k$ closest points in $O(n log k)$ time.

K Closest Points Max-Heap Solution

import java.util.PriorityQueue;

public class KClosestPoints {
    public static int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare((b[0]*b[0] + b[1]*b[1]), (a[0]*a[0] + a[1]*a[1]))
        );
        for (int[] p : points) {
            maxHeap.offer(p);
            if (maxHeap.size() > k) {
                maxHeap.poll();
            }
        }
        int[][] result = new int[k][2];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }
}

💡 Maintains $k$ smallest Euclidean distance points inside a bounded Max-Heap.

Key Takeaways

Avoid Math.sqrt() by comparing squared distances ($x^2 + y^2$).
Use size-bounded Max-Heap ($O(n log k)$ runtime).

Knowledge Check

Why is comparing (x1^2 + y1^2) directly preferred over using Math.sqrt(x1^2 + y1^2)?

Q10: How do you validate whether a Binary Tree is a valid Binary Search Tree (BST)?

Pass dynamic valid range constraints (min and max pointers) recursively down the tree. For a node to be valid, its value must satisfy min < node.val < max. When recurring left, update max = node.val. When recurring right, update min = node.val.

Validate BST Solution

public class ValidateBST {
    public static boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }
    private static boolean validate(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;
        if ((low != null && node.val <= low) || (high != null && node.val >= high)) {
            return false;
        }
        return validate(node.left, low, node.val) && validate(node.right, node.val, high);
    }
}

💡 Validates that node values fall within strict minimum and maximum subtree constraints.

Key Takeaways

Use Long pointers or object wrappers for min/max bounds to handle Integer.MIN_VALUE edge cases.
Validates that every left descendant is strictly smaller and right descendant is strictly larger.

Knowledge Check

Why is simply checking node.left.val < node.val && node.right.val > node.val for each node insufficient to validate a BST?

Q1: How do you count the number of set bits (1s) in an integer using Brian Kernighan's Algorithm?

Q2: How do you check if an integer is a Power of Two in O(1) time?

Q3: Given an array where every element appears twice except one, how do you find the single number in O(n) time and O(1) space?

Q4: How do you rotate an N x N 2D matrix 90 degrees clockwise in-place?

Q5: How do you traverse an M x N 2D matrix in Spiral Order?

Q6: How do you implement a Queue using two Stacks (and analyze amortized time complexity)?

Q7: How do you design a Min Stack that retrieves the minimum element in O(1) time?

Q8: How do you search for a target value in a Rotated Sorted Array in O(log n) time?

Q9: How do you find the K Closest Points to the Origin (0,0)?

Q10: How do you validate whether a Binary Tree is a valid Binary Search Tree (BST)?

STAY UPDATED WITH BYTES!