1. Fundamentals of Data Structures and Algorithms

Efficient software engineering relies heavily on the optimized use of memory and processing power. Data structures define how we organize and store data, while algorithms provide the step-by-step procedures to manipulate that data. A solid understanding of these concepts allows developers to write code that scales gracefully with increasing data volume and complexity.

2. Linear and Non-Linear Structures

Data structures are generally categorized into linear and non-linear types. Linear structures, such as arrays, linked lists, stacks, and queues, store data in a sequential manner. Non-linear structures, like trees and graphs, allow for more complex relationships where data elements are not arranged in a single sequence.

3. Sparse Arrays

In scenarios involving large matrices where the majority of values are zero (e.g., game boards like Go or Chess), a standard 2D array wastes significant space. A sparse array compresses this data by storing only non-zero values along with their row and column indices.

public class SparseArrayDemo {
    public static void main(String[] args) {
        int[][] originalMatrix = new int[11][11];
        originalMatrix[1][2] = 1;
        originalMatrix[2][3] = 2;
        // Convert to sparse array
        int[][] sparseArr = convertToSparse(originalMatrix);
        // Restore from sparse array
        int[][] restoredMatrix = restoreFromSparse(sparseArr);
    }

    public static int[][] convertToSparse(int[][] matrix) {
        int sum = 0;
        for (int[] row : matrix) {
            for (int data : row) {
                if (data != 0) sum++;
            }
        }
        int[][] sparse = new int[sum + 1][3];
        sparse[0] = new int[]{matrix.length, matrix[0].length, sum};
        int count = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] != 0) {
                    count++;
                    sparse[count][0] = i;
                    sparse[count][1] = j;
                    sparse[count][2] = matrix[i][j];
                }
            }
        }
        return sparse;
    }

    public static int[][] restoreFromSparse(int[][] sparse) {
        int[][] matrix = new int[sparse[0][0]][sparse[0][1]];
        for (int i = 1; i < sparse.length; i++) {
            matrix[sparse[i][0]][sparse[i][1]] = sparse[i][2];
        }
        return matrix;
    }
}

4. Circular Queues

A standard array-based queue suffers from the limitation where elements cannot be reused once the rear pointer reaches the array's capacity. A circular queue (or ring buffer) utilizes modular arithmetic to link the end of the array back to the beginning, allowing for efficient reuse of space.

class CircularQueue {
    private int[] data;
    private int head;
    private int tail;
    private int size;
    private int capacity;

    public CircularQueue(int k) {
        this.capacity = k;
        this.data = new int[k];
        this.head = -1;
        this.tail = -1;
        this.size = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        if (isEmpty()) head = 0;
        tail = (tail + 1) % capacity;
        data[tail] = value;
        size++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        if (head == tail) {
            head = -1;
            tail = -1;
        } else {
            head = (head + 1) % capacity;
        }
        size--;
        return true;
    }

    public int Front() {
        return isEmpty() ? -1 : data[head];
    }

    public int Rear() {
        return isEmpty() ? -1 : data[tail];
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean isFull() {
        return size == capacity;
    }
}

5. Linked Lists

Linked lists consist of nodes where each node contains data and a reference (or pointer) to the next node in the sequence. Unlike arrays, they allow for efficient insertion and deletion operations as memory does not need to be contiguous.

class Node {
    int val;
    Node next;
    Node(int x) { val = x; }
}

class SinglyLinkedList {
    private Node head;

    public void add(int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
    
    // Reversing the linked list
    public void reverse() {
        Node prev = null;
        Node current = head;
        Node next = null;
        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
    }
}

6. Recursion and the 8-Queens Problem

Recursion is a technique where a function calls itself to solve a smaller instance of the problem. It is particularly useful for problems like backtracking, tree traversal, and mathematical sequences.

public class NQueens {
    int max = 8;
    int[] array = new int[max];
    static int count = 0;

    public static void main(String[] args) {
        NQueens queue = new NQueens();
        queue.check(0);
        System.out.println("Total solutions: " + count);
    }

    private void check(int n) {
        if (n == max) {
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            array[n] = i;
            if (judge(n)) {
                check(n + 1);
            }
        }
    }

    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }

    private void print() {
        count++;
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

7. Sorting Algorithms

7.1 Quick Sort

Quick sort is a divide-and-conquer algorithm that selects a 'pivot' element and partitions the array around the pivot, placing smaller elements to the left and larger elements to the right.

public class QuickSort {
    public static void sort(int[] arr, int left, int right) {
        int l = left;
        int r = right;
        int pivot = arr[(left + right) / 2];
        int temp = 0;

        while (l < r) {
            while (arr[l] < pivot) l++;
            while (arr[r] > pivot) r--;
            if (l >= r) break;

            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            if (arr[l] == pivot) l++;
            if (arr[r] == pivot) r--;
        }

        if (l == r) {
            l++;
            r--;
        }
        if (left < r) sort(arr, left, r);
        if (right > l) sort(arr, l, right);
    }
}

7.2 Merge Sort

Merge sort divides the array into halves, recursively sorts them, and then merges the sorted halves back together.

public class MergeSort {
    public static void sort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);
            sort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int t = 0;

        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }

        while (i <= mid) temp[t++] = arr[i++];
        while (j <= right) temp[t++] = arr[j++];

        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }
    }
}

8. Binary Search Trees (BST)

A Binary Search Tree is a node-based binary tree data structure which has the following properties: The left subtree of a node contains only nodes with keys lesser than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key.

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class BinarySearchTree {
    private TreeNode root;

    public void add(int val) {
        root = recursiveAdd(root, val);
    }

    private TreeNode recursiveAdd(TreeNode node, int val) {
        if (node == null) return new TreeNode(val);
        if (val < node.val) {
            node.left = recursiveAdd(node.left, val);
        } else if (val > node.val) {
            node.right = recursiveAdd(node.right, val);
        }
        return node;
    }

    public void inOrderTraversal() {
        inOrder(root);
    }

    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.val + " ");
            inOrder(node.right);
        }
    }
}

9. Hash Tables

A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. It provides average O(1) time complexity for search, insert, and delete operations.

import java.util.LinkedList;

class HashEntry {
    String key;
    String value;
    HashEntry next;

    HashEntry(String key, String value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

public class CustomHashTable {
    private int capacity;
    private LinkedList<HashEntry>[] table;

    public CustomHashTable(int capacity) {
        this.capacity = capacity;
        this.table = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            table[i] = new LinkedList<>();
        }
    }

    private int getIndex(String key) {
        return Math.abs(key.hashCode() % capacity);
    }

    public void put(String key, String value) {
        int index = getIndex(key);
        LinkedList<HashEntry> bucket = table[index];
        for (HashEntry entry : bucket) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }
        bucket.add(new HashEntry(key, value));
    }

    public String get(String key) {
        int index = getIndex(key);
        LinkedList<HashEntry> bucket = table[index];
        for (HashEntry entry : bucket) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }
        return null;
    }
}