Data Structures & Algorithms

Develop logical coding capabilities, analyze complexity bounds, and master coding interview questions.

Arrays

Easy

Contiguous blocks of memory. Master traversal, insertion, deletion, sub-arrays, rotation, and two-pointer techniques.

  1. Basic operations, index lookup, and linear searches.
  2. Subarray analysis (Kadane's algorithm for maximum sum subarray).
  3. Two-pointer and sliding window methods.
  4. Matrix calculations (2D Arrays traversal and rotation).

P1. Two Sum: Given an array of integers, find two numbers such that they add up to a specific target.

Approach: Use a Hash Map to store elements and their indices. For each element x, check if target - x exists in the map. Time complexity is O(N).

Strings

Easy

Sequences of characters. Learn reverse algorithms, anagram verification, palindrome checks, substring counts, and pattern matching.

  1. Immutability concepts and basic character manipulations.
  2. Anagram verification & palindrome checks.
  3. Substrings, sliding window matches, and hash counts.
  4. Knuth-Morris-Pratt (KMP) pattern searching algorithm.

P1. Valid Anagram: Determine if string S and T are anagrams of each other.

Approach: Use a character frequency counter array of size 26. Increment counts for string S and decrement counts for string T. Check if all values are zero. O(N) time and O(1) auxiliary space.

Linked List

Medium

Linear collections of nodes containing pointers. Study singly, doubly, and circular linked lists, loops detection, and node reversals.

  1. Node structure creation, insertion, and traversal.
  2. Reversing a linked list (Iterative and Recursive).
  3. Floyd's Cycle-Finding Algorithm (Fast and Slow pointer).
  4. Merging and sorting linked lists (Merge Sort).

P1. Detect Loop in Linked List: Check if a linked list contains a cycle.

Approach: Use two pointers: slow moving 1 step and fast moving 2 steps. If they meet at any node, a cycle exists. If fast reaches NULL, no cycle exists.

Stack

Medium

LIFO (Last In First Out) structures. Learn array/list implementations, parenthesis matching, expression evaluations, and monotonic stack concepts.

  1. Standard operations: push(), pop(), peek(), isEmpty().
  2. Balanced parenthetical checks.
  3. Infix, prefix, and postfix conversions and evaluations.
  4. Monotonic stack to solve next greater element problems.

P1. Balanced Parentheses: Check if brackets (), {}, and [] in string S are balanced.

Approach: Push opening brackets onto a stack. When a closing bracket arrives, verify it matches the top of the stack and pop. If mismatched or stack ends empty/non-empty incorrectly, return false.

Queue

Medium

FIFO (First In First Out) structures. Practice circular queues, double-ended queues (Deques), sliding window maximums, and buffer queues.

  1. Enqueue, dequeue operations using arrays and linked lists.
  2. Circular Queue representation to save memory.
  3. Priority Queue implementation using Heaps.
  4. Sliding Window Maximum utilizing a Monotonic Deque.

P1. Implement Stack using Queues: Construct stack LIFO behavior using queue FIFO methods.

Approach: Use two queues. On pushing an element, enqueue to Queue2, then enqueue all elements from Queue1 to Queue2. Swap the names of Queue1 and Queue2. Push becomes O(N), Pop is O(1).

Tree

Hard

Non-linear hierarchical nodes. Master Binary Trees, Binary Search Trees (BST), traversals (Pre, In, Post, Level order), heights, and balancing.

  1. Binary tree properties and DFS Traversals (Inorder, Preorder, Postorder).
  2. BFS Traversal (Level-order) using queues.
  3. BST insertions, deletions, search validation.
  4. Advanced structures: AVL Trees, Segment Trees, and Tries.

P1. Find Height of Binary Tree: Find the length of the longest path from root to leaf node.

Approach: Use a post-order traversal recursively. Height of tree = 1 + max(Height(left_subtree), Height(right_subtree)). Base case returns 0 for NULL.

Graph

Hard

Nodes (vertices) and edges. Understand Adjacency lists, DFS, BFS, cycle checks, Dijkstra's algorithm, and topological sorting.

  1. Representations (Adjacency Matrix, Adjacency List).
  2. Standard Graph Traversals: Depth First Search and Breadth First Search.
  3. Shortest Path finding (Dijkstra's, Bellman-Ford).
  4. Minimum Spanning Trees (Kruskal's, Prim's algorithms).

P1. Detect Cycle in Undirected Graph: Check if a path can cycle back to an already visited vertex.

Approach: During DFS, pass the 'parent' node. If a neighbor is already visited and is not the parent of the current node, a cycle exists.

Recursion

Medium

Functions calling themselves. Study call stack mechanisms, base cases, fibonacci series, Tower of Hanoi, and backtracking principles.

  1. Stack frames, parameter passing, and base case formulation.
  2. Linear vs Tree recursion models.
  3. Divide-and-Conquer paradigms.
  4. Backtracking applications (N-Queens, Subset Generation).

P1. Fibonacci Sequence: Compute the N-th Fibonacci number.

Approach: Base case: if N <= 1, return N. Otherwise, return fib(N-1) + fib(N-2). Optimize to O(N) using dynamic programming / memoization.

Sorting

Easy

Arranging elements in order. Analyze Bubble, Selection, Insertion, Merge, Quick, Heap, and Radix sort complexities.

  1. O(N²) elementary algorithms: Bubble, Selection, Insertion Sort.
  2. O(N log N) recursive sorting: Merge Sort and Quick Sort.
  3. Space-Time complexity trade-offs and Stability analysis.
  4. Non-comparison based sorting (Counting Sort, Radix Sort).

P1. Merge Sort Implementation: Sort an array recursively using merge partitions.

Approach: Divide the array into two halves, recursively sort both halves, and then merge the sorted halves back together in O(N log N) time and O(N) auxiliary space.

Searching

Easy

Finding target elements. Compare Linear Search and Binary Search on sorted spaces, and search space reduction.

  1. Unsorted arrays search: Linear Search in O(N).
  2. Sorted arrays search: Binary Search in O(log N).
  3. Binary search implementation details (avoiding index overflows).
  4. Binary search on answer space (e.g., Book Allocation Problem).

P1. Binary Search: Find index of target K in a sorted array.

Approach: Initialize low = 0, high = N-1. While low <= high, calculate mid = low + (high - low)/2. If array[mid] == target, return mid. Adjust boundaries accordingly.