/Placement_prep

Primary LanguageC++

Important Algorithms asked in interview

Graph

  1. dfs
  2. bfs
  3. Cycle detection in undirected graph:
    • using dfs
    • using bfs
  4. Cycle detection in directed graph:
    • using dfs
    • using bfs
  5. Topological sort:
    • using dfs
    • using bfs
  6. Djikstra's algo for sortest path from source to all node
  7. Prim's algo for MST
  8. Kruskal's algo for MST
  9. Bridge in graph / Critical connection
  10. Articulation point (Tarjan's Algo) -related to bridge in graph-
  11. Bellman ford algorithm for sortest path from source to all node also include negative edges => find negative cycle in graph
  12. kosaraju's algorithm to find strongly connected component => discovered by all nodes to all nodes

Tree

  1. Inorder, Postorder, Preorder traversal
  2. left view, top view, bottom view of tree
  3. vertical order traversal
  4. Morris Inorder and preorder traversal takes O(1) space complexity for traversal
  5. Level order traversal
  6. Boundary traversal of tree
  7. Binary Tree Maximum Path Sum ... To be continued

Stack and Queue

  1. Balanced parantheses
  2. Next greater element
  3. Largest rectangle in histogram
  4. Sliding Window Maximum

Heap

  1. Max heap, Min Heap implementation (Hard)
  2. kth largest element
  3. k most frequent element
  4. Merge k sorted array
  5. Find median of from data stream
  6. maximum sum combination
  7. Sliding Window maximum

Greedy

  1. N meetings in a room
  2. Minimum num of platform required
  3. job sequencing problem
  4. Activity selection
  5. minimum number of coins

Linked list

  1. LRU cache

Dynamic programming

Types of DP questions:

  1. 0/1 knapsack =>
    • Subset sum
    • equal sum partition
    • count of subset sum
    • minimum subset sum diff
    • target sum
    • number of subset of given difference
  2. unbounded knapsack
    • rod cutting
    • coin change
    • coin change 2
    • maximum ribbon cut {not imp}
  3. Fibonacees
  4. LCS
    • longest common substring
    • print lcs
    • shortest common supersequence
    • print SCS
    • minimum number of insertion and deletion to make a from b string
    • largest repeating subsequence
    • length of largest subsequence of a which is a substring is b
    • subsequnce pattern matching
    • largest palindromic subsequence
    • largest palindromic substring
    • count of palindromic substring
    • min number of deletion/ insertion to make string a from b
  5. LIS
  6. Kadane's Algo
  7. Matrix chain multiplication
  8. DP on tree
  9. dp on grid
  10. others