Manav Goyal

Dsa - C P P

Data Structure

  • Array, Vector
  • Linked List
  • Stack => LIFO
    • Implementation Using => Array, Linked List, Queue
  • Queue => FIFO
    • Implementation => Array, Linked List, Stack
    • Modification => Priority Queue
  • Tree
    • Binary Tree
      • Insertion/Search/Deletion
        • Time Complexity
          • Worst = O(n)
          • Average = O(Height of Tree)
    • Binary Search Tree
    • Heap => Min, Max
      • Insertion/Deletion
        • Time Complexity = O(logn)
  • Set
  • Hashmap
    • Insertion/Deletion/Search
      • Time Complexity, Average Case = O(1)
  • Trie
    • Insertion/Deletion/Search
      • Time Complexity = O(Length of Word)
  • Graph

Complexity

  • Time Complexity
    • Time required as function of input
    • Types
      • O Notation => It also known as worst case time complexity as it denotes the upper bound in which algorithm terminates
      • Ω Notation => We denote it by Ω(g(n)). Pronounced as "big-omega of g of n". It also known as best case time complexity as it denotes the lower bound in which algorithm terminates
      • Θ Notation => It is used to denote the average time of a program
    • Method to Find
      • Recurrence Relation
      • Recurrence Tree
      • Masters Theorem
        • Error
    • Tricks
      • O(nn) > O(n!) > O(2n) > O(n3) > O(n2) > O(n.log(n)) > O(n.log(log(n))) > O(n) > O(sqrt(n)) > O(log(n)) > O(1)
      • Value on n
        • O(n!) - (<11) > O(2n*n2) - (<18) > O(n4) - (<100) > O(n3) - (<400) > O(n2) - (<104) > O(n.log(n)) - (<106) > O(log(n)) - (<108)
      • Cubic > Quadratic > Logarithmic > Linear > Constant
      • 108 Operation Rule => Most of the modern machines can perform 108 operation/second
  • Space Complexity
    • Memory required as function of input
      • Maximum space required at any point of time

Problems

  • Recursion
    • Inversion Count
    • Subsets
    • Subsequences
    • Phone Keypad Question
    • Permutations of a String/Integers
    • Rat in a Maze Problem
    • N-Queen Problem
    • Sudoku Solver
  • Linked List
    • Floyd Cycle Detection => Detect & Remove Loop
    • Remove Duplicates from a Sorted/UnSorted Linked List
    • Add 2 numbers
  • Stack
    • Reverse String
    • Valid Parenthesis
    • Largest Rectangle in Histogram
    • Celebrity Problem
    • N Stacks in an Array
  • Queue
    • Queue Reversal
    • N Queue in an Array
  • Binary Tree
    • Lowest Common Ancestor
    • Construct a Binary Tree from InOrder/PreOrder/PostOrder Traversal
    • Minimum Time to BURN Binary Tree
    • Morris Traversal
    • Flatten a Binary tree to Linked List
    • Merge 2 Binary Search Trees
    • Largest BST in a Binary Tree
  • Heap
    • Kth Smallest element
    • Merge 2 Heaps
    • Is Tree a Heap
    • Convert BST into HEAP
    • Merge K sorted Arrays
    • Smallest Range in K sorted List
    • Median in a Stream
    • Re-Organise Strings
  • Trie
    • Longest Common Prefix
    • Phone Directory
  • Graph
    • Cycle Detection
    • Shortest Path
  • Dynamic Programming
    • Minimum Cost Climbing Stairs
    • Minimum Number of Coins
    • Minimization and Maximization problems
    • Find the number of ways
  • Binary Search
    • First and Last Position of an element
    • Find total no. of Occurrence
    • Find Peak in Mountain array
    • Find Pivot in Sorted & Rotated array
    • Search an Element in a Sorted & Rotated array
    • Find Square Root of an Integer (both int & floating part)
    • Book Allocation Problem
    • Painter’s Partition Problem
    • Aggressive Cows Problem
  • Number Theory
    • BigInteger
      • Java class for the mathematical operation which involves very big integer calculations that are outside the limit of all available primitive data types
      • #define ull unsigned long long => In C++
    • Pigeon hole Principle
      • If there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it
    • Inclusion-Exclusion
      • In the field of Combinatorics, it is a counting method used to compute the cardinality of the union set
      • Applications
        • Derangements/Permutations
  • Others
    • Armstrong Number
      • Numbers which have their sum of cube of its individual digits equal to the number itself
    • Fibonacci Series
      • Series of numbers in which each number is the sum of the two preceding numbers
      • Golden Ratio = 1.6180
    • Palindrome
      • ABCBA
    • Permutation
      • An ordered arrangement of objects is called Permutations
    • Catalan Numbers => Cn = sum(Ci * Cn-i)
      • 1 1 2 5 14 42 132 429 1430 4862 ...
    • Perfect Numbers
      • Number equal to the sum of its proper divisors except for the number itself
    • Markov Process
      • Process which depends only on the previous state
    • alpha(n) => Inverse Ackermann Function
    • Ugly Numbers
      • Numbers whose Prime factors are 2, 3 or 5
    • Fermat Little Theorem
    • Wilson Theorem
Share: