/DSA

Primary LanguageC++MIT LicenseMIT

1. Programming Language

OOPs

C++

2. Database Management Systems

3. Operating Systems

4. Data Structures and Algorithms

Must do Coding Problems

Arrays :

  • Subarray with given sum
  • Count the triplets
  • Kadane’s Algorithm
  • Missing number in array
  • Merge two sorted arrays
  • Rearrange array alternatively
  • Number of pairs
  • Inversion of Array
  • Sort an array of 0s, 1s and 2s
  • Equilibrium point
  • Leaders in an array
  • Minimum Platforms
  • Reverse array in groups
  • K’th smallest element
  • Trapping Rain Water
  • Pythagorean Triplet
  • Chocolate Distribution Problem
  • Stock buy and sell
  • Element with left side smaller and right side greater
  • Convert array into Zig-Zag fashion
  • Last Index of 1
  • Spirally traversing a matrix
  • Largest Number formed from an Array

String :

  • Reverse words in a given string
  • Permutations of a given string
  • Longest Palindrome in a String
  • Recursively remove all adjacent duplicates
  • Check if string is rotated by two places
  • Roman Number to Integer
  • Anagram
  • Remove Duplicates
  • Form a Palindrome
  • Longest Distinct Characters in the string
  • Implement Atoi
  • Implement strstr
  • Longest Common Prefix

Divide and Conquer :

  • Find the element that appears once in sorted array
  • Search in a Rotated Array
  • Binary Search
  • Sum of Middle Elements of two sorted arrays
  • Quick Sort
  • Merge Sort
  • K-th element of two sorted Arrays

Backtracking :

  • N-Queen Problem
  • Solve the Sudoku
  • Rat in a Maze Problem
  • Word Boggle
  • Generate IP Addresses

Bit Magic :

  • Find first set bit
  • Rightmost different bit
  • Check whether K-th bit is set or not
  • Toggle bits given range
  • Set kth bit
  • Power of 2
  • Bit Difference
  • Rotate Bits
  • Swap all odd and even bits
  • Count total set bits
  • Longest Consecutive 1’s
  • Sparse Number
  • Alone in a couple
  • Maximum subset XOR

Linked List :

  • Finding middle element in a linked list
  • Reverse a linked list
  • Rotate a Linked List
  • Reverse a Linked List in groups of given size
  • Intersection point in Y shaped linked lists
  • Detect Loop in linked list
  • Remove loop in Linked List
  • n’th node from end of linked list
  • Flattening a Linked List
  • Merge two sorted linked lists
  • Intersection point of two Linked Lists
  • Pairwise swap of a linked list
  • Add two numbers represented by linked lists
  • Check if Linked List is Palindrome
  • Implement Queue using Linked List
  • Implement Stack using Linked List
  • Given a linked list of 0s, 1s and 2s, sort it
  • Delete without head pointer

Stack and Queue :

  • Parenthesis Checker
  • Next larger element
  • Queue using two Stacks
  • Stack using two queues
  • Get minimum element from stack
  • LRU Cache
  • Circular tour
  • First non-repeating character in a stream
  • Rotten Oranges
  • Maximum of all subarrays of size k

Tree :

  • Print Left View of Binary Tree
  • Check for BST
  • Print Bottom View of Binary Tree
  • Print a Binary Tree in Vertical Order
  • Level order traversal in spiral form
  • Connect Nodes at Same Level
  • Lowest Common Ancestor in a BST
  • Convert a given Binary Tree to Doubly Linked List
  • Write Code to Determine if Two Trees are Identical or Not
  • Given a binary tree, check whether it is a mirror of itself
  • Height of Binary Tree
  • Maximum Path Sum
  • Diameter of a Binary Tree
  • Number of leaf nodes
  • Check if given Binary Tree is Height Balanced or Not
  • Serialize and Deserialize a Binary Tree

Heap :

  • Find median in a stream
  • Heap Sort
  • Operations on Binary Min Heap
  • Rearrange characters
  • Kth largest element in a stream
  • Merge K sorted linked lists
  • Kth largest element in a stream

Recursion :

  • Flood fill Algorithm
  • Number of paths
  • Combination Sum – Part 2
  • Special Keyboard
  • Josephus problem

Hashing :

  • Relative Sorting
  • Sorting Elements of an Array by Frequency
  • Largest subarray with 0 sum
  • Common elements
  • Find all four sum numbers
  • Swapping pairs make sum equal
  • Count distinct elements in every window
  • Array Pair Sum Divisibility Problem
  • Longest consecutive subsequence
  • Array Subset of another array
  • Find all pairs with a given sum
  • Find first repeated character
  • Zero Sum Subarrays
  • Minimum indexed character
  • Check if two arrays are equal or not
  • Uncommon characters
  • Smallest window in a string containing all the characters of another string
  • First element to occur k times
  • Check if frequencies can be equal

Graph :

  • Depth First Traversal
  • Breadth First Traversal
  • Detect cycle in undirected graph
  • Detect cycle in a directed graph
  • Topological sort
  • Find the number of islands
  • Implementing Dijkstra
  • Minimum Swaps
  • Strongly Connected Components
  • Shortest Source to Destination Path
  • Find whether path exist
  • Minimum Cost Path
  • Circle of Strings
  • Floyd Warshall
  • Alien Dictionary
  • Snake and Ladder Problem

Greedy :

  • Activity Selection
  • N meetings in one room
  • Coin Piles
  • Maximize Toys
  • Page Faults in LRU
  • Largest number possible
  • Minimize the heights
  • Minimize the sum of product
  • Huffman Decoding
  • Minimum Spanning Tree
  • Shop in Candy Store
  • Geek collects the balls

Dynamic Programming :

  • Minimum Operations
  • Max length chain
  • Minimum number of Coins
  • Longest Common Substring
  • Longest Increasing Subsequence
  • Longest Common Subsequence
  • 0 – 1 Knapsack Problem
  • Maximum sum increasing subsequence
  • Minimum number of jumps
  • Edit Distance
  • Coin Change Problem
  • Subset Sum Problem
  • Box Stacking
  • Rod Cutting
  • Path in Matrix
  • Minimum sum partition
  • Count number of ways to cover a distance
  • Egg Dropping Puzzle
  • Optimal Strategy for a Game
  • Shortest Common Supersequence

Source - GFG

Data Structures:

  • Arrays
  • Linked lists
  • Stacks
  • Queues
  • Binary Trees & Binary search Trees
  • Self-balancing Trees (AVL Trees, Red-Black Trees, Splay Trees)
  • Heaps
  • Tries
  • Maps & Hash Tables
  • Graphs
  • Segment Trees
  • Fenwick Trees
  • Disjoint Set Union
  • Minimum Spanning Trees

Algorithms

  • Divide and Conquer
  • Sorting Algorithms (Bubble Sort, Counting Sort, Quick Sort, Merge Sort, Radix Sort)
  • Searching Algorithms (Linear Search, Binary Search)
  • Sieve of Eratosthenes
  • Knuth-Morris-Pratt Algorithm
  • Greedy I (Maximum number of non-overlapping intervals on an axis)
  • Greedy II (Fractional Knapsack Problem)
  • Dynamic Programming I (0–1 Knapsack Problem)
  • Dynamic Programming II (Longest Common Subsequence)
  • Dynamic Programming III (Longest Increasing Subsequence)
  • Convex Hull
  • Graph Traversals (Breadth-First Search, Depth-First Search)
  • Floyd-Warshall / Roy-Floyd Algorithm
  • Dijkstra's Algorithm & Bellman-Ford Algorithm
  • Topological Sorting

Resources: