DSA Interview Prep: Hinglish Edition

Definition: Array ek contiguous memory locations ka collection hota hai, jahan hum same type ke items store karte hain. Iska size generally fixed hota hai creation ke time pe.

Where & Why Used (Kahan aur Kyun): Jab aapko pata ho ki kitne items store karne hain aur aapko fast access chahiye by index (position). Jaise ki students ke marks, ya ek list of names.

Real-life Analogy (Asal Zindagi ki Misaal): Ek egg tray socho. Usmein fixed number of slots (e.g., 12) hote hain, aur har slot mein ek anda (same type item) rakha jaata hai. Aap direct kisi bhi slot (index) se anda utha sakte ho. Ya fir ek kitaabon ki shelf jisme har kitaab ek specific position par rakhi hai.

Pros: Fast access (O(1)) if you know the index. Cache friendly.

Cons: Fixed size. Insertion/deletion beech mein costly (O(n)) ho sakta hai kyunki elements shift karne padte hain.

let fruits = ["Apple", "Banana", "Orange"];
console.log(fruits[0]); // Output: Apple (Accessing by index)

fruits.push("Mango"); // Adding at the end (efficient if space available)
console.log(fruits);  // Output: ["Apple", "Banana", "Orange", "Mango"]

// Insert "Grapes" at index 1 (can be costly)
fruits.splice(1, 0, "Grapes");
console.log(fruits); // Output: ["Apple", "Grapes", "Banana", "Orange", "Mango"]
                    

Definition: Linked List ek linear data structure hai jahan elements (nodes) sequence mein toh hote hain, par memory mein kahin bhi scattered ho sakte hain. Har node mein data aur next node ka pointer/reference hota hai.

Where & Why Used: Jab dynamic size chahiye (elements easily add/remove kar sakein) aur random access ki zaroorat na ho. Insertion/deletion (especially at ends) arrays se efficient ho sakta hai (O(1) if you have pointer to previous node for deletion, or pointer to tail for insertion at end).

Real-life Analogy: Ek treasure hunt socho. Har clue (node) aapko batata hai ki agla clue (next node) kahan milega. Ya fir train ke coaches, har coach (node) agle coach se juda hota hai.

Types: Singly Linked List (sirf next pointer), Doubly Linked List (next aur previous pointers), Circular Linked List (last node points to first).

Pros: Dynamic size. Efficient insertion/deletion at ends (and middle if pointer is known).

Cons: Random access nahi hota (O(n) to reach an element). Extra memory for pointers.

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }

    append(data) { // Add to end
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    printList() {
        let current = this.head;
        let listStr = "";
        while (current) {
            listStr += current.data + " -> ";
            current = current.next;
        }
        console.log(listStr + "null");
    }
}

let list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList(); // Output: 10 -> 20 -> 30 -> null
                    

Definition: Recursion ek programming technique hai jahan ek function khud ko call karta hai (directly ya indirectly) ek chote version of the problem ko solve karne ke liye. Har recursive call problem ko simple banata hai jab tak woh base case tak na pahunch jaaye.

Where & Why Used: Problems jo naturally recursive structure follow karti hain, jaise tree traversals, factorial, Fibonacci series, divide and conquer algorithms (Merge Sort, Quick Sort). Code often elegant aur problem definition ke close hota hai.

Real-life Analogy: Russian nesting dolls (Matryoshka dolls). Har doll ke andar ek choti doll hoti hai, jab tak sabse choti doll na mil jaaye (base case). Ya fir ek set of mirrors facing each other, creating infinite reflections (agar base case na ho!).

Key Components: 1. Base Case: Woh condition jahan recursion ruk jaata hai. Bahut important hai infinite loop se bachne ke liye. 2. Recursive Step: Function khud ko call karta hai, problem ko chota karke.

Pros: Elegant solutions for certain problems. Complex problems ko break down karna aasan.

Cons: Can be less efficient due to function call overhead. Stack overflow ka risk agar recursion bahut deep ho. Debugging thoda tricky ho sakta hai.

function factorial(n) {
    // Base Case
    if (n === 0 || n === 1) {
        return 1;
    }
    // Recursive Step
    return n * factorial(n - 1);
}

console.log(factorial(5)); // Output: 120 (5 * 4 * 3 * 2 * 1)
                    

Definition: Time Complexity batata hai ki ek algorithm ko run hone mein kitna time lagega as a function of input size (n). Hum ise usually Big O Notation mein express karte hain. Yeh actual time (seconds/milliseconds) nahi batata, balki growth rate batata hai jab input size badhta hai.

Why Important: Efficient algorithms choose karne ke liye. Ek algorithm jo chhote input pe fast hai, woh bade input pe bahut slow ho sakta hai. Time complexity se hum predict kar sakte hain.

Common Functions (Growth Rates):

• O(1) - Constant: Execution time same rehta hai, input size kitna bhi ho. Example: Array element access by index (`arr[5]`).
• O(log n) - Logarithmic: Execution time input size ke logarithm ke proportion mein badhta hai. Bahut efficient. Example: Binary Search.
• O(n) - Linear: Execution time input size ke directly proportional badhta hai. Example: Traversing an array/list. Finding an element in unsorted array.
• O(n log n) - Linearithmic: Linear aur Logarithmic ka combination. Efficient sorting algorithms. Example: Merge Sort, Heap Sort.
• O(n²) - Quadratic: Execution time input size ke square ke proportion mein badhta hai. Example: Nested loops iterating over same data (e.g., Bubble Sort, Insertion Sort worst case).
• O(n³) - Cubic: Three nested loops. Example: Some matrix multiplication algorithms.
• O(2ⁿ) - Exponential: Execution time doubles with each addition to input. Bahut slow for larger inputs. Example: Recursive Fibonacci without memoization, Traveling Salesman Problem (brute force).
• O(n!) - Factorial: Even slower. Example: Permutations of a string.

Notations:

• Big O (O): Worst-case (Upper bound). "Algorithm will take AT MOST this much time."
• Big Omega (Ω): Best-case (Lower bound). "Algorithm will take AT LEAST this much time."
• Big Theta (Θ): Average-case or when best and worst are same. "Algorithm will take ABOUT this much time."

// O(n) - Linear
function findElement(arr, target) {
    for (let i = 0; i < arr.length; i++) { // Loop runs 'n' times
        if (arr[i] === target) {
            return i;
        }
    }
    return -1;
}

// O(n^2) - Quadratic
function hasDuplicates(arr) {
    for (let i = 0; i < arr.length; i++) {       // Outer loop: n times
        for (let j = i + 1; j < arr.length; j++) { // Inner loop: roughly n times
            if (arr[i] === arr[j]) {
                return true;
            }
        }
    }
    return false;
}
                    

Definition: Stack ek linear data structure hai jo LIFO (Last-In, First-Out) principle follow karta hai. Matlab, jo item sabse aakhir mein add hua, woh sabse pehle remove hoga.

Operations:

• Push: Element ko stack ke top pe add karna.
• Pop: Element ko stack ke top se remove karna.
• Peek/Top: Topmost element ko dekhna bina remove kiye.
• isEmpty: Check karna ki stack khali hai ya nahi.

Where & Why Used: Function calls (call stack), undo/redo operations in software, expression evaluation (infix to postfix), backtracking algorithms (like maze solving).

Real-life Analogy: Plates ka stack. Aap sabse upar wali plate hi uthate ho (pop), aur nayi plate bhi sabse upar rakhte ho (push). Ya browser ka back button history.

Implementation: Can be implemented using Arrays or Linked Lists.

class Stack {
    constructor() {
        this.items = [];
    }

    push(element) {
        this.items.push(element); // Array's push adds to end (our 'top')
    }

    pop() {
        if (this.isEmpty()) {
            return "Underflow - Stack is empty";
        }
        return this.items.pop(); // Array's pop removes from end
    }

    peek() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.items[this.items.length - 1];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    printStack() {
        console.log(this.items.join(" <- "));
    }
}

let myStack = new Stack();
myStack.push(10);
myStack.push(20);
myStack.push(30);
myStack.printStack(); // Output: 10 <- 20 <- 30 (30 is top)
console.log("Popped:", myStack.pop()); // Popped: 30
console.log("Peek:", myStack.peek());   // Peek: 20
myStack.printStack(); // Output: 10 <- 20
                    

Definition: Queue bhi ek linear data structure hai, lekin yeh FIFO (First-In, First-Out) principle follow karta hai. Matlab, jo item sabse pehle add hua, woh sabse pehle remove hoga.

Operations:

• Enqueue (or Add): Element ko queue ke rear (end) mein add karna.
• Dequeue (or Remove): Element ko queue ke front (start) se remove karna.
• Peek/Front: Frontmost element ko dekhna bina remove kiye.
• isEmpty: Check karna ki queue khali hai ya nahi.

Where & Why Used: Printer queues, CPU task scheduling, Breadth-First Search (BFS) in graphs, call center phone systems, message queues in distributed systems.

Real-life Analogy: Cinema hall ki ticket line. Jo log pehle line mein lagte hain, unko ticket pehle milti hai. Log line ke peeche (rear) judte hain aur aage (front) se nikalte hain.

Implementation: Can be implemented using Arrays (circular array is efficient) or Linked Lists.

class Queue {
    constructor() {
        this.items = [];
    }

    enqueue(element) {
        this.items.push(element); // Add to end (rear)
    }

    dequeue() {
        if (this.isEmpty()) {
            return "Underflow - Queue is empty";
        }
        return this.items.shift(); // Remove from beginning (front)
    }

    front() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items[0];
    }

    isEmpty() {
        return this.items.length === 0;
    }

    printQueue() {
        console.log("Front -> " + this.items.join(" -> ") + " <- Rear");
    }
}

let myQueue = new Queue();
myQueue.enqueue(10);
myQueue.enqueue(20);
myQueue.enqueue(30);
myQueue.printQueue(); // Output: Front -> 10 -> 20 -> 30 <- Rear
console.log("Dequeued:", myQueue.dequeue()); // Dequeued: 10
console.log("Front:", myQueue.front());   // Front: 20
myQueue.printQueue(); // Output: Front -> 20 -> 30 <- Rear
                    

Definition: Deque (pronounced "deck"), ya Double-Ended Queue, ek generalized version hai queue ka. Ismein elements dono ends (front aur rear) se add (enqueue) aur remove (dequeue) kiye ja sakte hain.

Operations:

• addFront: Element ko front mein add karna.
• addRear: Element ko rear mein add karna.
• removeFront: Element ko front se remove karna.
• removeRear: Element ko rear se remove karna.
• getFront: Front element dekhna.
• getRear: Rear element dekhna.
• isEmpty: Check karna ki deque khali hai ya nahi.

Where & Why Used: Palindrome checker, sliding window problems, undo/redo (more complex scenarios), task scheduling where priority tasks can be added to front.

Real-life Analogy: Ek deck of cards jahan se aap dono taraf se cards nikal sakte ho ya daal sakte ho. Ya fir ek line jahan log dono taraf se enter aur exit kar sakte hain (though less common).

Implementation: Usually implemented using Doubly Linked Lists or dynamic arrays with careful management of front/rear pointers.

class Deque {
    constructor() {
        this.items = [];
    }
    addFront(element) { this.items.unshift(element); } // Add to beginning
    addRear(element) { this.items.push(element); }    // Add to end
    removeFront() { return this.isEmpty() ? "Empty" : this.items.shift(); } // Remove from beginning
    removeRear() { return this.isEmpty() ? "Empty" : this.items.pop(); }    // Remove from end
    getFront() { return this.isEmpty() ? "Empty" : this.items[0]; }
    getRear() { return this.isEmpty() ? "Empty" : this.items[this.items.length - 1]; }
    isEmpty() { return this.items.length === 0; }
    printDeque() { console.log("Front <-> " + this.items.join(" <-> ") + " <-> Rear"); }
}

let myDeque = new Deque();
myDeque.addRear(20);   // [20]
myDeque.addFront(10);  // [10, 20]
myDeque.addRear(30);   // [10, 20, 30]
myDeque.printDeque();  // Front <-> 10 <-> 20 <-> 30 <-> Rear
console.log("Removed Rear:", myDeque.removeRear()); // 30
console.log("Removed Front:", myDeque.removeFront()); // 10
myDeque.printDeque(); // Front <-> 20 <-> Rear
                    

Definition: Tree ek non-linear, hierarchical data structure hai jo nodes se bana hota hai. Topmost node ko root kehte hain. Har node ka data aur uske children (child nodes) ke references ho sakte hain. Jin nodes ke koi children nahi hote, unhe leaf nodes kehte hain.

Terminology:

• Root: The topmost node.
• Parent: A node that has child nodes.
• Child: A node that has a parent node.
• Sibling: Nodes with the same parent.
• Leaf Node: A node with no children.
• Internal Node: A node with at least one child.
• Edge: Link between a parent and a child.
• Path: Sequence of nodes and edges from one node to another.
• Height of Tree: Length of the longest path from root to a leaf.
• Depth of a Node: Length of the path from root to that node.

Where & Why Used: Representing hierarchical data like file systems, organization charts, XML/HTML DOM structure, decision trees in AI, routing algorithms. Binary Search Trees (BSTs) are used for efficient searching and sorting.

Real-life Analogy: Family tree, company's organizational structure, file explorer in your computer.

Types: Binary Tree (max 2 children per node), Binary Search Tree (BST), AVL Tree, Red-Black Tree, N-ary Tree (any number of children), etc.

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;  // For Binary Tree, left child
        this.right = null; // For Binary Tree, right child
    }
}

// Example: Creating a simple binary tree
let root = new TreeNode(10);
root.left = new TreeNode(5);
root.right = new TreeNode(15);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(7);

//      10
//     /  \
//    5    15
//   / \
//  3   7
console.log("Root:", root.data); // Root: 10
console.log("Root's Left Child:", root.left.data); // Root's Left Child: 5
                    

Definition: Binary Search Tree (BST) ek special type ka Binary Tree hai jismein har node ke liye yeh properties hold karti hain:

• Left child ka value parent node se chota hota hai.
• Right child ka value parent node se bada hota hai.
• Left aur Right subtrees bhi BSTs hote hain.

Where & Why Used: Efficient searching (average O(log n)), insertion (average O(log n)), deletion (average O(log n)). Sorted order traversal (In-order traversal) deta hai. Used in dictionaries, symbol tables, set implementations.

Real-life Analogy: Ek dictionary. Aap ek word search karte ho, agar current word se chota hai toh pehle ke pages mein dekhte ho (left), bada hai toh baad ke pages mein (right).

Worst Case: Agar tree skewed (ek hi taraf saare nodes, like a linked list) ho jaaye, toh operations O(n) ho jaate hain. Isiliye self-balancing BSTs (like AVL, Red-Black) use hote hain.

// TreeNode class is same as above

class BST {
    constructor() {
        this.root = null;
    }

    insert(data) {
        const newNode = new TreeNode(data);
        if (!this.root) {
            this.root = newNode;
            return;
        }
        this._insertNode(this.root, newNode);
    }

    _insertNode(node, newNode) {
        if (newNode.data < node.data) {
            if (!node.left) {
                node.left = newNode;
            } else {
                this._insertNode(node.left, newNode);
            }
        } else {
            if (!node.right) {
                node.right = newNode;
            } else {
                this._insertNode(node.right, newNode);
            }
        }
    }

    search(data) {
        return this._searchNode(this.root, data);
    }

    _searchNode(node, data) {
        if (!node) return null; // Not found
        if (data < node.data) return this._searchNode(node.left, data);
        else if (data > node.data) return this._searchNode(node.right, data);
        else return node; // Found
    }
}

let bst = new BST();
bst.insert(50); bst.insert(30); bst.insert(70);
bst.insert(20); bst.insert(40); bst.insert(60); bst.insert(80);

//         50
//       /    \
//     30      70
//    /  \    /  \
//  20   40  60   80

console.log("Search for 40:", bst.search(40) ? "Found" : "Not Found"); // Found
console.log("Search for 90:", bst.search(90) ? "Found" : "Not Found"); // Not Found
                    

Definition: AVL Tree ek self-balancing Binary Search Tree hai. "AVL" Adelson-Velsky aur Landis ke naam se aata hai, jinhone ise invent kiya. Har node mein ek "balance factor" store hota hai (height of right subtree - height of left subtree). Yeh factor -1, 0, ya 1 hona chahiye.

Why Self-Balancing? Normal BSTs worst-case mein O(n) performance de sakte hain (jab woh skewed ho jaate hain). AVL trees ensure karte hain ki tree hamesha balanced rahe, isliye search, insert, delete operations O(log n) time mein guarantee hote hain.

How it Works: Jab bhi koi element insert ya delete hota hai, tree check karta hai ki balance factor disturb toh nahi hua. Agar hua (value -2 ya +2 ho gayi), toh rotations perform kiye jaate hain tree ko rebalance karne ke liye.

Where & Why Used: Situations jahan frequent lookups (search) ki zaroorat ho aur O(log n) worst-case performance guarantee chahiye. Databases, dictionaries, scenarios where insertions/deletions kam hain compared to lookups (kyunki rotations thoda overhead add karte hain).

Pros: Guaranteed O(log n) for all operations. Faster lookups than Red-Black trees (generally stricter balance).

Cons: Stricter balancing leads to more frequent rotations during insertion/deletion compared to Red-Black trees, so insertions/deletions can be slightly slower. Implementation complex hai.

// TreeNode for AVL would also store height and balance factor
class AVLNode extends TreeNode { // Assuming TreeNode is defined
    constructor(data) {
        super(data);
        this.height = 1; // Height of this node
    }
}

// Key operations in AVL:
// 1. getHeight(node)
// 2. getBalanceFactor(node)
// 3. rightRotate(yNode)
// 4. leftRotate(xNode)
// 5. insertNode(node, data) - with rebalancing logic

// Example of a rotation (Conceptual):
// If a node Z becomes unbalanced due to insertion in left child (Y) 
// and left-left grandchild (X) (LL case):
//
//        Z (unbalanced, BF= -2)
//       /
//      Y   (BF= -1 or 0)
//     /
//    X
//
// After Right Rotation on Z:
//
//        Y
//       / \
//      X   Z

function rightRotate(z) {
    let y = z.left;
    let T3 = y.right;

    // Perform rotation
    y.right = z;
    z.left = T3;

    // Update heights (order matters)
    z.height = Math.max(getHeight(z.left), getHeight(z.right)) + 1;
    y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;

    return y; // New root of this subtree
}
// getHeight and other functions would be needed.
                    

Definition: Heap ek special tree-based data structure hai jo "Heap Property" satisfy karta hai. Heaps are usually complete binary trees.

Heap Property:

• Min-Heap: Har parent node ka value uske children se chota ya barabar hota hai. Root node mein smallest element hota hai.
• Max-Heap: Har parent node ka value uske children se bada ya barabar hota hai. Root node mein largest element hota hai.

Where & Why Used: Priority Queues (heap is the most common way to implement them), Heap Sort algorithm, finding kth smallest/largest element, graph algorithms like Dijkstra's and Prim's.

Real-life Analogy (for Min-Heap): A company's hierarchy where the CEO (root) has the highest authority (or lowest 'priority number' if we think of tasks). For a Max-Heap, imagine a tournament bracket where the winner (largest value) moves up.

Implementation: Often implemented using arrays for efficiency due to the complete binary tree structure. Parent-child relationships can be found using array indices:

• Parent of `arr[i]` is `arr[Math.floor((i-1)/2)]`
• Left child of `arr[i]` is `arr[2*i + 1]`
• Right child of `arr[i]` is `arr[2*i + 2]`

Operations:

• Insert (O(log n)): Add element at end, then "heapify-up" (bubble up) to maintain heap property.
• DeleteMin/DeleteMax (O(log n)): Remove root, replace with last element, then "heapify-down" (sift down) to maintain heap property.
• GetMin/GetMax (O(1)): Root element.

class MinHeap {
    constructor() {
        this.heap = [];
    }

    insert(value) {
        this.heap.push(value);
        this._heapifyUp(this.heap.length - 1);
    }

    _heapifyUp(index) {
        let parentIndex = Math.floor((index - 1) / 2);
        while (index > 0 && this.heap[index] < this.heap[parentIndex]) {
            // Swap
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
            parentIndex = Math.floor((index - 1) / 2);
        }
    }
    
    extractMin() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop(); // Move last element to root
        this._heapifyDown(0);
        return min;
    }

    _heapifyDown(index) {
        let smallest = index;
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        const length = this.heap.length;

        if (leftChildIndex < length && this.heap[leftChildIndex] < this.heap[smallest]) {
            smallest = leftChildIndex;
        }
        if (rightChildIndex < length && this.heap[rightChildIndex] < this.heap[smallest]) {
            smallest = rightChildIndex;
        }

        if (smallest !== index) {
            [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
            this._heapifyDown(smallest);
        }
    }

    peek() { return this.heap.length > 0 ? this.heap[0] : null; }
}

let minHeap = new MinHeap();
minHeap.insert(10); minHeap.insert(5); minHeap.insert(20); minHeap.insert(2);
console.log("Heap array:", minHeap.heap); // Example: [2, 5, 20, 10] or similar after heapify
console.log("Min element:", minHeap.peek()); // Should be 2
console.log("Extracted Min:", minHeap.extractMin()); // 2
console.log("New Min element:", minHeap.peek()); // Should be 5
                    

Definition: Divide and Conquer ek powerful algorithmic paradigm hai. Ismein problem ko chote-chote sub-problems mein toda jaata hai, un sub-problems ko recursively solve kiya jaata hai, aur fir unke solutions ko combine karke original problem ka solution banaya jaata hai.

Steps:

1. Divide: Problem ko smaller, independent sub-problems mein break karo.
2. Conquer: Sub-problems ko recursively solve karo. Agar sub-problem bahut chota ho, toh use directly solve karo (base case).
3. Combine: Sub-problems ke solutions ko combine karke original problem ka solution banao.

Where & Why Used: Merge Sort, Quick Sort, Binary Search, Strassen's Matrix Multiplication, Closest Pair of Points. Yeh complex problems ko manageable parts mein break karne mein madad karta hai aur often efficient solutions deta hai.

Real-life Analogy: Ek badi task (jaise "clean the house") ko chote tasks mein divide karna (clean bedroom, clean kitchen, clean bathroom). Har choti task ko individually complete karna (conquer), aur fir saari tasks complete hone par poora ghar saaf ho jaata hai (combine).

Analyzing D&C Algorithms (Recurrence Relations): Recurrence relations use hote hain D&C algorithms ki time complexity analyze karne ke liye. For example, `T(n) = aT(n/b) + f(n)` where:

• `T(n)`: Time to solve problem of size `n`.
• `a`: Number of sub-problems.
• `n/b`: Size of each sub-problem.
• `f(n)`: Cost of dividing and combining.

Methods to Solve Recurrence Relations:

• Substitution Method: Guess a solution and prove it by induction. Andaza lagao aur mathematical induction se prove karo.
• Recursion Tree Method: Recursion ko tree ke form mein visualize karo. Har level ka cost calculate karo aur sum karo.
• Master Theorem: Ek direct formula hai `T(n) = aT(n/b) + f(n)` type ke recurrences ko solve karne ka, kuch specific conditions mein.
  • Case 1: If `f(n) = O(n<sup>log<sub>b</sub>a - ε</sup>)` for some `ε > 0`, then `T(n) = Θ(n<sup>log<sub>b</sub>a</sup>)`.
  • Case 2: If `f(n) = Θ(n<sup>log<sub>b</sub>a</sup> * (log n)<sup>k</sup>)` for `k >= 0`, then `T(n) = Θ(n<sup>log<sub>b</sub>a</sup> * (log n)<sup>k+1</sup>)`. (If k=0, then `T(n) = Θ(n<sup>log<sub>b</sub>a</sup> log n)`)
  • Case 3: If `f(n) = Ω(n<sup>log<sub>b</sub>a + ε</sup>)` for some `ε > 0`, AND if `a * f(n/b) ≤ c * f(n)` for some constant `c < 1` and large `n` (regularity condition), then `T(n) = Θ(f(n))`.

function mergeSort(arr) {
    if (arr.length <= 1) { // Base case
        return arr;
    }

    // Divide
    const middle = Math.floor(arr.length / 2);
    const leftHalf = arr.slice(0, middle);
    const rightHalf = arr.slice(middle);

    // Conquer (Recursive calls)
    const sortedLeft = mergeSort(leftHalf);
    const sortedRight = mergeSort(rightHalf);

    // Combine (Merge sorted halves)
    return merge(sortedLeft, sortedRight);
}

function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

let unsortedArray = [38, 27, 43, 3, 9, 82, 10];
console.log("Sorted:", mergeSort(unsortedArray.slice())); // Output: Sorted: [3, 9, 10, 27, 38, 43, 82]
// Recurrence for Merge Sort: T(n) = 2T(n/2) + O(n). Master Theorem Case 2 (k=0) => T(n) = Θ(n log n)
                    

Answer: Array mein elements contiguous memory mein hote hain. Linked List mein nodes scattered hote hain, pointers se connected.
Cache Locality: Arrays have better cache locality. Jab aap ek array element access karte ho, toh chances hain ki आसपास ke elements bhi CPU cache mein load ho jaayein (spatial locality). Isse subsequent accesses faster hote hain. Linked List nodes memory mein kahin bhi ho sakte hain, toh har node access pe cache miss ka chance zyada hota hai.
Scenario: Agar aapko data pe iterate karna hai frequently (e.g., summing all elements), array cache locality ke kaaran faster ho sakta hai, even if theoretical complexities same lagein. Lekin agar frequent insertions/deletions in the middle hain, toh Linked List shifting overhead se bacha lega.

Answer:
1. Array-based Stack/Queue:

• Stack Push/Pop (at end): O(1) average (amortized). Agar array full ho jaaye toh resize karna O(n) lag sakta hai, but yeh infrequent hota hai.
• Queue Enqueue (at end using array push): O(1) amortized.
• Queue Dequeue (from beginning using array shift): O(n) kyunki saare elements ko ek position left shift karna padta hai. This is inefficient.
  To make array-based queue efficient (O(1) dequeue): Use a circular array (or two stacks).

• Stack Push (add to head): O(1).
• Stack Pop (remove from head): O(1).
• Queue Enqueue (add to tail): O(1) if you maintain a tail pointer.
• Queue Dequeue (remove from head): O(1).

Answer: Recursive solutions aksar elegant aur problem ke mathematical formulation ke close hote hain. Lekin, har recursive call function call stack mein ek naya frame add karta hai.
Stack Overflow: Agar recursion bahut deep chali jaaye (e.g., factorial of a very large number, or traversing a very deep, unbalanced tree), toh call stack ki memory exhaust ho sakti hai, leading to a stack overflow error.
Iterative Solution: Iterative solutions loops (for, while) use karte hain aur generally stack space ka issue nahi hota (ya kam hota hai). Woh explicit stack/queue data structure use kar sakte hain recursion ko simulate karne ke liye (e.g., DFS using explicit stack, BFS using explicit queue).
Tail Recursion: Kuch languages/compilers tail call optimization (TCO) support karte hain. Agar function tail-recursive hai, toh compiler use iterative code mein convert kar sakta hai, stack overflow se bachate hue. JavaScript engines historically had limited TCO support, but it's improving in some strict mode contexts or specific engines. Generally, JS mein deep recursion se bachna better hai.

Answer:
Min-Heap for k smallest:

1. Ek Max-Heap banao size 'k' ka.
2. Pehle 'k' elements ko Max-Heap mein daalo. (k log k)
3. Baaki (n-k) elements ke liye:
   • Agar current element Max-Heap ke root (largest among k) se chhota hai:
     • Root ko remove karo (extractMax). (log k)
     • Current element ko heap mein insert karo. (log k)

Answer:
BST (Average O(log n), Worst O(n)):

• Pros: In-order traversal gives sorted data. Good for range queries. Simpler to implement than balanced trees.
• Cons: Performance degrades to O(n) if tree becomes skewed (e.g., inserting sorted data).

• Pros: Extremely fast average case lookups.
• Cons: No ordering of elements. Range queries inefficient (need to iterate all). High collision rate can degrade performance to O(n) (like a linked list for each bucket). Requires good hash function and collision resolution strategy. Memory overhead for table.

• Hash Table: Jab sirf fast key-value lookup chahiye aur order/range queries important nahi hain. This is the default choice for most "dictionary" type needs.
• BST: Jab sorted order, range queries (`find all elements between X and Y`), or finding successor/predecessor important ho. If worst-case O(log n) is critical, use a balanced BST (AVL, Red-Black).

Answer: Yes, a binary tree can be a heap, but not all binary trees are heaps. A heap must satisfy two properties:
1. Shape Property: It must be a complete binary tree. This means all levels are completely filled except possibly the last level, which has all its nodes as far left as possible.
2. Heap Property: For a Min-Heap, every node's value must be less than or equal to its children's values. For a Max-Heap, every node's value must be greater than or equal to its children's values.
A general binary tree (like a BST) might not be complete (e.g., a skewed tree). Even if it is complete, it might not satisfy the heap property (e.g., a complete BST is not necessarily a heap unless all elements are same or structured very specifically).
So, a heap IS a specific type of binary tree.

Answer:
Master Theorem: `T(n) = aT(n/b) + f(n)`
Here, `a=2` (two subproblems), `b=2` (size of subproblem is n/2), `f(n) = n` (cost of merging).
Calculate `n<sup>log<sub>b</sub>a</sup> = n<sup>log<sub>2</sub>2</sup> = n<sup>1</sup> = n`.
Compare `f(n)` with `n<sup>log<sub>b</sub>a</sup>`. Here, `f(n) = n` and `n<sup>log<sub>b</sub>a</sup> = n`.
This fits Case 2 of the Master Theorem where `f(n) = Θ(n<sup>log<sub>b</sub>a</sup> * (log n)<sup>k</sup>)` with `k=0`.
So, `T(n) = Θ(n<sup>log<sub>b</sub>a</sup> * (log n)<sup>k+1</sup>) = Θ(n * (log n)<sup>0+1</sup>) = Θ(n log n)`.
Merge Sort ki time complexity `Θ(n log n)` hoti hai.

Answer:
1. Use a Hash Set (or Hash Map):

• Iterate through the linked list. (O(n))
• For each node, check if its value (or a unique identifier if nodes can have same value but are different objects) is in the hash set.
  • If yes, you've found the start of the cycle. The current node is where the cycle begins, or if you are storing `node.next`, then `node.next` is the start. (O(1) average for hash set lookup)
  • If no, add the node to the hash set. (O(1) average for hash set insertion)

• Use two pointers: `slow` (moves 1 step) and `fast` (moves 2 steps).
• If they meet, there's a cycle.
• To find the start of the cycle: Reset `slow` to `head`. Keep `fast` at the meeting point. Now move both `slow` and `fast` one step at a time. The point where they meet again is the start of the cycle.

Answer:
Graph Representation:

• Adjacency Matrix: Ek 2D array `adj[V][V]` (V = number of vertices). `adj[i][j] = 1` (or weight) agar `i` se `j` tak edge hai, warna 0.
  • Pros: Check karna ki edge hai ya nahi O(1) mein. Adding/removing edge O(1).
  • Cons: Space O(V²), jo sparse graphs (kam edges) ke liye inefficient hai. Iterating over all neighbors of a vertex takes O(V).
• Adjacency List: Ek array of linked lists (ya dynamic arrays). `adj[i]` stores a list of vertices jo `i` se connected hain.
  • Pros: Space efficient for sparse graphs O(V+E) (E = number of edges). Iterating over neighbors of a vertex is O(degree of vertex).
  • Cons: Check karna ki edge hai ya nahi O(degree of vertex) worst case.

Answer:
BFS (Breadth-First Search):

• Uses a Queue.
• Explores neighbors level by level. Pehle starting node ke saare direct neighbors, fir unke unvisited neighbors, and so on.
• Use Cases: Finding shortest path in unweighted graphs. Web crawlers (level by level). Social network analysis (finding people within K connections). Testing if a graph is bipartite.

• Uses a Stack (implicitly via recursion, or explicitly).
• Explores as far as possible along each branch before backtracking. Ek path ko end tak explore karta hai, fir wapas aake dusra path.
• Use Cases: Detecting cycles in a graph. Topological sorting. Solving mazes. Finding connected components. Path finding (not necessarily shortest).

Answer: A Binary Tree can be traversed in several ways:
Depth-First Traversals (Stack/Recursion):

• In-order (Left, Root, Right): BST mein sorted order deta hai.
  function inOrder(node) { if(node) { inOrder(node.left); console.log(node.data); inOrder(node.right); } }
• Pre-order (Root, Left, Right): Useful for copying trees, or prefix expressions (Polish notation).
  function preOrder(node) { if(node) { console.log(node.data); preOrder(node.left); preOrder(node.right); } }
• Post-order (Left, Right, Root): Useful for deleting nodes in a tree (children delete hote hain pehle), or postfix expressions (Reverse Polish notation).
  function postOrder(node) { if(node) { postOrder(node.left); postOrder(node.right); console.log(node.data); } }

• Level-order Traversal: Nodes ko level by level visit karta hai, from left to right at each level.
  function levelOrder(root) { if(!root) return; let queue = [root]; while(queue.length > 0) { let node = queue.shift(); console.log(node.data); if(node.left) queue.push(node.left); if(node.right) queue.push(node.right); } }

Answer:
1. Sorting + Two Pointers:

• Sort the array. (O(n log n))
• Use two pointers, `left` starting at index 0, `right` at `n-1`.
• Calculate `sum = arr[left] + arr[right]`.
  • If `sum == target`, you found a pair. Increment `left`, decrement `right`.
  • If `sum < target`, increment `left` (to increase sum).
  • If `sum > target`, decrement `right` (to decrease sum).
• Repeat until `left >= right`. (O(n) for pointer traversal)

• Initialize an empty hash set `seen_numbers`.
• Iterate through the array. For each element `num`: (O(n))
  • Calculate `complement = target - num`.
  • If `complement` is in `seen_numbers`, you found a pair (`num`, `complement`). (O(1) average lookup)
  • Add `num` to `seen_numbers`. (O(1) average insertion)

Answer: Dynamic Programming (DP) aur Divide and Conquer (D&C) dono hi problems ko subproblems mein todte hain.
Key Difference: Overlapping Subproblems.

• Divide and Conquer: Subproblems are typically independent. Merge Sort mein left half sort karna right half sort karne se independent hai. Solutions are computed independently and then combined.
• Dynamic Programming: Subproblems often overlap. Fibonacci sequence `fib(n) = fib(n-1) + fib(n-2)`. `fib(n-1)` aur `fib(n-2)` dono `fib(n-3)` ko calculate karenge. DP stores the results of subproblems (memoization or tabulation) to avoid recomputing them.

Answer:
AVL Trees:

• Stricter Balance: Balance factor (-1, 0, 1) is strictly maintained. Height difference between left and right subtrees of any node is at most 1.
• Rotations: Can require more rotations on insertion/deletion to maintain the strict balance.
• Search: Potentially faster searches because the tree is more rigidly balanced ( shallower on average).
• Complexity: Slightly more complex to implement rotations (LL, RR, LR, RL).

• Relaxed Balance: Uses properties like "red" and "black" nodes and rules about their arrangement to ensure path from root to any leaf doesn't vary by more than a factor of 2. This ensures O(log n) but is less strict than AVL.
  Key RB Properties: 1. Every node is R or B. 2. Root is B. 3. All leaves (NIL) are B. 4. If a node is R, its children are B. 5. Every path from a node to its descendant NIL nodes has same number of B nodes.
• Rotations & Recoloring: Fewer rotations on average than AVL, but might involve color changes. Insertions/deletions can be faster.
• Search: Slightly slower searches on average than AVL as tree can be a bit deeper.
• Complexity: Also complex, different set of rules for balancing.

Answer: Space complexity algorithm ke execution ke dauraan use hone wali total memory space ko measure karta hai, as a function of input size. Ismein do parts hote hain:
1. Input Space: Input data ko store karne ke liye space. Yeh usually problem definition ka part hota hai.
2. Auxiliary Space: Algorithm dwara use kiya gaya extra space (variables, data structures, recursion call stack).
Generally, "space complexity" refers to auxiliary space, ya fir total space agar explicitly mention kiya ho.
Example: Sorting an array of size 'n'.

• Input Space: O(n) for the array itself.
• Bubble Sort (in-place): Auxiliary space O(1) (kuch temporary variables). Total space O(n).
• Merge Sort (not in-place): Auxiliary space O(n) (for temporary arrays during merge). Total space O(n).
• Recursive Quick Sort: Auxiliary space O(log n) average (for recursion stack), O(n) worst case. Total space O(n).

Answer: String `s1 = "hello"` aur `s2 = new String("hello")` JavaScript (aur Java) mein alag tareeke se memory allocate karte hain.
1. `String s1 = "hello";` (String Literal)

• Jab aap string literal create karte ho, toh JavaScript (or Java JVM) ise string pool (ya string constant pool) mein store karta hai.
• Agar "hello" pehle se pool mein hai, toh `s1` usi existing "hello" ko point karega. Koi naya object nahi banega.
• `s1 == s3` (where `s3 = "hello"`) would be true (reference equality in some contexts, definitely value equality).

• `new` keyword hamesha ek naya object heap memory mein create karta hai.
• Toh `s2` heap mein ek naye String object ko point karega, bhale hi "hello" string pool mein already ho. (Internally, this new object might still refer to the "hello" characters from the pool or have its own copy, depending on implementation).
• `s1 == s2` would be false (reference equality, as they point to different memory locations/objects).
• `s1.equals(s2)` (in Java) or `s1 === s2` (for value in JS, though `s1 == s2` for literals can be true due to interning) or `s1.valueOf() === s2.valueOf()` would be true (value equality). In JavaScript, `s1` is a primitive string, `s2` is an object. So `s1 === s2` is false. `s1 == s2` is true due to type coercion.

Answer:
Greedy Approach: Har step pe locally optimal choice banata hai, is ummeed mein ki yeh globally optimal solution dega.

• Example: Dijkstra's Shortest Path Algorithm. Har step pe, woh vertex choose karta hai jo source se ab tak ka sabse chhota distance rakhta hai aur unvisited hai.
• Coin Change Problem (Canonical Coins): Agar aapko specific denominations (e.g., 1, 5, 10, 25) se change dena hai, toh greedy approach (sabse bada coin pehle do jo amount se kam ya barabar ho) kaam karta hai.
• Pros: Simple to design, often fast.
• Cons: Not always guaranteed to find the global optimum. For example, coin change problem with non-canonical coins (e.g., 1, 7, 10 for amount 15: greedy gives 10+1*5=15, optimal is 7+7+1=15 ... wait, greedy gives 10,1,1,1,1, optimal 7,7,1). Correct for 15 with {1,7,10}: Greedy 10+1*5, fails. Optimal 7+7+1. Greedy gives 10, (rem 5) -> no 5. Oh, for amount 15 with {1,7,10}, greedy would pick 10. Remaining 5. Picks 1 five times. Total coins: 1+5=6. Optimal: 7+7+1, uses 3 coins. So greedy fails.
  Example for {1, 3, 4} and amount 6: Greedy: 4 + 1 + 1 (3 coins). Optimal: 3 + 3 (2 coins).

• Breaks problem into overlapping subproblems and solves each subproblem only once, storing its result (memoization/tabulation).
• Builds up solution from bottom-up or uses recursion with memoization.
• Example: Fibonacci Sequence, 0/1 Knapsack, Coin Change (general case). For coin change for amount 6 with {1,3,4}: DP would explore all possibilities and find 3+3.
• Pros: Guaranteed to find optimal solution if problem has optimal substructure and overlapping subproblems.
• Cons: Can be more complex to design and might have higher space complexity for storing subproblem solutions.

Answer:
Pass by Value:

• Jab ek variable function ko as an argument pass hota hai, toh us variable ki value ki copy function ke parameter ko milti hai.
• Function ke andar parameter mein koi bhi change original variable ko affect nahi karta.
• Primitive types (like numbers, strings, booleans in JavaScript) are typically passed by value.
• function modify(x) { x = 100; } let a = 10; modify(a); console.log(a); // Output: 10

• Jab ek variable function ko pass hota hai, toh us variable ka memory address (reference) function ke parameter ko milta hai.
• Function ke andar parameter ke through object ke properties mein changes original object ko affect karte hain, kyunki dono (original variable aur parameter) same memory location ko point kar rahe hote hain.
• Objects and Arrays in JavaScript are passed by "call-by-sharing" or "pass by reference value". Matlab, reference (memory address) ki value copy hoti hai. So, if you change the object's properties, the original object changes. But if you reassign the parameter to a new object, the original reference is unaffected.
• function modifyObj(obj) { obj.prop = "changed"; } let myObj = {prop: "original"}; modifyObj(myObj); console.log(myObj.prop); // Output: changed
• function reassignObj(obj) { obj = {prop: "new object"}; } modifyObj(myObj); console.log(myObj.prop); // Still "changed", not "new object" because obj inside reassignObj now points to a new memory location.

Answer:
Abstraction: Hiding complex implementation details and showing only essential features of an object/system. User ko "kya karta hai" pata hota hai, "kaise karta hai" nahi.

• Example: Car. Aap steering, accelerator, brakes use karte ho (essential features). Aapko engine ke internal working (complex details) janne ki zaroorat nahi. In programming, a function signature is an abstraction.

• Example: A `Capsule` (pill) contains medicine (data) securely. In a `BankAccount` class, `balance` (data) and `deposit()`/`withdraw()` (methods) are bundled. `balance` might be private, accessible only via methods.
• Benefit: Data hiding, better control, reduces complexity, increases reusability.

Answer: In a file system:

• Directories (Folders): These are like N-ary Trees (or general trees). Each directory can contain multiple files and subdirectories. The root directory is the root of the tree.
• Files: These are like Leaf Nodes in this tree structure.
• Path to a file/directory: Represents a path from the root node to a specific node in the tree. Example: `/home/user/docs/file.txt`.

• Navigating (`cd`): Traversing from one node (directory) to another (child or parent).
• Listing contents (`ls`): Getting all children of a node.
• Creating directory (`mkdir`): Adding a new child node (directory type).
• Searching for a file: A tree traversal (like DFS or BFS) to find a specific node.

Answer:
Problem: Check if a given string of parentheses `(`, `)`, `{`, `}`, `[`, `]` is "valid" or "balanced".
Valid: `()`, `()[]{}`, `({[]})`
Invalid: `(]`, `([)]`, `{{`
Solution using Stack:

1. Initialize an empty stack.
2. Iterate through the input string character by character.
3. If the character is an opening bracket (`(`, `{`, `[`), push it onto the stack.
4. If the character is a closing bracket (`)`, `}`, `]`):
   • If the stack is empty, it means there's no matching opening bracket. Return false (invalid).
   • Pop the top element from the stack.
     • If the popped opening bracket doesn't match the current closing bracket (e.g., `)` with `{`), return false (invalid).
5. After iterating through the entire string, if the stack is empty, it means all opening brackets were matched. Return true (valid).
6. If the stack is not empty, it means there are unmatched opening brackets. Return false (invalid).

Answer:
Merge Sort:

• Divide and Conquer: Yes. Divides array into two halves, sorts them recursively, then merges.
• Time Complexity: O(n log n) in all cases (worst, average, best).
• Space Complexity: O(n) for auxiliary array used in merging. Not in-place.
• Stable: Yes (if implemented carefully, equal elements maintain their relative order).

• Divide and Conquer: Yes. Picks a pivot, partitions array around pivot, then sorts sub-arrays recursively.
• Time Complexity:
  • Average/Best Case: O(n log n).
  • Worst Case: O(n²) (e.g., if array is already sorted and pivot is always first/last element). Randomized pivot selection or median-of-three helps avoid this.
• Space Complexity: O(log n) average (for recursion stack), O(n) worst case. In-place partitioning means less auxiliary space than Merge Sort for main data.
• Stable: No (typically not stable, depends on partitioning).

Answer:
Load Factor (α) = n / m
where `n` = number of elements stored in the hash table, and `m` = number of slots/buckets in the hash table.
It represents how full the hash table is.
Impact on Performance:

• Low Load Factor (e.g., α < 0.5):
  • Fewer collisions.
  • Search, insert, delete operations are closer to O(1).
  • Wasted space, as many slots are empty.
• High Load Factor (e.g., α > 0.7-0.8 for chaining, or approaching 1 for open addressing):
  • More collisions.
  • Performance degrades.
    • Chaining: Average length of linked lists increases. Lookup becomes O(1 + α) on average.
    • Open Addressing: Probing sequences become longer. Lookup can approach O(n) in worst case if clustering is bad.
  • Less wasted space.

Answer:
1. Iterative Approach (using a `prev` pointer):

1. Initialize three pointers: `prev = null`, `current = head`, `next = null`.
2. Iterate while `current` is not null:
   1. Store `current.next` in `next_node`. (`next_node = current.next;`)
   2. Reverse the `current` node's pointer: `current.next = prev;`
   3. Move `prev` and `current` one step forward: `prev = current; current = next_node;`
3. The new head of the reversed list is `prev`. Return `prev`.

function reverseRecursive(head) {
    if (head == null || head.next == null) {
        return head; // Base case: empty list or single node
    }

    // Recursively reverse the rest of the list
    let restReversedHead = reverseRecursive(head.next);

    // Make current head.next (which is now tail of reversed 'rest')
    // point back to current head
    head.next.next = head;

    // Set current head's next to null (it becomes the new tail)
    head.next = null;

    return restReversedHead; // The head of the fully reversed list
}
                    

Answer:
Scenario: You have an array where elements are sorted, but then "rotated" at some pivot point. Example: `[4, 5, 6, 7, 0, 1, 2]` (original `[0,1,2,4,5,6,7]` rotated). You need to search for an element.
Modified Binary Search:

1. Standard binary search setup: `low = 0`, `high = n-1`.
2. While `low <= high`:
   1. `mid = low + Math.floor((high - low) / 2)`.
   2. If `arr[mid] == target`, return `mid`.
   3. Determine which half is sorted:
      • If `arr[low] <= arr[mid]` (left half is sorted):
        • If `target >= arr[low]` AND `target < arr[mid]` (target is in sorted left half): `high = mid - 1`.
        • Else (target is in unsorted right half): `low = mid + 1`.
      • Else (`arr[mid] < arr[high]`, right half is sorted):
        • If `target > arr[mid]` AND `target <= arr[high]` (target is in sorted right half): `low = mid + 1`.
        • Else (target is in unsorted left half): `high = mid - 1`.
3. If loop finishes, target not found, return -1.

Answer:
A substring is a contiguous part of a string. Example: "sub" is a substring of "substring".
A subsequence is derived from a string by deleting zero or more characters, maintaining relative order. Example: "sting" is a subsequence of "substring" (delete 's', 'u', 'b'). "srig" is also a subsequence.
Problem: Find the Longest Common Subsequence (LCS) of two strings X and Y.
Dynamic Programming Approach: Let `m` be length of X, `n` be length of Y. Create a 2D table `dp[m+1][n+1]`. `dp[i][j]` will store the length of LCS of `X[0...i-1]` and `Y[0...j-1]`.
Initialization: `dp[0][j] = 0` for all `j`, `dp[i][0] = 0` for all `i`. (LCS with empty string is 0).
Fill the table: For `i` from 1 to `m`, `j` from 1 to `n`:

• If `X[i-1] == Y[j-1]` (characters match): `dp[i][j] = 1 + dp[i-1][j-1]` (current character contributes to LCS)
• If `X[i-1] != Y[j-1]` (characters don't match): `dp[i][j] = max(dp[i-1][j], dp[i][j-1])` (LCS is max of LCS without X[i-1] or LCS without Y[j-1])

Answer:
Normalization (Database): Process of organizing data in a database to reduce redundancy and improve data integrity. It involves dividing larger tables into smaller, well-structured tables and defining relationships between them.
Normal Forms (NF):

• 1NF (First Normal Form):
  • Each table cell should contain a single (atomic) value.
  • Each record needs to be unique (usually via a primary key).
  • No repeating groups of columns.
  Example: If a `Student` table has a `Courses` column with "Math, Physics", it violates 1NF. Should be separate rows for each course or a separate `StudentCourses` table.
• 2NF (Second Normal Form):
  • Must be in 1NF.
  • All non-key attributes must be fully functionally dependent on the entire primary key. (No partial dependencies on a composite primary key).
  • If PK is single column, table is automatically in 2NF if in 1NF.
  Example: Table `OrderDetails(OrderID, ProductID, ProductName, Quantity)`. PK = (OrderID, ProductID). `ProductName` depends only on `ProductID` (partial dependency). Split into `Products(ProductID, ProductName)` and `OrderItems(OrderID, ProductID, Quantity)`.
• 3NF (Third Normal Form):
  • Must be in 2NF.
  • No transitive dependencies. A non-key attribute should not depend on another non-key attribute.
  Example: `EmployeeDetails(EmpID, EmpName, DepartmentID, DepartmentName)`. PK = `EmpID`. `DepartmentName` depends on `DepartmentID` (non-key), which depends on `EmpID`. Transitive: `EmpID -> DepartmentID -> DepartmentName`. Split into `Employees(EmpID, EmpName, DepartmentID)` and `Departments(DepartmentID, DepartmentName)`.
• BCNF (Boyce-Codd Normal Form): Stricter than 3NF. For every non-trivial functional dependency `X -> Y`, `X` must be a superkey.

Answer:
Deadlock: A situation where two or more processes/threads are blocked forever, each waiting for a resource held by another process/thread in the same set.
Four Necessary Conditions for Deadlock (Coffman Conditions): All four must hold simultaneously for a deadlock to occur.

1. Mutual Exclusion: At least one resource must be held in a non-sharable mode. Only one process can use the resource at any given time. (e.g., a printer).
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be forcibly taken away from a process holding it. They must be released voluntarily by the process.
4. Circular Wait: A set of waiting processes {P0, P1, ..., Pn} must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, ..., Pn-1 is waiting for a resource held by Pn, and Pn is waiting for a resource held by P0.

• Prevention: Ensure at least one of the four conditions cannot hold. (e.g., request all resources at once - breaks Hold and Wait; allow preemption). Often restrictive.
• Avoidance: Use algorithms (like Banker's Algorithm) to check if granting a resource request could lead to a deadlock. Grant only if system remains in a "safe state". Requires prior knowledge of resource needs.
• Detection and Recovery: Allow deadlocks to occur, detect them (e.g., using resource allocation graphs), and then recover (e.g., by terminating a process, preempting resources).
• Ignoring (Ostrich Algorithm): Pretend deadlocks don't happen. Common in many OSes if deadlocks are rare and recovery is complex/costly.

Answer:
Process:

• An instance of a program in execution.
• Heavyweight. Each process has its own independent memory space (address space), including code, data, stack, heap.
• Processes are isolated from each other. Communication between processes (Inter-Process Communication - IPC) is more complex and slower (e.g., pipes, sockets, shared memory).
• Context switching between processes is slower due to more state to save/load (memory maps, etc.).
• If one process crashes, it usually doesn't affect other processes.

• A lightweight unit of execution within a process. A process can have multiple threads.
• Threads within the same process share the same memory space (code, data, heap). Each thread has its own stack and registers.
• Threads can communicate more easily and quickly using shared variables.
• Context switching between threads of the same process is faster.
• If one thread crashes, it can crash the entire process (as they share memory).
• Threads allow for parallelism (on multi-core systems) or concurrency (on single-core systems by interleaving execution) within a single application.

Answer:
SQL (Structured Query Language):

• Relational Databases (RDBMS). Examples: MySQL, PostgreSQL, Oracle, SQL Server.
• Data is stored in tables with rows and columns.
• Predefined schema (structure of tables and data types is fixed before data insertion).
• Strongly consistent (ACID properties: Atomicity, Consistency, Isolation, Durability).
• Good for complex queries involving joins between multiple tables.
• Vertically scalable (increase power of single server - CPU, RAM). Can also be horizontally scalable but more complex.

• Non-relational databases. Can be Document-based, Key-Value stores, Column-family stores, Graph databases. Examples: MongoDB (Document), Redis (Key-Value), Cassandra (Column-family), Neo4j (Graph).
• Dynamic schema or schema-less. Structure can vary.
• Data can be stored in various formats (JSON-like documents, key-value pairs, etc.).
• Often prioritize availability and partition tolerance over strong consistency (BASE properties: Basically Available, Soft state, Eventually consistent). Some NoSQL DBs offer tunable consistency.
• Good for unstructured or semi-structured data, large volumes of data, high write loads.
• Horizontally scalable (distribute data across multiple servers).

Answer:
Indexing in databases is like an index in a book. It's a data structure (often a B-Tree or B+Tree) that improves the speed of data retrieval operations on a database table.
How it works:

1. An index is created on one or more columns of a table.
2. The index stores the column values and pointers (row IDs or physical addresses) to the actual rows in the table that contain those values.
3. The index is kept sorted (or structured in a way that allows fast searching, like a hash table for hash indexes).
4. When a query with a `WHERE` clause on an indexed column is executed, the database can use the index to quickly find the relevant rows instead of scanning the entire table (Full Table Scan).

• Faster query performance (SELECTs, particularly with WHERE, JOIN, ORDER BY clauses).

• Slower write operations (INSERT, UPDATE, DELETE): Indexes also need to be updated, adding overhead.
• Extra storage space: Indexes consume disk space.
• Careful selection needed: Indexing all columns is not good. Index columns frequently used in WHERE clauses, JOIN conditions, and ORDER BY clauses. Small tables might not benefit much.