Design Patterns: Singleton Instantiation

Eager initialization constructs the instance during class loading. Lazy evaluation defers creation until explicit retrieval, requiring synchronization to prevent race conditions in concurrent environments.

class EagerSingleton {
    private EagerSingleton() {}
    private static final EagerSingleton INSTANCE = new EagerSingleton();
    public static EagerSingleton acquireInstance() { return INSTANCE; }
}

class LazySingleton {
    private LazySingleton() {}
    private static volatile LazySingleton _instance;
    public static synchronized LazySingleton acquireInstance() {
        if (_instance == null) {
            _instance = new LazySingleton();
        }
        return _instance;
    }
}

class DoubleCheckedLazy {
    private DoubleCheckedLazy() {}
    private static volatile DoubleCheckedLazy _ref;
    public static DoubleCheckedLazy getReference() {
        if (_ref == null) {
            synchronized (DoubleCheckedLazy.class) {
                if (_ref == null) {
                    _ref = new DoubleCheckedLazy();
                }
            }
        }
        return _ref;
    }
}

The volatile modifier prevents instruction reordering during object construction, ensuring other threads never observe a partially initialized reference.

Static inner classes defer loading until explicitly accessed, combining lazy behavior with thread safety without explicit locking:

class HolderSingleton {
    private HolderSingleton() {}
    public static HolderSingleton resolve() {
        return InternalHolder._object;
    }
    private static class InternalHolder {
        static final HolderSingleton _object = new HolderSingleton();
    }
}

String and Numeric Transformations

Palindrome verification can leverage bidirectional pointers or string reversal utilities. Integer reversal requires overflow detection before computation.

public boolean verifyPalindrome(String input) {
    int left = 0;
    int right = input.length() - 1;
    while (left < right) {
        if (input.charAt(left++) != input.charAt(right--)) {
            return false;
        }
    }
    return true;
}

public int invertNumericValue(int value) {
    long result = 0;
    while (value != 0) {
        result = result * 10 + value % 10;
        value /= 10;
    }
    if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
        return 0;
    }
    return (int) result;
}

public String reverseWordOrder(String text) {
    if (text == null || text.trim().isEmpty()) return text;
    String[] words = text.split("\\s+");
    StringBuilder builder = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        builder.append(words[i]);
        if (i > 0) builder.append(" ");
    }
    return builder.toString();
}

public String encodeSpaces(String source) {
    if (source == null) return "";
    return source.replace(" ", "%20");
}

public String rotateLeftShift(String sequence, int steps) {
    if (sequence == null || sequence.isEmpty() || steps <= 0) return sequence;
    int shift = steps % sequence.length();
    return sequence.substring(shift) + sequence.substring(0, shift);
}

Concurrency Mechanisms

Synchronized coordination ensures ordered execution across multiple threads. Resource contention requires atomic access controls, while improper lock acquisition ordering triggers deadlock states.

public class SequentialPrinter {
    private static char currentChar = 'A';
    private static int count = 0;
    private static final Object monitor = new Object();

    public void execute() {
        Thread t1 = new Thread(() -> processThread(0));
        Thread t2 = new Thread(() -> processThread(1));
        Thread t3 = new Thread(() -> processThread(2));
        t1.start(); t2.start(); t3.start();
    }

    private void processThread(int id) {
        synchronized (monitor) {
            while (count < 26) {
                if ((count % 3) == id) {
                    System.out.printf("%d: %c%n", id + 1, currentChar++);
                    count++;
                    monitor.notifyAll();
                } else {
                    try { monitor.wait(); } catch (InterruptedException ignored) {}
                }
            }
        }
    }
}

Thread-safe resource distribution using mutual exclusion:

public class TicketManager implements Runnable {
    private int remainingTickets = 100;
    private final Object lock = new Object();

    @Override
    public void run() {
        while (true) {
            synchronized (lock) {
                if (remainingTickets <= 0) break;
                try { Thread.sleep(5); } catch (InterruptedException ignored) {}
                System.out.println(Thread.currentThread().getName() + " sold: " + remainingTickets--);
            }
        }
    }
}

Deadlock scenario demonstration involves cyclic lock dependencies:

public class LockDemo {
    private final Object resourceX = new Object();
    private final Object resourceY = new Object();
    private final boolean prioritizeY;

    public void attemptExecution() {
        if (prioritizeY) {
            synchronized (resourceY) {
                synchronized (resourceX) { /* critical section */ }
            }
        } else {
            synchronized (resourceX) {
                synchronized (resourceY) { /* critical section */ }
            }
        }
    }
}

Sequence Generation and Performance Analysis

Fibonacci sequences follow additive recurrence relations. Iterative approaches elimniate call stack overhead compared to naive recursion.

public long computeIterativeFib(int n) {
    if (n <= 1) return n;
    long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

public long computeRecursiveFib(int n) {
    if (n <= 1) return n;
    return computeRecursiveFib(n - 1) + computeRecursiveFib(n - 2);
}

Recursion incurs significant memory allocation per frame due to parameter passing and return address preservation. While code readability improves with recursive structures, iterative loops deliver superior throughput for large datasets.

Tree Traversals and Metrics

Binary tree operations require depth-first exploartion strategies. Structural modifications and aggregate calculations traverse nodes recursively.

class TreeNode {
    int data;
    TreeNode left, right;
    TreeNode(int val) { this.data = val; }
}

public void traversePreorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.data + " ");
    traversePreorder(root.left);
    traversePreorder(root.right);
}

public void traverseInorder(TreeNode root) {
    if (root == null) return;
    traverseInorder(root.left);
    System.out.print(root.data + " ");
    traverseInorder(root.right);
}

public void traversePostorder(TreeNode root) {
    if (root == null) return;
    traversePostorder(root.left);
    traversePostorder(root.right);
    System.out.print(root.data + " ");
}

public void mirrorTree(TreeNode root) {
    if (root == null) return;
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    mirrorTree(root.left);
    mirrorTree(root.right);
}

public int calculateMaxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(calculateMaxDepth(root.left), calculateMaxDepth(root.right)) + 1;
}

public int locateMaximumValue(TreeNode root) {
    if (root == null) return Integer.MIN_VALUE;
    return Math.max(root.data, Math.max(locateMaximumValue(root.left), locateMaximumValue(root.right)));
}

Linked List Manipulations

Pointer manipulation requires careful reference updates to prevent memory leaks or infinite loops.

class Node {
    int value;
    Node next;
    Node(int v) { value = v; }
}

public void removeDuplicateNode(Node target) {
    if (target == null || target.next == null) return;
    target.value = target.next.value;
    target.next = target.next.next;
}

public Node reverseLinkedList(Node head) {
    Node prev = null, curr = head;
    while (curr != null) {
        Node nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

public boolean detectCycle(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

public boolean checkPalindrome(Node head) {
    Node slow = head, fast = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    Node reversedHalf = reverseLinkedList(slow);
    while (reversedHalf != null) {
        if (head.value != reversedHalf.value) return false;
        head = head.next;
        reversedHalf = reversedHalf.next;
    }
    return true;
}

public Node reverseNodesInGroups(Node head, int k) {
    if (head == null || k == 1) return head;
    Node current = head;
    Node nextGroupStart = null;
    for (int i = 0; i < k; i++) {
        if (current == null) return head;
        current = current.next;
    }
    nextGroupStart = current;
    Node prev = null, curr = head;
    for (int i = 0; i < k; i++) {
        Node nextRef = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextRef;
    }
    head.next = reverseNodesInGroups(nextGroupStart, k);
    return prev;
}

Queue Simulation via Stacks

First-in-first-out behavior can be reconstructed using two last-in-first-out containers.

class DualStackQueue {
    private java.util.Stack<Integer> inputBuffer = new java.util.Stack<>();
    private java.util.Stack<Integer> outputBuffer = new java.util.Stack<>();

    public void enqueue(int element) { inputBuffer.push(element); }

    public int dequeue() {
        if (outputBuffer.isEmpty() && inputBuffer.isEmpty()) throw new IllegalStateException("Queue empty");
        if (outputBuffer.isEmpty()) {
            while (!inputBuffer.isEmpty()) outputBuffer.push(inputBuffer.pop());
        }
        return outputBuffer.pop();
    }
}

Search Strategies

Divide-and-conquer techniques reduce search space logarithmically on sorted collections.

public int binarySearchIterative(int[] dataset, int target) {
    int low = 0, high = dataset.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (dataset[mid] == target) return mid;
        if (dataset[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

public int binarySearchRecursive(int[] dataset, int target) {
    return searchHelper(dataset, target, 0, dataset.length - 1);
}

private int searchHelper(int[] dataset, int target, int start, int end) {
    if (start > end) return -1;
    int mid = start + (end - start) / 2;
    if (dataset[mid] == target) return mid;
    return dataset[mid] > target ? searchHelper(dataset, target, start, mid - 1) : searchHelper(dataset, target, mid + 1, end);
}

Array Modifications

Deduplication and merging strategies optimize memory footprint and traversal efficiency.

public int[] removeDuplicates(int[] source) {
    if (source.length == 0) return source;
    int writeIndex = 1;
    for (int readIndex = 1; readIndex < source.length; readIndex++) {
        if (source[readIndex] != source[readIndex - 1]) {
            source[writeIndex++] = source[readIndex];
        }
    }
    return Arrays.copyOf(source, writeIndex);
}

public void mergeSortedSegments(int[] first, int m, int[] second, int n) {
    int idxA = m - 1, idxB = n - 1, mergedIdx = m + n - 1;
    while (idxA >= 0 && idxB >= 0) {
        first[mergedIdx--] = first[idxA] > second[idxB] ? first[idxA--] : second[idxB--];
    }
    while (idxB >= 0) first[mergedIdx--] = second[idxB--];
}

public int findFirstRepetition(int[] values) {
    Set<Integer> observed = new HashSet<>();
    for (int num : values) {
        if (!observed.add(num)) return num;
    }
    return -1;
}

Sorting Routines

Comparison-based algorithms vary in stability, space complexity, and adaptive performance.

public int[] bubbleSort(int[] array) {
    boolean swapped;
    for (int i = 0; i < array.length - 1; i++) {
        swapped = false;
        for (int j = 0; j < array.length - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return array;
}

public int[] selectionSort(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int minPos = i;
        for (int j = i + 1; j < array.length; j++) {
            if (array[j] < array[minPos]) minPos = j;
        }
        int temp = array[i]; array[i] = array[minPos]; array[minPos] = temp;
    }
    return array;
}

public int[] insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
    return array;
}

public void quickSort(int[] data, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(data, left, right);
        quickSort(data, left, pivotIndex - 1);
        quickSort(data, pivotIndex + 1, right);
    }
}

private int partition(int[] data, int low, int high) {
    int pivot = data[high];
    int boundary = low - 1;
    for (int i = low; i < high; i++) {
        if (data[i] <= pivot) {
            boundary++;
            int temp = data[boundary]; data[boundary] = data[i]; data[i] = temp;
        }
    }
    int temp = data[boundary + 1]; data[boundary + 1] = data[high]; data[high] = temp;
    return boundary + 1;
}

Combinatorial Pathfinding

Staircase navigation problems model recursive decomposition. Unrestricted jump ranges yield exponential progression formulas.

public int calculateJumpVariants(int levels) {
    if (levels <= 2) return levels;
    int[] memo = new int[levels + 1];
    memo[1] = 1; memo[2] = 2;
    for (int i = 3; i <= levels; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    return memo[levels];
}

public int calculateUnrestrictedJumps(int heights) {
    if (heights <= 0) return 0;
    return 1 << (heights - 1);
}

public int climbStepCombinations(int n) {
    if (n == 0) return 0;
    int[] dp = new int[n + 1];
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}