SouravDas25/NetworkingPaper

Data Structure & Algorithms

Arrays

• Suffix & Prefix Array, sum or product

  • Suffix Arrays with cache
    • Sub-Array Sum With K

• sum or product except self

  • total = sum(array), for each item, subtract that from total
  • total = product(array), for each item, divide that from total
    • track division by zero

• Sliding Window

  • if continuous sub-array is asked,
  • sliding window does not work with negative no
  • Minimum Size Subarray Sum
  • Longest Substring Without Repeating Character
  • https://leetcode.com/problems/continuous-subarray-sum

• O(n) important Algorithms

  • Maximum Absolute Difference
  • Majority Element
  • next-permutation
  • Permutation Sequence

• Cyclic Sort

  • first-missing-positive

• String Sort

  • largest-number

• Two Pointer

  • two pointer with sorted Array
  • two pointer with sliding window
  • remove duplicate from sorted Array
  • Two Pointer to compare two list of intervals
    • interval-list-intersections

Binary Search

• Matrix Search
• Median of 2 sorted Array
  • Median Of Two Sorted Arrays
• Search in Rotated Array
• Median of N Sorted Array

LinkedList

• Traversal
  • Reverse linked List
    • reverse-linked-list-ii
  • Middle Of linked List
    • Palindrome Linked List
  • Traversal in Groups
    • reverse-nodes-in-k-group
• Partition Linked List on some Condition
  • sort binary linked list
  • bucket sort
• Merge two Linked List
  • Merge to sorted Linked List
• Cycle
  • Detect Cycle
  • Find Cycle Point

Stack

• Balance Parenthesis
  • Longest Valid Parentheses
  • valid-parenthesis-string
• Tracking Previous Result
  • largest-rectangle-in-histogram
  • maximal-rectangle
  • daily-temperatures
• Advance Stack
  • Min Stack
  • Max Stack
• Infix 2 PostFix
• Expression Evaluation
  • Asteroid Collision

Queue & Strings

Heap, Maps & Hashing

• K or Kth Largest / Smallest Element
  • k largest element
• min and max Heap Combination
  • Median of Input Stream
• Caches
  • LRU Cache
  • LFU Cache
  • LRU with Time to Live
• Merge K Sorted List
• Hashing
  • Points on a Straight Line
  • fraction-to-recurring-decimal

Trees

• Property of tree

  • Maximum Edge Removal

• DFS

  • InOrder
    • keeping answer in global variable
    • traverse 2 trees together
      • merge-two-binary-trees
  • PreOrder
  • PostOrder
  • Vertical Order Traversal
    • Vertical Sum Of Binary Tree
  • Level Order Traversal
    • Cousins In Binary Tree
  • Diagonal Order Traversal
    • diagonal-traversal

• BFS

  • Level Order Traversal
    • Left and Right Side View of the tree
      • Cover and Uncover Nodes
    • Level Zig Zag Traversal

• DFS + BFS

  • Parent + Children Traversal
    • All Nodes Distance K in Binary Tree

• Generate All Binary Trees

  • Unique Binary Search Trees
  • all-possible-full-binary-trees

• DP Solution

  • Callan Number
    • Unique Binary Search Trees

Graph

• Adj List

• Matrix

• Cycle Detection

  • Directed
    • use DFS with global and local visited set,
    • Cycle In Directed Graph
  • Undirected
    • use Union Find // union find only works with undirected
    • Cycle In Undirected Graph

• BFS

  • Bi-directional BFS
  • Normal BFS
    • use queue
  • Heap BFS
    • pick min weight of graph
    • Commutable Island

• DFS

  • iterative DFS with stack
    • Cycle In Directed Graph
  • use recursion for normal, use global and local visited set
    • Course Schedule

• Union Find

  • find disconnected graphs
    • Number Of Provinces
  • find parent of each nodes with ranking
    • Cycle In Undirected Graph

• Minimal Spanning Tree

  • do bfs for minimum using heap, instead of queue
    • Commutable Island

• Topological Sort

  • use dfs and the reverse the traversed list
    • Course Schedule
  • All topological sorts of a Directed Acyclic Graph

• In/Out Degree of Graph

  • count the incoming connections and outgoing connections in each node
    • minimum-number-of-vertices-to-reach-all-nodes

• Strongly Connected Components

  • Kosaraju's Algorithm
    • reverse DFS
    • Strongly Connected Graphs

• Single Source Shortest Path

  • Bellman Fords Algorithm
    • Bellman Ford Algorithm
  • Dijsktra Algorithm
    • Dijkstra Algorithm

• All Pair Shortest Path

  • Floyd-Warshall Algorithm
    • Floyd Warshall Algorithm

Recursion/backtracking

• Memoization
  • best-time-to-buy-and-sell-stock-iv
  • best-time-to-buy-and-sell-stock-ii

Greedy

• Greedy with single Array Traversal

  • valid-parenthesis-string

• Reverse traversal of Array, with cache

  • jump-game II

• use min heap to take greedy decision

  • merge-triplets-to-form-target-triplet

• Greedy Algorithms

Dynamic Programming

• Find out the item used from the DP problem

  • Coin Change

• Constant Space DP

  • climbing-stairs
  • Selecting Alternating items
    • house-robber
    • delete-and-earn

• 1D Dp

  • Simple Array DP
    • longest-increasing-subsequence
    • Unique Binary Search Trees

• 2D Dp

• Knapsack 0/1

  • Subset Sum Problem
    • Partition Equal Subset Sum
  • Equal Sum Partition problem
  • Target Sum

• Knapsack Unbounded

  • Coin Change Problem
    • Coin Change
  • Rod Cutting Problem
  • Maximum Product Cutting

• Longest Common Subsequence

  • Longest Common Subsequence
  • Longest Palindromic Subsequence

• Egg Dropping Problem

  • Super Egg Drop

• Matrix Chain Multiplication

• Word Break

• Palindromic Partitioning

• DP with Grid — Unique Paths

• DP with Strings

• DP with bit-masking

ALL DP Questions : DP PROBLEMS

Advance Data Structures

• Fibonacci Heap
• Splay Trees
• Dynamic graph data structures

Augmenting Data Structures

• Order statistics
  • Find i'th smallest element
  • Randomized Quick Sort Partitions with Divide & Conquer - O(n)
  • Augmented Red Black Trees - O(log n)
• Interval Trees
  • find overlapping intervals in O(log n) time.
  • augmented red black trees
• Segment Trees
  • get SUM, MIN, MAX in O(log n) time