Design and Algos
Data Structure?
At its core, a data structure is a specialized format for organizing and storing data in a computer so that it can be accessed and modified efficiently. Think of it as a container or a blueprint that defines how data is arranged, allowing for various operations (like searching, inserting, deleting, and updating) to be performed effectively. The choice of data structure can significantly impact the performance and efficiency of an algorithm or an entire software system.
Common examples include arrays, linked lists, trees, graphs, and hash tables, each with its strengths and weaknesses depending on the specific problem you're trying to solve.
Time and Space Complexity
When we talk about the efficiency of an algorithm, we primarily consider its time complexity and space complexity. These concepts help us understand how an algorithm scales with the size of its input.
Time Complexity: Measures the amount of time an algorithm takes to run as a function of the input size (n). It doesn't measure the actual execution time in seconds, but rather the number of operations performed. We typically express time complexity using Big O notation (O(n)), which describes the upper bound or worst-case scenario for an algorithm's growth rate.
Common Big O Notations:
O(1): Constant time (e.g., accessing an array element by index).
O(logn): Logarithmic time (e.g., binary search).
O(n): Linear time (e.g., iterating through a list).
O(nlogn): Linearithmic time (e.g., merge sort, quicksort).
O(n2): Quadratic time (e.g., bubble sort, nested loops).
O(2n): Exponential time (e.g., certain recursive algorithms without memoization).
O(n): Factorial time (e.g., brute-force solutions for traveling salesman).
Space Complexity: Measures the amount of memory (space) an algorithm uses as a function of the input size (n). This includes the space used by the input itself and any auxiliary space required by the algorithm during its execution. Like time complexity, it's also expressed using Big O notation.
Calculating complexity involves analyzing the operations an algorithm performs.
Identify the Input Size (n): What defines the "size" of the problem? Is it the number of elements in an array, the number of nodes in a tree, etc.?
Count Operations (Time Complexity):
Basic Operations: Assigning a value, arithmetic operations, comparisons, array access by index are generally considered O(1).
Loops: If a loop runs
ntimes and performs O(1) operations inside, the loop's complexity is O(n). Nested loops multiply complexities (e.g., two nested loops runningntimes each result in O(n2)).Recursion: Analyze the recurrence relation. The Master Theorem can be useful for divide-and-conquer algorithms.
Conditional Statements: Consider the worst-case path.
Count Memory Usage (Space Complexity):
Variables: Basic variables typically consume O(1) space.
Data Structures: The space used by data structures scales with the number of elements stored (e.g., an array of
nelements uses O(n) space).Recursion Stack: Recursive calls consume stack space. If the recursion depth is
n, it can be O(n) space.
public void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) { // Loop runs 'arr.length' times (n times)
System.out.println(arr[i]); // O(1) operation
}
}
n times (where n is arr.length). Inside the loop, System.out.println is an O(1) operation. Therefore, the total time complexity is $O(n) \* O(1) = O(n)$.public int sumArray(int[] arr) {
int sum = 0; // O(1) space for 'sum' variable
for (int num : arr) {
sum += num;
}
return sum;
}
int variable sum regardless of the input array size. Thus, the space complexity is O(1) (constant space).a. Array
Concept: A collection of elements of the same data type stored in contiguous memory locations. Elements are accessed using an index.
Characteristics:
Fixed size (in most languages, once declared).
Direct access to elements using index (O(1)).
Use Cases: Storing a fixed number of items, lookup by index, implementing other data structures.
Time & Space Complexity:
Access/Read: O(1)
Insertion/Deletion (at end): O(1) (if space is available)
Insertion/Deletion (at beginning/middle): O(n) (requires shifting elements)
Space: O(n) (where
nis the size of the array)
class CustomArray {
private int[] data;
private int size; // Current number of elements
public CustomArray(int capacity) {
data = new int[capacity];
size = 0;
}
public void add(int value) {
if (size == data.length) {
// In a real scenario, you'd resize the array (e.g., double its capacity)
System.out.println("Array is full. Cannot add more elements.");
return;
}
data[size++] = value;
}
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
}
return data[index];
}
public void set(int index, int value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
}
data[index] = value;
}
public void removeAt(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
}
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
}
public int getSize() {
return size;
}
public void print() {
System.out.print("Array: [");
for (int i = 0; i < size; i++) {
System.out.print(data[i]);
if (i < size - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
}
b. Linked List
Concept: A linear collection of elements (nodes) where each node points to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations.
Characteristics:
Dynamic size.
Elements are not stored contiguously.
Accessing an element requires traversing from the beginning (O(n)).
Use Cases: Implementing stacks, queues, hash maps (for collision resolution), dynamic memory allocation.
Time & Space Complexity:
Access/Search: O(n)
Insertion/Deletion (at beginning/end - if tail pointer exists): O(1)
Insertion/Deletion (at middle): O(n) (requires traversing to find the position)
Space: O(n) (for nodes)
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CustomLinkedList {
private Node head;
private int size;
public CustomLinkedList() {
this.head = null;
this.size = 0;
}
public void addFirst(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
size++;
}
public void addLast(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
size++;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
size++;
}
public void removeFirst() {
if (head == null) {
System.out.println("List is empty. Cannot remove.");
return;
}
head = head.next;
size--;
}
public void removeLast() {
if (head == null) {
System.out.println("List is empty. Cannot remove.");
return;
}
if (head.next == null) { // Only one element
head = null;
size--;
return;
}
Node current = head;
Node prev = null;
while (current.next != null) {
prev = current;
current = current.next;
}
prev.next = null;
size--;
}
public boolean contains(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
return true;
}
current = current.next;
}
return false;
}
public int getSize() {
return size;
}
public void print() {
Node current = head;
System.out.print("LinkedList: [");
while (current != null) {
System.out.print(current.data);
if (current.next != null) {
System.out.print(" -> ");
}
current = current.next;
}
System.out.println("]");
}
}
c. Stack
Concept: A linear data structure that follows the Last-In, First-Out (LIFO) principle. Think of a stack of plates: the last plate you put on is the first one you take off.
Operations:
push(): Adds an element to the top of the stack.pop(): Removes and returns the element from the top of the stack.peek(): Returns the top element without removing it.isEmpty(): Checks if the stack is empty.
Use Cases: Function call stack, undo/redo functionality, expression evaluation, backtracking algorithms.
Time & Space Complexity:
Push: O(1)
Pop: O(1)
Peek: O(1)
IsEmpty: O(1)
Space: O(n)
class CustomStack {
private int[] stackArray;
private int top; // Index of the top element
private int capacity;
public CustomStack(int capacity) {
this.capacity = capacity;
stackArray = new int[capacity];
top = -1; // Indicates an empty stack
}
public void push(int value) {
if (top == capacity - 1) {
System.out.println("Stack Overflow: Stack is full.");
return;
}
stackArray[++top] = value;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow: Stack is empty.");
return -1; // Or throw an exception
}
return stackArray[top--];
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty.");
return -1; // Or throw an exception
}
return stackArray[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
public void print() {
System.out.print("Stack: [");
for (int i = 0; i <= top; i++) {
System.out.print(stackArray[i]);
if (i < top) {
System.out.print(", ");
}
}
System.out.println("] (Top: " + (isEmpty() ? "None" : stackArray[top]) + ")");
}
}
d. Queue
Concept: A linear data structure that follows the First-In, First-Out (FIFO) principle. Like a line of people waiting: the first person in line is the first one served.
Operations:
enqueue(): Adds an element to the rear of the queue.dequeue(): Removes and returns the element from the front of the queue.peek(): Returns the front element without removing it.isEmpty(): Checks if the queue is empty.
Use Cases: Task scheduling, breadth-first search, printer queues, simulating waiting lines.
Time & Space Complexity:
Enqueue: O(1)
Dequeue: O(1)
Peek: O(1)
IsEmpty: O(1)
Space: O(n)
class CustomQueue {
private int[] queueArray;
private int front;
private int rear;
private int size;
private int capacity;
public CustomQueue(int capacity) {
this.capacity = capacity;
queueArray = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
public void enqueue(int value) {
if (size == capacity) {
System.out.println("Queue Overflow: Queue is full.");
return;
}
rear = (rear + 1) % capacity; // Circular increment
queueArray[rear] = value;
size++;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue Underflow: Queue is empty.");
return -1; // Or throw an exception
}
int data = queueArray[front];
front = (front + 1) % capacity; // Circular increment
size--;
return data;
}
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return -1; // Or throw an exception
}
return queueArray[front];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void print() {
System.out.print("Queue: [");
if (!isEmpty()) {
for (int i = 0; i < size; i++) {
System.out.print(queueArray[(front + i) % capacity]);
if (i < size - 1) {
System.out.print(", ");
}
}
}
System.out.println("] (Front: " + (isEmpty() ? "None" : queueArray[front]) + ")");
}
}
e. HashMap (Hash Table)
Concept: A data structure that stores key-value pairs. It uses a hash function to map keys to array indices (buckets) to provide fast data retrieval. Collisions (when two different keys hash to the same index) are handled using techniques like chaining (linked lists) or open addressing.
Characteristics:
Aims for O(1) average-case time complexity for operations.
No inherent order of elements.
Use Cases: Caching, counting frequencies, implementing dictionaries/associative arrays, symbol tables.
Time & Space Complexity:
Put/Insert (Average): O(1)
Get/Search (Average): O(1)
Remove (Average): O(1)
Put/Get/Remove (Worst-case, due to collisions): O(n) (if all keys hash to the same bucket, it degrades to a linked list traversal)
Space: O(n) (for storing
nkey-value pairs)
// Helper class for key-value pair
class Entry {
Object key;
Object value;
Entry next;
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
this.next = null;
}
}
class CustomHashMap {
private Entry[] table;
private int capacity;
private int size; // Number of key-value pairs
public CustomHashMap(int capacity) {
this.capacity = capacity;
table = new Entry[capacity];
size = 0;
}
private int getBucketIndex(Object key) {
// Simple hash function using Java's hashCode()
return Math.abs(key.hashCode() % capacity);
}
public void put(Object key, Object value) {
int bucketIndex = getBucketIndex(key);
Entry newEntry = new Entry(key, value);
if (table[bucketIndex] == null) {
table[bucketIndex] = newEntry;
size++;
} else {
Entry current = table[bucketIndex];
Entry prev = null;
while (current != null) {
if (current.key.equals(key)) {
current.value = value; // Update value if key exists
return;
}
prev = current;
current = current.next;
}
// Key not found, add to the end of the chain
prev.next = newEntry;
size++;
}
}
public Object get(Object key) {
int bucketIndex = getBucketIndex(key);
Entry current = table[bucketIndex];
while (current != null) {
if (current.key.equals(key)) {
return current.value;
}
current = current.next;
}
return null; // Key not found
}
public void remove(Object key) {
int bucketIndex = getBucketIndex(key);
Entry current = table[bucketIndex];
Entry prev = null;
while (current != null) {
if (current.key.equals(key)) {
if (prev == null) { // Removing the head of the list
table[bucketIndex] = current.next;
} else {
prev.next = current.next;
}
size--;
return;
}
prev = current;
current = current.next;
}
}
public boolean containsKey(Object key) {
return get(key) != null;
}
public int size() {
return size;
}
public void print() {
System.out.println("HashMap:");
for (int i = 0; i < capacity; i++) {
System.out.print("Bucket " + i + ": ");
Entry current = table[i];
while (current != null) {
System.out.print("(" + current.key + ", " + current.value + ") ");
current = current.next;
}
System.out.println();
}
}
}
f. Tree (Binary Search Tree - BST)
Concept: A non-linear data structure that organizes data in a hierarchical manner. A Binary Tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. A Binary Search Tree (BST) is a special type of binary tree where for each node:
All values in the left subtree are less than the node's value.
All values in the right subtree are greater than the node's value.
Characteristics:
Efficient for searching, insertion, and deletion if balanced.
Hierarchical structure.
Use Cases: Implementing sets and maps, databases (indexing), file systems, representing hierarchical data.
Time & Space Complexity (for a balanced BST):
Search: O(logn)
Insertion: O(logn)
Deletion: O(logn)
Worst-case (skewed tree, like a linked list): O(n) for all operations
Space: O(n) (for nodes)
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class CustomBinarySearchTree {
private TreeNode root;
public CustomBinarySearchTree() {
this.root = null;
}
// Insert operation
public void insert(int data) {
root = insertRecursive(root, data);
}
private TreeNode insertRecursive(TreeNode current, int data) {
if (current == null) {
return new TreeNode(data);
}
if (data < current.data) {
current.left = insertRecursive(current.left, data);
} else if (data > current.data) {
current.right = insertRecursive(current.right, data);
} else {
// Value already exists, handle as needed (e.g., do nothing, update)
return current;
}
return current;
}
// Search operation
public boolean search(int data) {
return searchRecursive(root, data);
}
private boolean searchRecursive(TreeNode current, int data) {
if (current == null) {
return false;
}
if (data == current.data) {
return true;
}
return data < current.data ? searchRecursive(current.left, data) : searchRecursive(current.right, data);
}
// Delete operation
public void delete(int data) {
root = deleteRecursive(root, data);
}
private TreeNode deleteRecursive(TreeNode current, int data) {
if (current == null) {
return null;
}
if (data == current.data) {
// Case 1: No children or one child
if (current.left == null) {
return current.right;
}
if (current.right == null) {
return current.left;
}
// Case 2: Two children
// Find the smallest value in the right subtree (in-order successor)
int smallestValue = findSmallestValue(current.right);
current.data = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;
}
if (data < current.data) {
current.left = deleteRecursive(current.left, data);
return current;
}
current.right = deleteRecursive(current.right, data);
return current;
}
private int findSmallestValue(TreeNode root) {
return root.left == null ? root.data : findSmallestValue(root.left);
}
// In-order traversal (Left -> Root -> Right)
public void inOrderTraversal() {
System.out.print("In-order Traversal: ");
inOrderTraversalRecursive(root);
System.out.println();
}
private void inOrderTraversalRecursive(TreeNode node) {
if (node != null) {
inOrderTraversalRecursive(node.left);
System.out.print(node.data + " ");
inOrderTraversalRecursive(node.right);
}
}
// Pre-order traversal (Root -> Left -> Right)
public void preOrderTraversal() {
System.out.print("Pre-order Traversal: ");
preOrderTraversalRecursive(root);
System.out.println();
}
private void preOrderTraversalRecursive(TreeNode node) {
if (node != null) {
System.out.print(node.data + " ");
preOrderTraversalRecursive(node.left);
preOrderTraversalRecursive(node.right);
}
}
// Post-order traversal (Left -> Right -> Root)
public void postOrderTraversal() {
System.out.print("Post-order Traversal: ");
postOrderTraversalRecursive(root);
System.out.println();
}
private void postOrderTraversalRecursive(TreeNode node) {
if (node != null) {
postOrderTraversalRecursive(node.left);
postOrderTraversalRecursive(node.right);
System.out.print(node.data + " ");
}
}
}
Bubble Sort
Concept: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.
Time Complexity:
Worst-case: O(n2)
Average-case: O(n2)
Best-case: O(n) (if already sorted)
Space Complexity: O(1)
Stability: Stable
class SortAlgorithms {
public void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were swapped by inner loop, then break
if (!swapped) {
break;
}
}
}
}
Insertion Sort
Concept: Builds the final sorted array (or list) one item at a time. It iterates through the input elements and consumes one input element in each iteration to place it into the correct sorted position in the array.
Time Complexity:
Worst-case: O(n2)
Average-case: O(n2)
Best-case: O(n) (if already sorted)
Space Complexity: O(1)
Stability: Stable
class SortAlgorithms {
public void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
Selection Sort
Concept: Divides the input list into two parts: a sorted sublist and an unsorted sublist. It repeatedly finds the minimum element from the unsorted sublist and puts it at the end of the sorted sublist.
Time Complexity:
Worst-case: O(n2)
Average-case: O(n2)
Best-case: O(n2) (always performs n2 comparisons)
Space Complexity: O(1)
Stability: Unstable
class SortAlgorithms {
public void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Find the minimum element in unsorted array
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
Merge Sort
Concept: A divide-and-conquer algorithm. It recursively divides the array into two halves until it reaches single-element arrays (which are inherently sorted). Then, it merges these sorted halves back together to produce a sorted array.
Time Complexity:
Worst-case: O(nlogn)
Average-case: O(nlogn)
Best-case: O(nlogn)
Space Complexity: O(n) (due to the temporary array used in merging)
Stability: Stable
class SortAlgorithms {
public void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
mergeSortRecursive(arr, new int[arr.length], 0, arr.length - 1);
}
private void mergeSortRecursive(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSortRecursive(arr, temp, left, mid); // Sort left half
mergeSortRecursive(arr, temp, mid + 1, right); // Sort right half
merge(arr, temp, left, mid, right); // Merge them
}
}
private void merge(int[] arr, int[] temp, int left, int mid, int right) {
// Copy both halves into the temporary array
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left; // Pointer for the left half
int j = mid + 1; // Pointer for the right half
int k = left; // Pointer for the main array
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// Copy remaining elements of left half, if any
while (i <= mid) {
arr[k++] = temp[i++];
}
// Copy remaining elements of right half, if any (not strictly necessary
// as they would already be in place if left half exhausted)
// while (j <= right) {
// arr[k++] = temp[j++];
// }
}
}
Heap Sort
Concept: A comparison-based sorting technique based on the Binary Heap data structure. It involves two main steps:
Building a max-heap from the input data.
Repeatedly extracting the maximum element from the heap and placing it at the end of the array, then rebuilding the heap.
Time Complexity:
Worst-case: O(nlogn)
Average-case: O(nlogn)
Best-case: O(nlogn)
Space Complexity: O(1)
Stability: Unstable
class SortAlgorithms {
public void heapSort(int[] arr) {
int n = arr.length;
// Build max heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
private void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
}
Quick Sort
Concept: A highly efficient, comparison-based sorting algorithm that also uses the divide-and-conquer paradigm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
Time Complexity:
Worst-case: O(n2) (occurs when the pivot selection consistently leads to highly unbalanced partitions, e.g., already sorted array with first/last element as pivot)
Average-case: O(nlogn)
Best-case: O(nlogn)
Space Complexity:
O(logn) (for recursion stack in average case), O(n) (worst case) Stability: Unstable
class SortAlgorithms {
public void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
quickSortRecursive(arr, 0, arr.length - 1);
}
private void quickSortRecursive(int[] arr, int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[pi] is now
at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSortRecursive(arr, low, pi - 1);
quickSortRecursive(arr, pi + 1, high);
}
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (than pivot) to left
of pivot and all greater elements to right of pivot */
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
Linear Search
Concept: Also known as sequential search. It checks each element in the list sequentially until a match is found or the end of the list is reached.
Time Complexity:
Worst-case: O(n) (element not found or at the end)
Average-case:
O(n) Best-case:
O(1) (element found at the beginning)
Space Complexity:
O(1) Applicability: Can be used on unsorted or sorted data.
class SearchAlgorithms {
public int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Return the index if target is found
}
}
return -1; // Return -1 if target is not found
}
}
Binary Search
Concept: An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, then the search narrows to the lower half. Otherwise, the search narrows to the upper half.
Prerequisite: The input array must be sorted.
Time Complexity:
Worst-case: O(logn)
Average-case: O(logn)
Best-case: O(1)
Space Complexity: O(1) (iterative) or O(logn) (recursive due to call stack)
class SearchAlgorithms {
public int binarySearchIterative(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // To prevent overflow for large low+high
if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
low = mid + 1; // Target is in the right half
} else {
high = mid - 1; // Target is in the left half
}
}
return -1; // Target not found
}
// Java Implementation (Recursive):
public int binarySearchRecursive(int[] arr, int target) {
return binarySearchRecursiveHelper(arr, target, 0, arr.length - 1);
}
private int binarySearchRecursiveHelper(int[] arr, int target, int low, int high) {
if (low > high) {
return -1; // Base case: element not found
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursiveHelper(arr, target, mid + 1, high);
} else {
return binarySearchRecursiveHelper(arr, target, low, mid - 1);
}
}
}
Depth-First Search (DFS)
Concept: An algorithm for traversing or searching tree or graph data structures. It starts at a chosen root (or arbitrary node) and explores as far as possible along each branch before backtracking. It typically uses a stack (implicitly with recursion or explicitly with an iterative approach).
Use Cases: Finding connected components, topological sorting, solving mazes, pathfinding (simple paths).
Time Complexity: where V is the number of vertices and E is the number of edges (for graphs). O(V) for trees.
Space Complexity: O(V) (for recursion stack or explicit stack)
class GraphDFS {
private int V; // Number of vertices
private List<List<Integer>> adj; // Adjacency list
public GraphDFS(int v) {
V = v;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int u, int v) {
adj.get(u).add(v); // For undirected graph, add adj.get(v).add(u); as well
}
// Recursive DFS traversal
public void dfsRecursive(int startNode) {
boolean[] visited = new boolean[V];
System.out.print("DFS Traversal (Recursive): ");
dfsRecursiveHelper(startNode, visited);
System.out.println();
}
private void dfsRecursiveHelper(int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfsRecursiveHelper(neighbor, visited);
}
}
}
// Iterative DFS traversal
public void dfsIterative(int startNode) {
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(startNode);
visited[startNode] = true;
System.out.print("DFS Traversal (Iterative): ");
while (!stack.isEmpty()) {
int currentNode = stack.pop();
System.out.print(currentNode + " ");
// Get all adjacent vertices of the popped vertex.
// If a neighbor has not been visited, then push it to the stack.
// Pushing in reverse order to explore smaller neighbors first, if order matters
for (int i = adj.get(currentNode).size() - 1; i >= 0; i--) {
int neighbor = adj.get(currentNode).get(i);
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
System.out.println();
}
}
Breadth-First Search (BFS)
Concept: An algorithm for traversing or searching tree or graph data structures. It starts at a chosen root (or arbitrary node) and explores all the neighbor nodes at the present depth level before moving on to the nodes at the next depth level. It typically uses a queue.
Use Cases: Finding the shortest path in an unweighted graph, peer-to-peer networking, web crawlers, garbage collection.
Time Complexity: where V is the number of vertices and E is the number of edges (for graphs). O(V) for trees.
Space Complexity: O(V) (for the queue)
class GraphBFS {
private int V; // Number of vertices
private List<List<Integer>> adj; // Adjacency list
public GraphBFS(int v) {
V = v;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int u, int v) {
adj.get(u).add(v); // For undirected graph, add adj.get(v).add(u); as well
}
// BFS traversal
public void bfs(int startNode) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[startNode] = true;
queue.add(startNode);
System.out.print("BFS Traversal: ");
while (!queue.isEmpty()) {
int currentNode = queue.poll();
System.out.print(currentNode + " ");
// Get all adjacent vertices of the dequeued vertex.
// If a neighbor has not been visited, then mark it visited and enqueue it.
for (int neighbor : adj.get(currentNode)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
System.out.println();
}
}
Dynamic Programming
Concept: An algorithmic technique for solving problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations. It's typically used for optimization problems.
Key Characteristics:
Optimal Substructure: Optimal solution to a problem can be constructed from optimal solutions of its subproblems.
Overlapping Subproblems: The same subproblems are solved repeatedly.
Approaches:
Memoization (Top-down): Recursive approach that stores the results of subproblems in a cache (e.g., hash map or array) to avoid recomputing them.
Tabulation (Bottom-up): Iterative approach that builds up the solution from the smallest subproblems to the larger ones, storing results in a table.
Java Example: Fibonacci Sequence
Problem: Calculate the n-th Fibonacci number ( with ).
1. Recursive (without DP - for comparison):
class DynamicProgrammingExamples {
public int fibonacciRecursive(int n) {
if (n <= 1) {
return n;
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}
}
fibonacciRecursive(2) multiple times, leading to exponential time complexity.class DynamicProgrammingExamples {
private Map<Integer, Integer> memo = new HashMap<>();
public int fibonacciMemoization(int n) {
if (n <= 1) {
return n;
}
if (memo.containsKey(n)) {
return memo.get(n);
}
int result = fibonacciMemoization(n - 1) + fibonacciMemoization(n - 2);
memo.put(n, result);
return result;
}
}
class DynamicProgrammingExamples {
public int fibonacciTabulation(int n) {
if (n <= 1) {
return n;
}
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
class DynamicProgrammingExamples {
// Given coins and a target amount, return the fewest number of coins
// that you need to make up that amount. If that amount of money cannot
// be made up by any combination of the coins, return -1.
public int coinChange(int[] coins, int amount) {
// dp[i] will store the minimum coins needed for amount i
int[] dp = new int[amount + 1];
// Initialize dp array with amount + 1 (representing infinity)
// 0 coins needed for amount 0
for (int i = 1; i <= amount; i++) {
dp[i] = amount + 1;
}
dp[0] = 0;
// Iterate through each amount from 1 to 'amount'
for (int i = 1; i <= amount; i++) {
// For each amount, iterate through all available coins
for (int coin : coins) {
// If the current coin can be used to form the current amount 'i'
if (coin <= i) {
// Update dp[i] with the minimum of its current value
// and 1 (for the current coin) + dp[i - coin] (for the remaining amount)
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
// If dp[amount] is still amount + 1, it means the amount cannot be made
return dp[amount] > amount ? -1 : dp[amount];
}
}
d. Backtracking
Concept: A general algorithmic technique for solving problems, particularly constraint satisfaction problems. It builds a solution incrementally, and if a partial solution leads to a dead end (violates constraints or cannot lead to a complete solution), it "backtracks" to a previous state and tries a different path. It's often implemented recursively.
Key Characteristics: Explores all possible paths (similar to DFS), but prunes branches that are invalid.
Use Cases: Solving Sudoku, N-Queens problem, generating permutations/combinations, finding Hamiltonian paths.
class BacktrackingExamples {
public List<List<String>> solveNQueens(int n) {
List<List<String>> solutions = new ArrayList<>();
char[][] board = new char[n][n];
// Initialize board with '.' (empty cells)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
solve(board, 0, solutions);
return solutions;
}
private void solve(char[][] board, int row, List<List<String>> solutions) {
if (row == board.length) { // All queens placed successfully
solutions.add(constructBoard(board));
return;
}
for (int col = 0; col < board.length; col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q'; // Place queen
solve(board, row + 1, solutions); // Recurse for the next row
board[row][col] = '.'; // Backtrack: remove queen
}
}
}
private boolean isValid(char[][] board, int row, int col) {
// Check current column
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// Check upper left diagonal
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check upper right diagonal
for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
private List<String> constructBoard(char[][] board) {
List<String> currentBoard = new ArrayList<>();
for (char[] row : board) {
currentBoard.add(new String(row));
}
return currentBoard;
}
}
e. Sliding Window
Concept: A technique used for problems that involve arrays or lists, where we need to find a sub-array or a sub-string that satisfies certain conditions. It works by maintaining a "window" (a contiguous range of elements) that slides over the data. The window size can be fixed or dynamic.
Use Cases: Finding maximum/minimum sum subarray of a given size, finding the longest substring with K distinct characters, finding anagrams.
Time Complexity: Often reduces O(N2) brute-force solutions to O(N) by avoiding redundant computations.
class SlidingWindowExamples {
public int maxSubarraySum(int[] arr, int k) {
if (k > arr.length || k <= 0) {
throw new IllegalArgumentException("Invalid k or array length.");
}
int maxSum = 0;
int windowSum = 0;
// Calculate sum of the first window
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// Slide the window
for (int i = k; i < arr.length; i++) {
// Subtract the element going out of the window
// Add the element coming into the window
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
}
That's a comprehensive plan for a blog on data structures, algorithms, and system design! I can definitely help you explain these concepts. Let's break down each point.
Mastering Data Structures, Algorithms, and System Design
Welcome to a deep dive into the foundational elements of computer science and software engineering! This blog post will guide you through the essentials of data structures, algorithms, and key system design concepts, providing clear explanations and practical Java implementations.
1. What is a Data Structure?
At its core, a data structure is a specialized format for organizing and storing data in a computer so that it can be accessed and modified efficiently. Think of it as a container or a blueprint that defines how data is arranged, allowing for various operations (like searching, inserting, deleting, and updating) to be performed effectively. The choice of data structure can significantly impact the performance and efficiency of an algorithm or an entire software system.
Common examples include arrays, linked lists, trees, graphs, and hash tables, each with its strengths and weaknesses depending on the specific problem you're trying to solve.
2. Time and Space Complexity: Understanding Performance
When we talk about the efficiency of an algorithm, we primarily consider its time complexity and space complexity. These concepts help us understand how an algorithm scales with the size of its input.
Time Complexity: Measures the amount of time an algorithm takes to run as a function of the input size (n). It doesn't measure the actual execution time in seconds, but rather the number of operations performed. We typically express time complexity using Big O notation (O(n)), which describes the upper bound or worst-case scenario for an algorithm's growth rate.
Common Big O Notations:
O(1): Constant time (e.g., accessing an array element by index).
O(logn): Logarithmic time (e.g., binary search).
O(n): Linear time (e.g., iterating through a list).
O(nlogn): Linearithmic time (e.g., merge sort, quicksort).
O(n2): Quadratic time (e.g., bubble sort, nested loops).
O(2n): Exponential time (e.g., certain recursive algorithms without memoization).
O(n): Factorial time (e.g., brute-force solutions for traveling salesman).
Space Complexity: Measures the amount of memory (space) an algorithm uses as a function of the input size (n). This includes the space used by the input itself and any auxiliary space required by the algorithm during its execution. Like time complexity, it's also expressed using Big O notation.
How to Calculate Time and Space Complexity:
Calculating complexity involves analyzing the operations an algorithm performs.
Identify the Input Size (n): What defines the "size" of the problem? Is it the number of elements in an array, the number of nodes in a tree, etc.?
Count Operations (Time Complexity):
Basic Operations: Assigning a value, arithmetic operations, comparisons, array access by index are generally considered O(1).
Loops: If a loop runs
ntimes and performs O(1) operations inside, the loop's complexity is O(n). Nested loops multiply complexities (e.g., two nested loops runningntimes each result in O(n2)).Recursion: Analyze the recurrence relation. The Master Theorem can be useful for divide-and-conquer algorithms.
Conditional Statements: Consider the worst-case path.
Count Memory Usage (Space Complexity):
Variables: Basic variables typically consume O(1) space.
Data Structures: The space used by data structures scales with the number of elements stored (e.g., an array of
nelements uses O(n) space).Recursion Stack: Recursive calls consume stack space. If the recursion depth is
n, it can be O(n) space.
Example (Time Complexity):
public void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) { // Loop runs 'arr.length' times (n times)
System.out.println(arr[i]); // O(1) operation
}
}
Here, the loop runs n times (where n is arr.length). Inside the loop, System.out.println is an O(1) operation. Therefore, the total time complexity is $O(n) \* O(1) = O(n)$.
Example (Space Complexity):
public int sumArray(int[] arr) {
int sum = 0; // O(1) space for 'sum' variable
for (int num : arr) {
sum += num;
}
return sum;
}
In this example, we only use a single int variable sum regardless of the input array size. Thus, the space complexity is O(1) (constant space).
3. Core Data Structures with Java Implementations
Let's explore some fundamental data structures and implement them in Java without using the standard java.util collections.
a. Array
Concept: A collection of elements of the same data type stored in contiguous memory locations. Elements are accessed using an index.
Characteristics:
Fixed size (in most languages, once declared).
Direct access to elements using index (O(1)).
Use Cases: Storing a fixed number of items, lookup by index, implementing other data structures.
Time & Space Complexity:
Access/Read: O(1)
Insertion/Deletion (at end): O(1) (if space is available)
Insertion/Deletion (at beginning/middle): O(n) (requires shifting elements)
Space: O(n) (where
nis the size of the array)
Java Implementation:
class CustomArray {
private int[] data;
private int size; // Current number of elements
public CustomArray(int capacity) {
data = new int[capacity];
size = 0;
}
public void add(int value) {
if (size == data.length) {
// In a real scenario, you'd resize the array (e.g., double its capacity)
System.out.println("Array is full. Cannot add more elements.");
return;
}
data[size++] = value;
}
public int get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
}
return data[index];
}
public void set(int index, int value) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
}
data[index] = value;
}
public void removeAt(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("Index " + index + " out of bounds for size " + size);
}
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
size--;
}
public int getSize() {
return size;
}
public void print() {
System.out.print("Array: [");
for (int i = 0; i < size; i++) {
System.out.print(data[i]);
if (i < size - 1) {
System.out.print(", ");
}
}
System.out.println("]");
}
}
b. Linked List
Concept: A linear collection of elements (nodes) where each node points to the next node in the sequence. Unlike arrays, linked lists do not store elements in contiguous memory locations.
Characteristics:
Dynamic size.
Elements are not stored contiguously.
Accessing an element requires traversing from the beginning (O(n)).
Use Cases: Implementing stacks, queues, hash maps (for collision resolution), dynamic memory allocation.
Time & Space Complexity:
Access/Search: O(n)
Insertion/Deletion (at beginning/end - if tail pointer exists): O(1)
Insertion/Deletion (at middle): O(n) (requires traversing to find the position)
Space: O(n) (for nodes)
Java Implementation (Singly Linked List):
class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
this.next = null;
}
}
class CustomLinkedList {
private Node head;
private int size;
public CustomLinkedList() {
this.head = null;
this.size = 0;
}
public void addFirst(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
size++;
}
public void addLast(int data) {
Node newNode = new Node(data);
if (head == null) {
head = newNode;
size++;
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
size++;
}
public void removeFirst() {
if (head == null) {
System.out.println("List is empty. Cannot remove.");
return;
}
head = head.next;
size--;
}
public void removeLast() {
if (head == null) {
System.out.println("List is empty. Cannot remove.");
return;
}
if (head.next == null) { // Only one element
head = null;
size--;
return;
}
Node current = head;
Node prev = null;
while (current.next != null) {
prev = current;
current = current.next;
}
prev.next = null;
size--;
}
public boolean contains(int data) {
Node current = head;
while (current != null) {
if (current.data == data) {
return true;
}
current = current.next;
}
return false;
}
public int getSize() {
return size;
}
public void print() {
Node current = head;
System.out.print("LinkedList: [");
while (current != null) {
System.out.print(current.data);
if (current.next != null) {
System.out.print(" -> ");
}
current = current.next;
}
System.out.println("]");
}
}
c. Stack
Concept: A linear data structure that follows the Last-In, First-Out (LIFO) principle. Think of a stack of plates: the last plate you put on is the first one you take off.
Operations:
push(): Adds an element to the top of the stack.pop(): Removes and returns the element from the top of the stack.peek(): Returns the top element without removing it.isEmpty(): Checks if the stack is empty.
Use Cases: Function call stack, undo/redo functionality, expression evaluation, backtracking algorithms.
Time & Space Complexity:
Push: O(1)
Pop: O(1)
Peek: O(1)
IsEmpty: O(1)
Space: O(n)
Java Implementation (using an Array):
class CustomStack {
private int[] stackArray;
private int top; // Index of the top element
private int capacity;
public CustomStack(int capacity) {
this.capacity = capacity;
stackArray = new int[capacity];
top = -1; // Indicates an empty stack
}
public void push(int value) {
if (top == capacity - 1) {
System.out.println("Stack Overflow: Stack is full.");
return;
}
stackArray[++top] = value;
}
public int pop() {
if (isEmpty()) {
System.out.println("Stack Underflow: Stack is empty.");
return -1; // Or throw an exception
}
return stackArray[top--];
}
public int peek() {
if (isEmpty()) {
System.out.println("Stack is empty.");
return -1; // Or throw an exception
}
return stackArray[top];
}
public boolean isEmpty() {
return top == -1;
}
public int size() {
return top + 1;
}
public void print() {
System.out.print("Stack: [");
for (int i = 0; i <= top; i++) {
System.out.print(stackArray[i]);
if (i < top) {
System.out.print(", ");
}
}
System.out.println("] (Top: " + (isEmpty() ? "None" : stackArray[top]) + ")");
}
}
d. Queue
Concept: A linear data structure that follows the First-In, First-Out (FIFO) principle. Like a line of people waiting: the first person in line is the first one served.
Operations:
enqueue(): Adds an element to the rear of the queue.dequeue(): Removes and returns the element from the front of the queue.peek(): Returns the front element without removing it.isEmpty(): Checks if the queue is empty.
Use Cases: Task scheduling, breadth-first search, printer queues, simulating waiting lines.
Time & Space Complexity:
Enqueue: O(1)
Dequeue: O(1)
Peek: O(1)
IsEmpty: O(1)
Space: O(n)
Java Implementation (using an Array - Circular Array for efficiency):
class CustomQueue {
private int[] queueArray;
private int front;
private int rear;
private int size;
private int capacity;
public CustomQueue(int capacity) {
this.capacity = capacity;
queueArray = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
public void enqueue(int value) {
if (size == capacity) {
System.out.println("Queue Overflow: Queue is full.");
return;
}
rear = (rear + 1) % capacity; // Circular increment
queueArray[rear] = value;
size++;
}
public int dequeue() {
if (isEmpty()) {
System.out.println("Queue Underflow: Queue is empty.");
return -1; // Or throw an exception
}
int data = queueArray[front];
front = (front + 1) % capacity; // Circular increment
size--;
return data;
}
public int peek() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return -1; // Or throw an exception
}
return queueArray[front];
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void print() {
System.out.print("Queue: [");
if (!isEmpty()) {
for (int i = 0; i < size; i++) {
System.out.print(queueArray[(front + i) % capacity]);
if (i < size - 1) {
System.out.print(", ");
}
}
}
System.out.println("] (Front: " + (isEmpty() ? "None" : queueArray[front]) + ")");
}
}
e. HashMap (Hash Table)
Concept: A data structure that stores key-value pairs. It uses a hash function to map keys to array indices (buckets) to provide fast data retrieval. Collisions (when two different keys hash to the same index) are handled using techniques like chaining (linked lists) or open addressing.
Characteristics:
Aims for O(1) average-case time complexity for operations.
No inherent order of elements.
Use Cases: Caching, counting frequencies, implementing dictionaries/associative arrays, symbol tables.
Time & Space Complexity:
Put/Insert (Average): O(1)
Get/Search (Average): O(1)
Remove (Average): O(1)
Put/Get/Remove (Worst-case, due to collisions): O(n) (if all keys hash to the same bucket, it degrades to a linked list traversal)
Space: O(n) (for storing
nkey-value pairs)
Java Implementation (using chaining with Linked Lists):
// Helper class for key-value pair
class Entry {
Object key;
Object value;
Entry next;
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
this.next = null;
}
}
class CustomHashMap {
private Entry[] table;
private int capacity;
private int size; // Number of key-value pairs
public CustomHashMap(int capacity) {
this.capacity = capacity;
table = new Entry[capacity];
size = 0;
}
private int getBucketIndex(Object key) {
// Simple hash function using Java's hashCode()
return Math.abs(key.hashCode() % capacity);
}
public void put(Object key, Object value) {
int bucketIndex = getBucketIndex(key);
Entry newEntry = new Entry(key, value);
if (table[bucketIndex] == null) {
table[bucketIndex] = newEntry;
size++;
} else {
Entry current = table[bucketIndex];
Entry prev = null;
while (current != null) {
if (current.key.equals(key)) {
current.value = value; // Update value if key exists
return;
}
prev = current;
current = current.next;
}
// Key not found, add to the end of the chain
prev.next = newEntry;
size++;
}
}
public Object get(Object key) {
int bucketIndex = getBucketIndex(key);
Entry current = table[bucketIndex];
while (current != null) {
if (current.key.equals(key)) {
return current.value;
}
current = current.next;
}
return null; // Key not found
}
public void remove(Object key) {
int bucketIndex = getBucketIndex(key);
Entry current = table[bucketIndex];
Entry prev = null;
while (current != null) {
if (current.key.equals(key)) {
if (prev == null) { // Removing the head of the list
table[bucketIndex] = current.next;
} else {
prev.next = current.next;
}
size--;
return;
}
prev = current;
current = current.next;
}
}
public boolean containsKey(Object key) {
return get(key) != null;
}
public int size() {
return size;
}
public void print() {
System.out.println("HashMap:");
for (int i = 0; i < capacity; i++) {
System.out.print("Bucket " + i + ": ");
Entry current = table[i];
while (current != null) {
System.out.print("(" + current.key + ", " + current.value + ") ");
current = current.next;
}
System.out.println();
}
}
}
f. Tree (Binary Search Tree - BST)
Concept: A non-linear data structure that organizes data in a hierarchical manner. A Binary Tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. A Binary Search Tree (BST) is a special type of binary tree where for each node:
All values in the left subtree are less than the node's value.
All values in the right subtree are greater than the node's value.
Characteristics:
Efficient for searching, insertion, and deletion if balanced.
Hierarchical structure.
Use Cases: Implementing sets and maps, databases (indexing), file systems, representing hierarchical data.
Time & Space Complexity (for a balanced BST):
Search: O(logn)
Insertion: O(logn)
Deletion: O(logn)
Worst-case (skewed tree, like a linked list): O(n) for all operations
Space: O(n) (for nodes)
Java Implementation (Binary Search Tree):
class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class CustomBinarySearchTree {
private TreeNode root;
public CustomBinarySearchTree() {
this.root = null;
}
// Insert operation
public void insert(int data) {
root = insertRecursive(root, data);
}
private TreeNode insertRecursive(TreeNode current, int data) {
if (current == null) {
return new TreeNode(data);
}
if (data < current.data) {
current.left = insertRecursive(current.left, data);
} else if (data > current.data) {
current.right = insertRecursive(current.right, data);
} else {
// Value already exists, handle as needed (e.g., do nothing, update)
return current;
}
return current;
}
// Search operation
public boolean search(int data) {
return searchRecursive(root, data);
}
private boolean searchRecursive(TreeNode current, int data) {
if (current == null) {
return false;
}
if (data == current.data) {
return true;
}
return data < current.data ? searchRecursive(current.left, data) : searchRecursive(current.right, data);
}
// Delete operation
public void delete(int data) {
root = deleteRecursive(root, data);
}
private TreeNode deleteRecursive(TreeNode current, int data) {
if (current == null) {
return null;
}
if (data == current.data) {
// Case 1: No children or one child
if (current.left == null) {
return current.right;
}
if (current.right == null) {
return current.left;
}
// Case 2: Two children
// Find the smallest value in the right subtree (in-order successor)
int smallestValue = findSmallestValue(current.right);
current.data = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;
}
if (data < current.data) {
current.left = deleteRecursive(current.left, data);
return current;
}
current.right = deleteRecursive(current.right, data);
return current;
}
private int findSmallestValue(TreeNode root) {
return root.left == null ? root.data : findSmallestValue(root.left);
}
// In-order traversal (Left -> Root -> Right)
public void inOrderTraversal() {
System.out.print("In-order Traversal: ");
inOrderTraversalRecursive(root);
System.out.println();
}
private void inOrderTraversalRecursive(TreeNode node) {
if (node != null) {
inOrderTraversalRecursive(node.left);
System.out.print(node.data + " ");
inOrderTraversalRecursive(node.right);
}
}
// Pre-order traversal (Root -> Left -> Right)
public void preOrderTraversal() {
System.out.print("Pre-order Traversal: ");
preOrderTraversalRecursive(root);
System.out.println();
}
private void preOrderTraversalRecursive(TreeNode node) {
if (node != null) {
System.out.print(node.data + " ");
preOrderTraversalRecursive(node.left);
preOrderTraversalRecursive(node.right);
}
}
// Post-order traversal (Left -> Right -> Root)
public void postOrderTraversal() {
System.out.print("Post-order Traversal: ");
postOrderTraversalRecursive(root);
System.out.println();
}
private void postOrderTraversalRecursive(TreeNode node) {
if (node != null) {
postOrderTraversalRecursive(node.left);
postOrderTraversalRecursive(node.right);
System.out.print(node.data + " ");
}
}
}
4. Different Sorting Algorithms with Core Java Implementations
Sorting algorithms arrange elements of a list in a specific order (ascending or descending).
a. Bubble Sort
Concept: Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted.
Time Complexity:
Worst-case: O(n2)
Average-case: O(n2)
Best-case: O(n) (if already sorted)
Space Complexity: O(1)
Stability: Stable
Java Implementation:
class SortAlgorithms {
public void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no two elements were swapped by inner loop, then break
if (!swapped) {
break;
}
}
}
}
b. Insertion Sort
Concept: Builds the final sorted array (or list) one item at a time. It iterates through the input elements and consumes one input element in each iteration to place it into the correct sorted position in the array.
Time Complexity:
Worst-case: O(n2)
Average-case: O(n2)
Best-case: O(n) (if already sorted)
Space Complexity: O(1)
Stability: Stable
Java Implementation:
class SortAlgorithms {
// ... other sorts ...
public void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
}
c. Selection Sort
Concept: Divides the input list into two parts: a sorted sublist and an unsorted sublist. It repeatedly finds the minimum element from the unsorted sublist and puts it at the end of the sorted sublist.
Time Complexity:
Worst-case: O(n2)
Average-case: O(n2)
Best-case: O(n2) (always performs n2 comparisons)
Space Complexity: O(1)
Stability: Unstable
Java Implementation:
class SortAlgorithms {
// ... other sorts ...
public void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
// Find the minimum element in unsorted array
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first element
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
}
d. Merge Sort
Concept: A divide-and-conquer algorithm. It recursively divides the array into two halves until it reaches single-element arrays (which are inherently sorted). Then, it merges these sorted halves back together to produce a sorted array.
Time Complexity:
Worst-case: O(nlogn)
Average-case: O(nlogn)
Best-case: O(nlogn)
Space Complexity: O(n) (due to the temporary array used in merging)
Stability: Stable
Java Implementation:
class SortAlgorithms {
// ... other sorts ...
public void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
mergeSortRecursive(arr, new int[arr.length], 0, arr.length - 1);
}
private void mergeSortRecursive(int[] arr, int[] temp, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
mergeSortRecursive(arr, temp, left, mid); // Sort left half
mergeSortRecursive(arr, temp, mid + 1, right); // Sort right half
merge(arr, temp, left, mid, right); // Merge them
}
}
private void merge(int[] arr, int[] temp, int left, int mid, int right) {
// Copy both halves into the temporary array
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left; // Pointer for the left half
int j = mid + 1; // Pointer for the right half
int k = left; // Pointer for the main array
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// Copy remaining elements of left half, if any
while (i <= mid) {
arr[k++] = temp[i++];
}
// Copy remaining elements of right half, if any (not strictly necessary
// as they would already be in place if left half exhausted)
// while (j <= right) {
// arr[k++] = temp[j++];
// }
}
}
e. Heap Sort
Concept: A comparison-based sorting technique based on the Binary Heap data structure. It involves two main steps:
Building a max-heap from the input data.
Repeatedly extracting the maximum element from the heap and placing it at the end of the array, then rebuilding the heap.
Time Complexity:
Worst-case: O(nlogn)
Average-case: O(nlogn)
Best-case: O(nlogn)
Space Complexity: O(1)
Stability: Unstable
Java Implementation:
class SortAlgorithms {
// ... other sorts ...
public void heapSort(int[] arr) {
int n = arr.length;
// Build max heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
private void heapify(int[] arr, int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2*i + 1
int right = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If right child is larger than largest so far
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
}
f. Quick Sort
Concept: A highly efficient, comparison-based sorting algorithm that also uses the divide-and-conquer paradigm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
Time Complexity:
Worst-case: O(n2) (occurs when the pivot selection consistently leads to highly unbalanced partitions, e.g., already sorted array with first/last element as pivot)
Average-case: O(nlogn)
Best-case: O(nlogn)
Space Complexity:
O(logn) (for recursion stack in average case), O(n) (worst case) Stability: Unstable
Java Implementation:
class SortAlgorithms {
// ... other sorts ...
public void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
quickSortRecursive(arr, 0, arr.length - 1);
}
private void quickSortRecursive(int[] arr, int low, int high) {
if (low < high) {
/* pi is partitioning index, arr[pi] is now
at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSortRecursive(arr, low, pi - 1);
quickSortRecursive(arr, pi + 1, high);
}
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (than pivot) to left
of pivot and all greater elements to right of pivot */
private int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
}
5. Different Searching Algorithms with Core Java Implementations
Searching algorithms are used to find the location of a target element within a data structure.
a. Linear Search
Concept: Also known as sequential search. It checks each element in the list sequentially until a match is found or the end of the list is reached.
Time Complexity:
Worst-case: O(n) (element not found or at the end)
Average-case:
O(n) Best-case:
O(1) (element found at the beginning)
Space Complexity:
O(1) Applicability: Can be used on unsorted or sorted data.
Java Implementation:
class SearchAlgorithms {
public int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i; // Return the index if target is found
}
}
return -1; // Return -1 if target is not found
}
}
b. Binary Search
Concept: An efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, then the search narrows to the lower half. Otherwise, the search narrows to the upper half.
Prerequisite: The input array must be sorted.
Time Complexity:
Worst-case: O(logn)
Average-case: O(logn)
Best-case: O(1)
Space Complexity: O(1) (iterative) or O(logn) (recursive due to call stack)
Java Implementation (Iterative):
class SearchAlgorithms {
// ... other searches ...
public int binarySearchIterative(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2; // To prevent overflow for large low+high
if (arr[mid] == target) {
return mid; // Target found
} else if (arr[mid] < target) {
low = mid + 1; // Target is in the right half
} else {
high = mid - 1; // Target is in the left half
}
}
return -1; // Target not found
}
// Java Implementation (Recursive):
public int binarySearchRecursive(int[] arr, int target) {
return binarySearchRecursiveHelper(arr, target, 0, arr.length - 1);
}
private int binarySearchRecursiveHelper(int[] arr, int target, int low, int high) {
if (low > high) {
return -1; // Base case: element not found
}
int mid = low + (high - low) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
return binarySearchRecursiveHelper(arr, target, mid + 1, high);
} else {
return binarySearchRecursiveHelper(arr, target, low, mid - 1);
}
}
}
6. Explain Following Algorithms with Java Examples
a. Depth-First Search (DFS)
Concept: An algorithm for traversing or searching tree or graph data structures. It starts at a chosen root (or arbitrary node) and explores as far as possible along each branch before backtracking. It typically uses a stack (implicitly with recursion or explicitly with an iterative approach).
Use Cases: Finding connected components, topological sorting, solving mazes, pathfinding (simple paths).
Time Complexity: where V is the number of vertices and E is the number of edges (for graphs). O(V) for trees.
Space Complexity: O(V) (for recursion stack or explicit stack)
Java Example (on a graph represented by an adjacency list):
import java.util.ArrayList;
import java.util.Stack;
import java.util.List;
class GraphDFS {
private int V; // Number of vertices
private List<List<Integer>> adj; // Adjacency list
public GraphDFS(int v) {
V = v;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int u, int v) {
adj.get(u).add(v); // For undirected graph, add adj.get(v).add(u); as well
}
// Recursive DFS traversal
public void dfsRecursive(int startNode) {
boolean[] visited = new boolean[V];
System.out.print("DFS Traversal (Recursive): ");
dfsRecursiveHelper(startNode, visited);
System.out.println();
}
private void dfsRecursiveHelper(int node, boolean[] visited) {
visited[node] = true;
System.out.print(node + " ");
for (int neighbor : adj.get(node)) {
if (!visited[neighbor]) {
dfsRecursiveHelper(neighbor, visited);
}
}
}
// Iterative DFS traversal
public void dfsIterative(int startNode) {
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>();
stack.push(startNode);
visited[startNode] = true;
System.out.print("DFS Traversal (Iterative): ");
while (!stack.isEmpty()) {
int currentNode = stack.pop();
System.out.print(currentNode + " ");
// Get all adjacent vertices of the popped vertex.
// If a neighbor has not been visited, then push it to the stack.
// Pushing in reverse order to explore smaller neighbors first, if order matters
for (int i = adj.get(currentNode).size() - 1; i >= 0; i--) {
int neighbor = adj.get(currentNode).get(i);
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
System.out.println();
}
}
b. Breadth-First Search (BFS)
Concept: An algorithm for traversing or searching tree or graph data structures. It starts at a chosen root (or arbitrary node) and explores all the neighbor nodes at the present depth level before moving on to the nodes at the next depth level. It typically uses a queue.
Use Cases: Finding the shortest path in an unweighted graph, peer-to-peer networking, web crawlers, garbage collection.
Time Complexity: where V is the number of vertices and E is the number of edges (for graphs). O(V) for trees.
Space Complexity: O(V) (for the queue)
Java Example (on a graph represented by an adjacency list):
import java.util.ArrayList;
import java.util.LinkedList; // Using LinkedList as a Queue
import java.util.Queue;
import java.util.List;
class GraphBFS {
private int V; // Number of vertices
private List<List<Integer>> adj; // Adjacency list
public GraphBFS(int v) {
V = v;
adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int u, int v) {
adj.get(u).add(v); // For undirected graph, add adj.get(v).add(u); as well
}
// BFS traversal
public void bfs(int startNode) {
boolean[] visited = new boolean[V];
Queue<Integer> queue = new LinkedList<>();
visited[startNode] = true;
queue.add(startNode);
System.out.print("BFS Traversal: ");
while (!queue.isEmpty()) {
int currentNode = queue.poll();
System.out.print(currentNode + " ");
// Get all adjacent vertices of the dequeued vertex.
// If a neighbor has not been visited, then mark it visited and enqueue it.
for (int neighbor : adj.get(currentNode)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
System.out.println();
}
}
c. Dynamic Programming
Concept: An algorithmic technique for solving problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant computations. It's typically used for optimization problems.
Key Characteristics:
Optimal Substructure: Optimal solution to a problem can be constructed from optimal solutions of its subproblems.
Overlapping Subproblems: The same subproblems are solved repeatedly.
Approaches:
Memoization (Top-down): Recursive approach that stores the results of subproblems in a cache (e.g., hash map or array) to avoid recomputing them.
Tabulation (Bottom-up): Iterative approach that builds up the solution from the smallest subproblems to the larger ones, storing results in a table.
Java Example: Fibonacci Sequence
Problem: Calculate the n-th Fibonacci number ( with ).
1. Recursive (without DP - for comparison):
Javaclass DynamicProgrammingExamples { public int fibonacciRecursive(int n) { if (n <= 1) { return n; } return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); } }Issue: Highly inefficient due to redundant calculations of
fibonacciRecursive(2)multiple times, leading to exponential time complexity.
2. Dynamic Programming (Memoization - Top-down):
Javaimport java.util.HashMap; import java.util.Map; class DynamicProgrammingExamples { private Map<Integer, Integer> memo = new HashMap<>(); public int fibonacciMemoization(int n) { if (n <= 1) { return n; } if (memo.containsKey(n)) { return memo.get(n); } int result = fibonacciMemoization(n - 1) + fibonacciMemoization(n - 2); memo.put(n, result); return result; } }Time Complexity: O(n)
Space Complexity: O(n) (for hash map/recursion stack)
3. Dynamic Programming (Tabulation - Bottom-up):
Javaclass DynamicProgrammingExamples { public int fibonacciTabulation(int n) { if (n <= 1) { return n; } int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }Time Complexity: O(n)
Space Complexity: O(n) (for
dparray)
Another Example: Coin Change Problem (Minimum number of coins to make a sum)
Javaclass DynamicProgrammingExamples { // Given coins and a target amount, return the fewest number of coins // that you need to make up that amount. If that amount of money cannot // be made up by any combination of the coins, return -1. public int coinChange(int[] coins, int amount) { // dp[i] will store the minimum coins needed for amount i int[] dp = new int[amount + 1]; // Initialize dp array with amount + 1 (representing infinity) // 0 coins needed for amount 0 for (int i = 1; i <= amount; i++) { dp[i] = amount + 1; } dp[0] = 0; // Iterate through each amount from 1 to 'amount' for (int i = 1; i <= amount; i++) { // For each amount, iterate through all available coins for (int coin : coins) { // If the current coin can be used to form the current amount 'i' if (coin <= i) { // Update dp[i] with the minimum of its current value // and 1 (for the current coin) + dp[i - coin] (for the remaining amount) dp[i] = Math.min(dp[i], 1 + dp[i - coin]); } } } // If dp[amount] is still amount + 1, it means the amount cannot be made return dp[amount] > amount ? -1 : dp[amount]; } }
d. Backtracking
Concept: A general algorithmic technique for solving problems, particularly constraint satisfaction problems. It builds a solution incrementally, and if a partial solution leads to a dead end (violates constraints or cannot lead to a complete solution), it "backtracks" to a previous state and tries a different path. It's often implemented recursively.
Key Characteristics: Explores all possible paths (similar to DFS), but prunes branches that are invalid.
Use Cases: Solving Sudoku, N-Queens problem, generating permutations/combinations, finding Hamiltonian paths.
Java Example: N-Queens Problem
Problem: Place N non-attacking queens on an N×N chessboard.
Javaimport java.util.ArrayList; import java.util.List; class BacktrackingExamples { public List<List<String>> solveNQueens(int n) { List<List<String>> solutions = new ArrayList<>(); char[][] board = new char[n][n]; // Initialize board with '.' (empty cells) for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { board[i][j] = '.'; } } solve(board, 0, solutions); return solutions; } private void solve(char[][] board, int row, List<List<String>> solutions) { if (row == board.length) { // All queens placed successfully solutions.add(constructBoard(board)); return; } for (int col = 0; col < board.length; col++) { if (isValid(board, row, col)) { board[row][col] = 'Q'; // Place queen solve(board, row + 1, solutions); // Recurse for the next row board[row][col] = '.'; // Backtrack: remove queen } } } private boolean isValid(char[][] board, int row, int col) { // Check current column for (int i = 0; i < row; i++) { if (board[i][col] == 'Q') { return false; } } // Check upper left diagonal for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') { return false; } } // Check upper right diagonal for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) { if (board[i][j] == 'Q') { return false; } } return true; } private List<String> constructBoard(char[][] board) { List<String> currentBoard = new ArrayList<>(); for (char[] row : board) { currentBoard.add(new String(row)); } return currentBoard; } }
e. Sliding Window
Concept: A technique used for problems that involve arrays or lists, where we need to find a sub-array or a sub-string that satisfies certain conditions. It works by maintaining a "window" (a contiguous range of elements) that slides over the data. The window size can be fixed or dynamic.
Use Cases: Finding maximum/minimum sum subarray of a given size, finding the longest substring with K distinct characters, finding anagrams.
Time Complexity: Often reduces O(N2) brute-force solutions to O(N) by avoiding redundant computations.
Java Example: Maximum Sum Subarray of Size K
Problem: Given an array of integers and an integer
k, find the maximum sum of any contiguous subarray of sizek.
class SlidingWindowExamples {
public int maxSubarraySum(int[] arr, int k) {
if (k > arr.length || k <= 0) {
throw new IllegalArgumentException("Invalid k or array length.");
}
int maxSum = 0;
int windowSum = 0;
// Calculate sum of the first window
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
maxSum = windowSum;
// Slide the window
for (int i = k; i < arr.length; i++) {
// Subtract the element going out of the window
// Add the element coming into the window
windowSum = windowSum - arr[i - k] + arr[i];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
}
f. Top K Element
Concept: Algorithms to find the 'k' largest or 'k' smallest elements in a collection. This often involves using a min-heap (for largest k elements) or a max-heap (for smallest k elements) to efficiently maintain the relevant elements.
Use Cases: Finding frequent elements, recommendation systems, leaderboards, percentile calculations.
Time Complexity: Generally O(NlogK) using a heap, where N is the total number of elements and K is the number of top elements. A naive sorting approach would be O(NlogN).
k, find the k largest elements.import java.util.PriorityQueue; // Java's built-in min-heap (PriorityQueue)
class TopKExamples {
public List<Integer> findKLargestElements(int[] nums, int k) {
if (k <= 0 || k > nums.length) {
return new ArrayList<>(); // Or throw exception
}
// Create a min-heap (PriorityQueue)
// The smallest element will be at the root (top)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.offer(num); // Add element to the heap
if (minHeap.size() > k) {
minHeap.poll(); // If heap size exceeds k, remove the smallest element (root)
}
}
// The heap now contains the k largest elements
// Convert to a List for the result
return new ArrayList<>(minHeap);
}
}
k largest elements seen so far. When a new element comes in, if it's larger than the smallest element in the heap (the root), we remove the smallest and add the new element. This ensures the heap always contains the k largest elements.Design patterns are reusable solutions to common problems in software design. They are not direct code but rather templates for how to solve certain recurring issues.
a. Creational Patterns
Purpose: Deal with object creation mechanisms, trying to create objects in a manner suitable to the situation. They reduce complexity and provide flexibility in creating objects.
1. Singleton Pattern
Concept: Ensures a class has only one instance and provides a global point of access to that instance.
Use Case: Logging, configuration managers, database connection pools.
Java Example:
// Lazy Initialization Singleton
class Logger {
private static Logger instance;
private Logger() {
// Private constructor to prevent instantiation from outside
System.out.println("Logger instance created.");
}
public static Logger getInstance() {
if (instance == null) { // Lazy initialization
synchronized (Logger.class) { // Thread-safe
if (instance == null) {
instance = new Logger();
}
}
}
return instance;
}
public void log(String message) {
System.out.println("Log: " + message);
}
}
// How to use:
// Logger logger1 = Logger.getInstance();
// Logger logger2 = Logger.getInstance();
// // logger1 and logger2 will refer to the same object
2. Factory Method Pattern
Concept: Defines an interface for creating an object, but lets subclasses decide which class to instantiate. Defers instantiation to subclasses.
Use Case: When a class cannot anticipate the class of objects it must create, or when a class wants its subclasses to specify the objects it creates.
Java Example:
/ Product Interface
interface Notification {
void notifyUser();
}
// Concrete Products
class EmailNotification implements Notification {
@Override
public void notifyUser() {
System.out.println("Sending an email notification.");
}
}
class SMSNotification implements Notification {
@Override
public void notifyUser() {
System.out.println("Sending an SMS notification.");
}
}
// Creator Abstract Class/Interface
abstract class NotificationFactory {
public abstract Notification createNotification();
}
// Concrete Creators
class EmailNotificationFactory extends NotificationFactory {
@Override
public Notification createNotification() {
return new EmailNotification();
}
}
class SMSNotificationFactory extends NotificationFactory {
@Override
public Notification createNotification() {
return new SMSNotification();
}
}
// How to use:
// NotificationFactory emailFactory = new EmailNotificationFactory();
// Notification email = emailFactory.createNotification();
// email.notifyUser();
//
// NotificationFactory smsFactory = new SMSNotificationFactory();
// Notification sms = smsFactory.createNotification();
// sms.notifyUser();
b. Structural Patterns
Purpose: Deal with class and object composition. They explain how to assemble objects and classes into larger structures, while keeping these structures flexible and efficient.
1. Adapter Pattern
Concept: Allows objects with incompatible interfaces to collaborate. It acts as a wrapper around an object, translating its interface into something that another object expects.
Use Case: Integrating existing components that have incompatible interfaces, allowing new components to work with old systems.
Java Example:
// Incompatible Interface (Old system)
class LegacyPrinter {
public void printText(String text) {
System.out.println("Legacy Printer: " + text);
}
}
// Desired Interface (New system)
interface ModernPrinter {
void print(String content);
}
// Adapter Class
class PrinterAdapter implements ModernPrinter {
private LegacyPrinter legacyPrinter;
public PrinterAdapter(LegacyPrinter legacyPrinter) {
this.legacyPrinter = legacyPrinter;
}
@Override
public void print(String content) {
// Adapt the call from ModernPrinter to LegacyPrinter
legacyPrinter.printText(content);
}
}
// How to use:
// LegacyPrinter oldPrinter = new LegacyPrinter();
// ModernPrinter adapter = new PrinterAdapter(oldPrinter);
// adapter.print("Hello from the new system!");
2. Decorator Pattern
Concept: Attaches additional responsibilities to an object dynamically. Decorators provide a flexible alternative to subclassing for extending functionality.
Use Case: Adding features to objects without changing their core structure, GUI toolkits (adding scrollbars, borders), stream operations (compression, encryption).
Java Example:
// Component Interface
interface Coffee {
String getDescription();
double getCost();
}
// Concrete Component
class SimpleCoffee implements Coffee {
@Override
public String getDescription() {
return "Simple Coffee";
}
@Override
public double getCost() {
return 2.0;
}
}
// Base Decorator
abstract class CoffeeDecorator implements Coffee {
protected Coffee decoratedCoffee;
public CoffeeDecorator(Coffee decoratedCoffee) {
this.decoratedCoffee = decoratedCoffee;
}
@Override
public String getDescription() {
return decoratedCoffee.getDescription();
}
@Override
public double getCost() {
return decoratedCoffee.getCost();
}
}
// Concrete Decorators
class MilkDecorator extends CoffeeDecorator {
public MilkDecorator(Coffee decoratedCoffee) {
super(decoratedCoffee);
}
@Override
public String getDescription() {
return super.getDescription() + ", Milk";
}
@Override
public double getCost() {
return super.getCost() + 0.5;
}
}
class SugarDecorator extends CoffeeDecorator {
public SugarDecorator(Coffee decoratedCoffee) {
super(decoratedCoffee);
}
@Override
public String getDescription() {
return super.getDescription() + ", Sugar";
}
@Override
public double getCost() {
return super.getCost() + 0.2;
}
}
// How to use:
// Coffee myCoffee = new SimpleCoffee();
// System.out.println(myCoffee.getDescription() + " Cost: " + myCoffee.getCost()); // Simple Coffee Cost: 2.0
//
// myCoffee = new MilkDecorator(myCoffee);
// System.out.println(myCoffee.getDescription() + " Cost: " + myCoffee.getCost()); // Simple Coffee, Milk Cost: 2.5
//
// myCoffee = new SugarDecorator(myCoffee);
// System.out.println(myCoffee.getDescription() + " Cost: " + myCoffee.getCost()); // Simple Coffee, Milk, Sugar Cost: 2.7
c. Behavioral Patterns
Purpose: Deal with algorithms and the assignment of responsibilities between objects. They describe how objects and classes interact and distribute responsibilities.
1. Observer Pattern
Concept: Defines a one-to-many dependency between objects so that when one object changes state, all its dependents are notified and updated automatically.
Use Case: Event handling systems, real-time data updates (stock prices), GUI components (buttons, text fields).
Java Example:
// Subject Interface (Observable)
interface Subject {
void addObserver(Observer o);
void removeObserver(Observer o);
void notifyObservers();
}
// Observer Interface
interface Observer {
void update(String message);
}
// Concrete Subject (e.g., a WeatherStation)
class WeatherStation implements Subject {
private List<Observer> observers;
private String weatherUpdate;
public WeatherStation() {
this.observers = new ArrayList<>();
}
@Override
public void addObserver(Observer o) {
observers.add(o);
}
@Override
public void removeObserver(Observer o) {
observers.remove(o);
}
@Override
public void notifyObservers() {
for (Observer observer : observers) {
observer.update(weatherUpdate);
}
}
public void setWeatherUpdate(String weatherUpdate) {
this.weatherUpdate = weatherUpdate;
System.out.println("\nWeather Station: New update - " + weatherUpdate);
notifyObservers();
}
}
// Concrete Observers
class PhoneDisplay implements Observer {
private String name;
public PhoneDisplay(String name) {
this.name = name;
}
@Override
public void update(String message) {
System.out.println(name + " (Phone Display): Received update - " + message);
}
}
class TVDisplay implements Observer {
private String name;
public TVDisplay(String name) {
this.name = name;
}
@Override
public void update(String message) {
System.out.println(name + " (TV Display): Received update - " + message);
}
}
// How to use:
// WeatherStation station = new WeatherStation();
// PhoneDisplay phone1 = new PhoneDisplay("My Phone");
// TVDisplay tv1 = new TVDisplay("Living Room TV");
//
// station.addObserver(phone1);
// station.addObserver(tv1);
//
// station.setWeatherUpdate("Sunny with a chance of clouds.");
// station.setWeatherUpdate("Heavy rain expected tonight.");
//
// station.removeObserver(phone1);
// station.setWeatherUpdate("Clear skies tomorrow!");
2. Strategy Pattern
Concept: Defines a family of algorithms, encapsulates each one, and makes them interchangeable. The strategy pattern lets the algorithm vary independently from clients that use it.
Use Case: When you need to select an algorithm at runtime, when you have many algorithms for the same task, or when an object's behavior needs to be configured.
Java Example:
// Strategy Interface
interface PaymentStrategy {
void pay(double amount);
}
// Concrete Strategies
class CreditCardPayment implements PaymentStrategy {
private String cardNumber;
private String name;
public CreditCardPayment(String cardNumber, String name) {
this.cardNumber = cardNumber;
this.name = name;
}
@Override
public void pay(double amount) {
System.out.println("Paying " + amount + " using Credit Card (Card No: " + cardNumber + ")");
}
}
class PayPalPayment implements PaymentStrategy {
private String email;
public PayPalPayment(String email) {
this.email = email;
}
@Override
public void pay(double amount) {
System.out.println("Paying " + amount + " using PayPal (Email: " + email + ")");
}
}
// Context Class
class ShoppingCart {
private PaymentStrategy paymentStrategy;
public void setPaymentStrategy(PaymentStrategy paymentStrategy) {
this.paymentStrategy = paymentStrategy;
}
public void checkout(double amount) {
if (paymentStrategy == null) {
System.out.println("Please select a payment strategy.");
return;
}
paymentStrategy.pay(amount);
}
}
// How to use:
// ShoppingCart cart = new ShoppingCart();
//
// // Pay with Credit Card
// cart.setPaymentStrategy(new CreditCardPayment("1234-5678-9012-3456", "John Doe"));
// cart.checkout(100.0);
//
// // Pay with PayPal
// cart.setPaymentStrategy(new PayPalPayment("john.doe@example.com"));
// cart.checkout(50.0);