Problem 1: Kth Largest Element in an Unsorted Array

Goal
Locate the k-th largest value in a integer array that is not pre-sorted.

Example

Input:  [3, 2, 1, 5, 6, 4], k = 2  
Output: 5

Optimized Java Implementation

import java.util.Random;

public final class KthLargestFinder {
    private static final Random RNG = new Random();

    public int kthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1, target = nums.length - k;
        while (left <= right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == target) {
                return nums[pivotIndex];
            } else if (pivotIndex < target) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
        throw new IllegalArgumentException("k is out of bounds");
    }

    private int partition(int[] arr, int low, int high) {
        int pivotIndex = low + RNG.nextInt(high - low + 1);
        int pivotValue = arr[pivotIndex];
        swap(arr, pivotIndex, high);
        int store = low;
        for (int i = low; i < high; i++) {
            if (arr[i] < pivotValue) {
                swap(arr, store++, i);
            }
        }
        swap(arr, store, high);
        return store;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] data = {3, 2, 1, 5, 6, 4};
        System.out.println(new KthLargestFinder().kthLargest(data, 2)); // 5
    }
}

Problem 2: Valid Sudoku Board

Goal
Verify that a 9×9 Sudoku grid satisfies row, column, and 3×3 sub-box constraints without duplicates.

Example

Input:
[ ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  ... ]
Output: true

Bit-Masked Java Implementation

public final class SudokuValidator {
    public boolean isValid(char[][] board) {
        int[] rowMask = new int[9];
        int[] colMask = new int[9];
        int[] boxMask = new int[9];

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char ch = board[r][c];
                if (ch == '.') continue;
                int bit = 1 << (ch - '1');
                int box = (r / 3) * 3 + c / 3;
                if ((rowMask[r] & bit) != 0 ||
                    (colMask[c] & bit) != 0 ||
                    (boxMask[box] & bit) != 0) {
                    return false;
                }
                rowMask[r] |= bit;
                colMask[c] |= bit;
                boxMask[box] |= bit;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'5','3','.','.','7','.','.','.','.'},
            {'6','.','.','1','9','5','.','.','.'},
            {'.','9','8','.','.','.','.','6','.'},
            {'8','.','.','.','6','.','.','.','3'},
            {'4','.','.','8','.','3','.','.','1'},
            {'7','.','.','.','2','.','.','.','6'},
            {'.','6','.','.','.','.','2','8','.'},
            {'.','.','.','4','1','9','.','.','5'},
            {'.','.','.','.','8','.','.','7','9'}
        };
        System.out.println(new SudokuValidator().isValid(grid)); // true
    }
}

Problem 3: Merge Two Sorted Arays In-Place

Goal
Combine two ascending arrays into the first array, assuming it has enough trailing buffer.

Example

Input:
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 3], n = 3
Output: [1, 2, 2, 3, 3, 5]

Two-Pointer Java Implementation

public final class ArrayMerger {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 0, 0, 0};
        int[] b = {2, 5, 3};
        new ArrayMerger().merge(a, 3, b, 3);
        System.out.println(java.util.Arrays.toString(a)); // [1, 2, 2, 3, 3, 5]
    }
}