DATA STRUCTURES & ALGORITHMS

  1. Overview
  2. Why DSA?
  3. Complexity
    • Time
    • Space
  4. Asymptotic Notations
    • Big-O Notation (Ο)
    • Omega Notation (Ω)
    • Theta Notation (θ)
  5. Data Structures
    • Linear
      • Array
      • Linked list
      • Stack
      • Queue
    • Non-Linear
      • Tree
      • Graph
    • String
    • Matrix
    • Heap
    • Hash Map
    • Hash Table
  6. Algorithms
    • Searching
      • Linear Search
      • Binary Search
      • Ternary Search
      • Jump Search
    • Sorting
      • Bubble Sort
      • Insertion Sort
      • Selection Sort
      • Quick Sort
      • Merge Sort
      • Heap Sort
      • Counting Sort
    • Brute Force
    • Recursion
    • Divide and Conquer
    • Greedy
    • Hashing
    • Backtracking
    • Dynamic Programming
    • Pattern Searching / String Searching 
    • Mathematical
    • Geometric
    • Bitwise 
    • Two Pointers Technique
    • Sliding Window Technique
  7. Practice Problems - Elemental 
    • Print Prime Numbers
    • Print Factorial
    • Print Fibonacci Series 
    • Reverse A Number  
    • Identify a number as Palindrome 
    • Swap two numbers without using a temporary variable 
    • Get a distinct word list from the given file
    • Get a line with max word count from the given file
    • Find two lines with max characters in descending order
    • Find Divisors Of Given Number
    • Find Sum of Digits of a Number using Recursion
    • Check Armstrong number
    • Convert Binary to Decimal Format
    • Check Whether Given Number Is Binary Or Not
    • Convert Decimal to Binary Format
    • Fizz Buzz
    • Find Perfect Number
    • Square root of an integer
    • Count Perfect Squares less than N
    • Print Star Pattern
  8. Practice Problems - Matrix
      • Spiral traversal on a Matrix
      • Search an element in a Matrix
      • Find median in a row wise sorted matrix
      • Find row with maximum no. of 1's
      • Print elements in sorted order using row-column wise sorted matrix
      • Maximum size rectangle
      • Find a specific pair in matrix
      • Rotate matrix by 90 degrees
      • Kth smallest element in a row-cpumn wise sorted matrix
      • Common elements in all rows of a given matrix
    1. Practice Problems - Graph
      • Create a Graph, print it
      • Implement BFS algorithm 
      • Implement DFS Algo 
      • Detect Cycle in Directed Graph using BFS/DFS Algo 
      • Detect Cycle in UnDirected Graph using BFS/DFS Algo 
      • Search in a Maze
      • Minimum Step by Knight
      • flood fill algo
      • Clone a graph
      • Making wired Connections
      • word Ladder 
      • Dijkstra algo
      • Implement Topological Sort 
      • Minimum time taken by each job to be completed given by a Directed Acyclic Graph
      • Find whether it is possible to finish all tasks or not from given dependencies
      • Find the no. of Isalnds
      • Given a sorted Dictionary of an Alien Language, find order of characters
      • Implement Kruksal’sAlgorithm
      • Implement Prim’s Algorithm
      • Total no. of Spanning tree in a graph
      • Implement Bellman Ford Algorithm
      • Implement Floyd warshallAlgorithm
      • Travelling Salesman Problem
      • Graph ColouringProblem
      • Snake and Ladders Problem
      • Find bridge in a graph
      • Count Strongly connected Components(Kosaraju Algo)
      • Check whether a graph is Bipartite or Not
      • Detect Negative cycle in a graph
      • Longest path in a Directed Acyclic Graph
      • Journey to the Moon
      • Cheapest Flights Within K Stops
      • Oliver and the Game
      • Water Jug problem using BFS
      • Water Jug problem using BFS
      • Find if there is a path of more thank length from a source
      • M-ColouringProblem
      • Minimum edges to reverse o make path from source to destination
      • Paths to travel each nodes using each edge(Seven Bridges)
      • Vertex Cover Problem
      • Chinese Postman or Route Inspection
      • Number of Triangles in a Directed and Undirected Graph
      • Minimise the cashflow among a given set of friends who have borrowed money from each other
      • Two Clique Problem
    2. Practice Problems - Heap
      • Implement a Maxheap/MinHeap using arrays and recursion.
      • Sort an Array using heap. (HeapSort)
      • “k” largest element in an array
      • Kth smallest and largest element in an unsorted array
      • Merge “K” sorted arrays
      • Merge 2 Binary Max Heaps
      • Leetcode- reorganize strings
      • Merge “K” Sorted Linked Lists
      • Smallest range in “K” Lists
      • Median in a stream of Integers
      • Check if a Binary Tree is Heap
      • Connect “n” ropes with minimum cost
      • Convert BST to Min Heap
      • Convert min heap to max heap
      • Rearrange characters in a string such that no two adjacent are same.
      • Minimum sum of two numbers formed from digits of an array
    3. Practice Problems - Trie
      • Construct a trie from scratch
      • Find shortest unique prefix for every word in a given list
      • Given a sequence of words, print all anagrams together
      • Implement a Phone Directory
      • Print unique rows in a given boolean matrix
    4. Practice Problems - Greedy Algorithm
      • Find Minimum number of Coins
      • Activity Selection Problem
      • Job SequencingProblem
      • Huffman Coding
      • Water Connection Problem
      • Fractional Knapsack Problem
      • Greedy Algorithm to find Minimum number of Coins
      • Maximum trains for which stoppage can be provided
      • Minimum Platforms Problem
      • Buy Maximum Stocks if i stocks can be bought on i-th day
      • Find the minimum and maximum amount to buy all N candies
      • Minimize Cash Flow among a given set of friends who have borrowed money from each other
      • Minimum Cost to cut a board into squares
      • Check if it is possible to survive on Island
      • Find maximum meetings in one room
      • Maximum product subset of an array
      • Maximize array sum after K negations
      • Maximize the sum of arr[i]*i
      • Maximum sum of absolute difference of an array
      • Maximize sum of consecutive differences in a circular array
      • Minimum sum of absolute difference of pairs of two arrays
      • Program for Shortest Job First (or SJF) CPU Scheduling
      • Program for Least Recently Used (LRU) Page Replacement algorithm
      • Smallest subset with sum greater than all other elements
      • Chocolate Distribution Problem
      • DEFKIN -Defense of a Kingdom
      • DIEHARD -DIE HARD
      • GERGOVIA -Wine trading in Gergovia
      • Picking Up Chicks
      • CHOCOLA –Chocolate
      • ARRANGE -Arranging Amplifiers
      • K Centers Problem
      • Minimum Cost of ropes
      • Job Scheduling
      • Find smallest number with given number of digits and sum of digits
      • Rearrange characters in a string such that no two adjacent are same
      • Find maximum sum possible equal sum of three stacks
    5. Practice Problems - BackTracking
      • Permutations of the given string
      • Rat in a maze Problem
      • Printing all solutions in N-Queen Problem
      • Remove Invalid Parentheses
      • Sudoku Solver
      • m Coloring Problem
      • Print all palindromic partitions of a string
      • Subset Sum Problem
      • The Knight’s tour problem
      • Tug of War
      • Find shortest safe route in a path with landmines
      • Combinational Sum
      • Find Maximum number possible by doing at-most K swaps
      • Print all permutations of a string 
      • Find if there is a path of more than k length from a source
      • Longest Possible Route in a Matrix with Hurdles
      • Print all possible paths from top left to bottom right of a mXn matrix
      • Partition of a set intoK subsets with equal sum
      • Find the K-th Permutation Sequence of first N natural numbers
    6. Practice Problems - Dynamic Programming
      • Coin ChangeProblem
      • Knapsack Problem
      • Binomial CoefficientProblem
      • Permutation CoefficientProblem
      • Program for nth Catalan Number
      • Matrix Chain Multiplication 
      • Edit Distance
      • Subset Sum Problem
      • Friends Pairing Problem
      • Gold Mine Problem
      • Assembly Line SchedulingProblem
      • Painting the Fenceproblem
      • Maximize The Cut Segments
      • Longest Common Subsequence
      • Longest Repeated Subsequence
      • Longest Increasing Subsequence
      • Longest Common Substring
      • LCS (Longest Common Subsequence) of three strings
      • Space Optimized Solution of LCS
      • Maximum Sum Increasing Subsequence
      • Count all subsequences having product less than K
      • Longest subsequence such that difference between adjacent is one
      • Maximum subsequence sum such that no three are consecutive
      • Egg Dropping Problem
      • Maximum Length Chain of Pairs
      • Maximum size square sub-matrix with all 1s
      • Maximum sum of pairs with specific difference
      • Min Cost PathProblem
      • Maximum difference of zeros and ones in binary string
      • Minimum number of jumps to reach end
      • Minimum cost to fill given weight in a bag
      • Minimum removals from array to make max –min <= K
      • Count number of ways to reacha given score in a game
      • Count Balanced Binary Trees of Height h
      • Unbounded Knapsack (Repetition of items allowed)
      • Word Break Problem
      • Largest Independent Set Problem
      • Partition problem
      • Longest Palindromic Subsequence
      • Count All Palindromic Subsequence in a given String
      • Longest Palindromic Substring
      • Longest alternating subsequence
      • Weighted Job Scheduling
      • Coin game winner where every player has three choices
      • Count Derangements (Permutation such that no element appears in its original position)
      • Maximum profit by buying and selling a share at most twice
      • Optimal Strategy for a Game
      • Optimal Binary Search Tree
      • Palindrome PartitioningProblem
      • Word Wrap Problem
      • Mobile Numeric Keypad Problem
      • Boolean Parenthesization Problem
      • Largest rectangular sub-matrix whose sum is 0
      • Largest area rectangular sub-matrix with equal number of 1’s and 0’s
      • Maximum sum rectangle in a 2D matrix
      • Maximum profit by buying and selling a share at most k times
      • Find if a string is interleaved of two other strings
      • Maximum Length of Pair Chain
    7. Practice Problems - Bit Manipulation
      • Count set bits in an integer
      • Find the two non-repeating elements in an array of repeating elements
      • Count number of bits to be flipped to convert A to B
      • Count total set bits in all numbers from 1 to n
      • Program to find whether a no is power of two
      • Find position of the only set bit
      • Copy set bits in a range
      • Divide two integers without using multiplication, division and mod operator
      • Calculate square of a number without using *, / and pow()
      • Power Set
    8. Practice Problems - Searching & Sorting
      • First and last occurrences of an element
      • Find a Fixed Point (Value equal to index) in a given array
      • Search an element in a sorted and rotated array
      • Search an element in a sorted and infinite array
      • Optimum location of point to minimize total distance
      • Find the repeating and the missing numbers
      • Majority Elements / Boyer–Moore Majority Vote Algorithm
      • Searching in an array where adjacent differ by at most k
      • Find A Pair With A Given Difference
      • Find Four Elements That Sums To A Given Value
      • Find Maximum Sum Such That No 2 Elements Are Adjacent
      • Product Array Puzzle
      • Sort Array According To Count Of Set Bits
      • Minimum Number Of Swaps Required To Sort An Array
      • Kth Smallest Number Again
      • Find Pivot Element In A Sorted Array
      • Kth Element of Two Sorted Arrays
      • Missing Number in AP
      • Smallest number with at least n trailing zeroes in factorial
      • Subset Sums
      • Implement Merge-sort in-place
      • Partitioning and Sorting Arrays with Many Repeated Entries
      • Aggressive cows
      • Book Allocation Problem
      • Painters Partition Problem
      • Bishu and Soldiers
      • Rasta and Kheshtak
      • Roti Prata - SPOJ
      • Double Helix - SPOJ
      • EKO - SPOJ
    9. Practice Problems - Pattern Searching / SubString Search
      • Rabin-Karp Algorithm
      • Knuth-Morris-Pratt (KMP) Algorithm
      • Boyer Moore Algorithm

    Subscribe to: Posts (Atom)