Skip to content

I have create this repo to keep a track on my Problem solving progress.

Notifications You must be signed in to change notification settings

prakritikishore/Problem-solving-101

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 

Repository files navigation

Problem-solving-101



Arrays

  • Sort an array of 0’s 1’s 2’s without using extra space or sorting algo
  • Repeat and Missing Number
  • Merge two sorted Arrays without extra space
  • Kadane’s Algorithm
  • Merge Overlapping Subintervals
  • Find the duplicate in an array of N+1 integers.
  • Set Matrix Zeros
  • Pascal Triangle
  • Next Permutation
  • Inversion of Array (Using Merge Sort)
  • Stock Buy and Sell
  • Rotate Matrix
  • Search in a 2D matrix
  • Pow(X,n)
  • Majority Element (>N/2 times)
  • Majority Element (>N/3 times)
  • Grid Unique Paths
  • Reverse Pairs (Leetcode)
  • Go through Puzzles from GFG (Search on own)

Hashing

  • 2 Sum problem
  • 4 Sum problem
  • Longest Consecutive Sequence
  • Largest Subarray with 0 sum
  • Count number of subarrays with given XOR(this clears a lot of problems)
  • Longest substring without repeat

LinkedList

  • Reverse a LinkedList
  • Find middle of LinkedList
  • Merge two sorted Linked List
  • Remove N-th node from back of LinkedList
  • Delete a given Node when a node is given. (0(1) solution)
  • Add two numbers as LinkedList
  • Find intersection point of Y LinkedList
  • Detect a cycle in Linked List
  • Reverse a LinkedList in groups of size k.
  • Check if a LinkedList is palindrome or not.
  • Find the starting point of the Loop of LinkedList
  • Flattening of a LinkedList
  • Rotate a LinkedList

2-pointer

  • Clone a Linked List with random and next pointer
  • 3 sum
  • Trapping rainwater
  • Remove Duplicate from Sorted array
  • Max consecutive ones

Greedy

  • N meeting in one room
  • Minimum number of platforms required for a railway
  • Job sequencing Problem
  • Fractional Knapsack Problem
  • Greedy algorithm to find minimum number of coins
  • Activity Selection (it is same as N meeting in one room)

Recursion

  • Subset Sums
  • Subset-II
  • Combination sum-1
  • Combination sum-2
  • Palindrome Partitioning
  • K-th permutation Sequence

Recursion and Backtracking

  • Print all Permutations of a string/array
  • N queens Problem
  • Sudoku Solver
  • M coloring Problem
  • Rat in a Maze
  • Word Break (print all ways) (Will be covered later in DP series)

Divide and Conquer

  • N-th root of an integer (use binary search) (square root, cube root, ..)
  • Matrix Median
  • Find the element that appears once in sorted array, and rest element appears twice (Binary search)
  • Search element in a sorted and rotated array/ find pivot where it is rotated
  • Median of 2 sorted arrays
  • K-th element of two sorted arrays

Stack and Queue

  • Implement Stack / Implement Queue
  • BFS
  • Implement Stack using Queue
  • Implement Queue using Stack
  • Check for balanced parentheses
  • Next Greater Element

String

  • Reverse Words in a String
  • Longest Palindrome in a string
  • Roman Number to Integer and vice versa
  • Implement ATOI/STRSTR
  • Longest Common Prefix
  • Rabin Karp
  • Prefix Function/Z-Function
  • KMP algo
  • Minimum characters needed to be inserted in the beginning to make it palindromic.
  • Check for Anagrams
  • Count and Say
  • Compare version numbers

Binary Tree

  • Inorder Traversal (with recursion and without recursion)
  • Preorder Traversal (with recursion and without recursion)
  • Postorder Traversal (with recursion and without recursion)
  • LeftView Of Binary Tree
  • Bottom View of Binary Tree
  • Top View of Binary Tree
  • Level order Traversal / Level order traversal in spiral form
  • Height of a Binary Tree
  • Diameter of Binary Tree
  • Check if Binary tree is height balanced or not
  • LCA in Binary Tree
  • Check if two trees are identical or not
  • Maximum path sum
  • Construct Binary Tree from inorder and preorder
  • Construct Binary Tree from Inorder and Postorder
  • Symmetric Binary Tree
  • Flatten Binary Tree to LinkedList
  • Check if Binary Tree is mirror of itself or not

Binary Search Tree

  • Populate Next Right pointers of Tree
  • Search given Key in BST
  • Construct BST from given keys.
  • Check is a BT is BST or not
  • Find LCA of two nodes in BST
  • Find the inorder predecessor/successor of a given Key in BST.
  • Floor and Ceil in a BST
  • Find K-th smallest and K-th largest element in BST (2 different Questions)
  • Find a pair with a given sum in BST
  • BST iterator
  • Size of the largest BST in a Binary Tree
  • Serialize and deserialize Binary Tree

Graph

  • Clone a graph (Not that easy as it looks)
  • DFS
  • BFS
  • Detect A cycle in Undirected Graph/Directed Graph
  • Topo Sort
  • Number of islands (Do in Grid and Graph both)
  • Bipartite Check
  • SCC(using KosaRaju’s algo)
  • Djisktra’s Algorithm
  • Bellman Ford Algo
  • Floyd Warshall Algorithm
  • MST using Prim’s Algo
  • MST using Kruskal’s Algo

Dynamic Programming

  • Max Product Subarray
  • Longest Increasing Subsequence
  • Longest Common Subsequence
  • 0-1 Knapsack
  • Edit Distance
  • Maximum sum increasing subsequence
  • Matrix Chain Multiplication
  • Maximum sum path in matrix, (count paths, and similar type do, also backtrack to find the maximum path)
  • Coin change
  • Subset Sum
  • Rod Cutting
  • Egg Dropping
  • Word Break
  • Palindrome Partitioning (MCM Variation)
  • Maximum profit in Job scheduling

Revising questions

  • Next Smaller Element
  • LRU cache (vvvv. imp)
  • Largest rectangle in histogram
  • Sliding Window maximum
  • Implement Min Stack
  • Rotten Orange (Using BFS)
  • Binary Tree to Double Linked List
  • Find median in a stream of running integers.
  • K-th largest element in a stream.
  • Distinct numbers in Window.
  • K-th largest element in an unsorted array.
  • Flood-fill Algorithm
  • Check if a number if a power of 2 or not in O(1)
  • Count total set bits
  • Divide Integers without / operator
  • Power Set (this is very important)
  • Find MSB in o(1)
  • Find square of a number without using multiplication or division operators.

Releases

No releases published

Packages

No packages published