/450-dsa

Primary LanguageJava

It is useful for placement it include Babbar SDE Sheet

Arrays

  1. Reverse the array
  2. Find the maximum and minimum element in an array
  3. Find the "Kth" max and min element of an array
  4. Given an array which consists of only 0, 1 and 2. Sort the array without using any sorting algo
  5. Move all the negative elements to one side of the array
  6. Find the Union and Intersection of the two sorted arrays.
  7. Write a program to cyclically rotate an array by one.
  8. find Largest sum contiguous Subarray [V. IMP]
  9. [Minimise the maximum difference between heights [V.IMP]]
  10. [Minimum no. of Jumps to reach end of an array]
  11. find duplicate in an array of N+1 Integers
  12. [Merge 2 sorted arrays without using Extra space.]
  13. Kadane's Algo [V.V.V.V.V IMP]
  14. [Merge Intervals]
  15. [Next Permutation]
  16. [Count Inversion]
  17. Best time to buy and Sell stock
  18. find all pairs on integer array whose sum is equal to given number
  19. find common elements In 3 sorted arrays
  20. Rearrange the array in alternating positive and negative items with O(1) extra space
  21. Find if there is any subarray with sum equal to 0
  22. Find factorial of a large number
  23. find maximum product subarray
  24. Find longest coinsecutive subsequence
  25. Given an array of size n and a number k, fin all elements that appear more than " n/k " times.
  26. Maximum profit by buying and selling a share atmost twice
  27. Find whether an array is a subset of another array
  28. Find the triplet that sum to a given value
  29. Trapping Rain water problem
  30. Chocolate Distribution problem
  31. Smallest Subarray with sum greater than a given value
  32. Three way partitioning of an array around a given value
  33. Minimum swaps required bring elements less equal K together
  34. Minimum no. of operations required to make an array palindrome
  35. Median of 2 sorted arrays of equal size
  36. Median of 2 sorted arrays of different size

Matrix

  1. Spiral traversal on a Matrix
  2. Search an element in a matriix
  3. Find median in a row wise sorted matrix
  4. Find row with maximum no. of 1's
  5. Print elements in sorted order using row-column wise sorted matrix
  6. Maximum size rectangle
  7. Find a specific pair in matrix
  8. Rotate matrix by 90 degrees
  9. Kth smallest element in a row-cpumn wise sorted matrix
  10. Common elements in all rows of a given matrix

String

  1. Reverse a String
  2. Check whether a String is Palindrome or not
  3. Find Duplicate characters in a string
  4. Why strings are immutable in Java?
  5. Write a Code to check whether one string is a rotation of another
  6. Write a Program to check whether a string is a valid shuffle of two strings or not
  7. Count and Say problem
  8. Write a program to find the longest Palindrome in a string.[ Longest palindromic Substring]
  9. Find Longest Recurring Subsequence in String
  10. Print all Subsequences of a string.
  11. Print all the permutations of the given string
  12. Split the Binary string into two substring with equal 0’s and 1’s
  13. Word Wrap Problem [VERY IMP].
  14. EDIT Distance [Very Imp]
  15. Find next greater number with same set of digits. [Very Very IMP]
  16. Balanced Parenthesis problem.[Imp]
  17. Word break Problem[ Very Imp]
  18. Rabin Karp Algo
  19. KMP Algo
  20. Convert a Sentence into its equivalent mobile numeric keypad sequence.
  21. Minimum number of bracket reversals needed to make an expression balanced.
  22. Count All Palindromic Subsequence in a given String.
  23. Count of number of given string in 2D character array
  24. Search a Word in a 2D Grid of characters.
  25. Boyer Moore Algorithm for Pattern Searching.
  26. Converting Roman Numerals to Decimal
  27. Longest Common Prefix
  28. Number of flips to make binary string alternate
  29. Find the first repeated word in string.
  30. Minimum number of swaps for bracket balancing.
  31. Find the longest common subsequence between two strings.
  32. Program to generate all possible valid IP addresses from given string.
  33. Write a program tofind the smallest window that contains all characters of string itself.
  34. Rearrange characters in a string such that no two adjacent are same
  35. Minimum characters to be added at front to make string palindrome
  36. Given a sequence of words, print all anagrams together
  37. Find the smallest window in a string containing all characters of another string
  38. Recursively remove all adjacent duplicates
  39. String matching where one string contains wildcard characters
  40. Function to find Number of customers who could not get a computer
  41. Transform One String to Another using Minimum Number of Given Operation
  42. Check if two given strings are isomorphic to each other
  43. Recursively print all sentences that can be formed from list of word lists

Searching & Sorting

  1. Find first and last positions of an element in a sorted array
  2. Find a Fixed Point (Value equal to index) in a given array
  3. Search in a rotated sorted array
  4. square root of an integer
  5. Maximum and minimum of an array using minimum number of comparisons
  6. Optimum location of point to minimize total distance
  7. Find the repeating and the missing
  8. find majority element
  9. Searching in an array where adjacent differ by at most k
  10. find a pair with a given difference
  11. find four elements that sum to a given value
  12. maximum sum such that no 2 elements are adjacent
  13. Count triplet with sum smaller than a given value
  14. merge 2 sorted arrays
  15. print all subarrays with 0 sum
  16. Product array Puzzle
  17. Sort array according to count of set bits
  18. minimum no. of swaps required to sort the array
  19. Bishu and Soldiers
  20. Rasta and Kheshtak
  21. Kth smallest number again
  22. Find pivot element in a sorted array
  23. K-th Element of Two Sorted Arrays
  24. Aggressive cows
  25. Book Allocation Problem
  26. EKOSPOJ:
  27. Job Scheduling Algo
  28. Missing Number in AP
  29. Smallest number with atleastn trailing zeroes infactorial
  30. Painters Partition Problem:
  31. ROTI-Prata SPOJ
  32. DoubleHelix SPOJ
  33. Subset Sums
  34. Find the inversion count
  35. Implement Merge-sort in-place
  36. Partitioning and Sorting Arrays with Many Repeated Entries

Link List

  1. Write a Program to reverse the Linked List. (Both Iterative and recursive)
  2. Reverse a Linked List in group of Given Size. [Very Imp]
  3. Write a program to Detect loop in a linked list.
  4. Write a program to Delete loop in a linked list.
  5. Find the starting point of the loop. 
  6. Remove Duplicates in a sorted Linked List.
  7. Remove Duplicates in a Un-sorted Linked List.
  8. Write a Program to Move the last element to Front in a Linked List.
  9. Add “1” to a number represented as a Linked List.
  10. Add two numbers represented by linked lists.
  11. Intersection of two Sorted Linked List.
  12. Intersection Point of two Linked Lists.
  13. Merge Sort For Linked lists.[Very Important]
  14. Quicksort for Linked Lists.[Very Important]
  15. Find the middle Element of a linked list.
  16. Check if a linked list is a circular linked list.
  17. Split a Circular linked list into two halves.
  18. Write a Program to check whether the Singly Linked list is a palindrome or not.
  19. Deletion from a Circular Linked List.
  20. Reverse a Doubly Linked list.
  21. Find pairs with a given sum in a DLL.
  22. Count triplets in a sorted DLL whose sum is equal to given value “X”.
  23. Sort a “k”sorted Doubly Linked list.[Very IMP]
  24. Rotate DoublyLinked list by N nodes.
  25. Rotate a Doubly Linked list in group of Given Size.[Very IMP]
  26. Can we reverse a linked list in less than O(n) ?
  27. Why Quicksort is preferred for. Arrays and Merge Sort for LinkedLists ?
  28. Flatten a Linked List
  29. Sort a LL of 0's, 1's and 2's
  30. Clone a linked list with next and random pointer
  31. Merge K sorted Linked list
  32. Multiply 2 no. represented by LL
  33. Delete nodes which have a greater value on right side
  34. Segregate even and odd nodes in a Linked List
  35. Program for n’th node from the end of a Linked List
  36. Find the first non-repeating character from a stream of characters

Binary Trees

  1. level order traversal
  2. Reverse Level Order traversal
  3. Height of a tree
  4. Diameter of a tree
  5. Mirror of a tree
  6. Inorder Traversal of a tree both using recursion and Iteration
  7. Preorder Traversal of a tree both using recursion and Iteration
  8. Postorder Traversal of a tree both using recursion and Iteration
  9. Left View of a tree
  10. Right View of Tree
  11. Top View of a tree
  12. Bottom View of a tree
  13. Zig-Zag traversal of a binary tree
  14. Check if a tree is balanced or not
  15. Diagnol Traversal of a Binary tree
  16. Boundary traversal of a Binary tree
  17. Construct Binary Tree from String with Bracket Representation
  18. Convert Binary tree into Doubly Linked List
  19. Convert Binary tree into Sum tree
  20. Construct Binary tree from Inorder and preorder traversal
  21. Find minimum swaps required to convert a Binary tree into BST
  22. Check if Binary tree is Sum tree or not
  23. Check if all leaf nodes are at same level or not
  24. Check if a Binary Tree contains duplicate subtrees of size 2 or more [ IMP ]
  25. Check if 2 trees are mirror or not
  26. Sum of Nodes on the Longest path from root to leaf node
  27. Check if given graph is tree or not. [ IMP ]
  28. Find Largest subtree sum in a tree
  29. Maximum Sum of nodes in Binary tree such that no two are adjacent
  30. Print all "K" Sum paths in a Binary tree
  31. Find LCA in a Binary tree
  32. Find distance between 2 nodes in a Binary tree
  33. Kth Ancestor of node in a Binary tree
  34. Find all Duplicate subtrees in a Binary tree [ IMP ]
  35. Tree Isomorphism Problem

Binary Search Trees

  1. Fin a value in a BST
  2. Deletion of a node in a BST
  3. Find min and max value in a BST
  4. Find inorder successor and inorder predecessor in a BST
  5. Check if a tree is a BST or not
  6. Populate Inorder successor of all nodes
  7. Find LCA of 2 nodes in a BST
  8. Construct BST from preorder traversal
  9. Convert Binary tree into BST
  10. Convert a normal BST into a Balanced BST
  11. Merge two BST [ V.V.V>IMP ]
  12. Find Kth largest element in a BST
  13. Find Kth smallest element in a BST
  14. Count pairs from 2 BST whose sum is equal to given value "X"
  15. Find the median of BST in O(n) time and O(1) space
  16. Count BST ndoes that lie in a given range
  17. Replace every element with the least greater element on its right
  18. Given "n" appointments, find the conflicting appointments
  19. Check preorder is valid or not
  20. Check whether BST contains Dead end
  21. Largest BST in a Binary Tree [ V.V.V.V.V IMP ]
  22. Flatten BST to sorted list

Greedy

  1. Activity Selection Problem c
  2. Job SequencingProblem
  3. Huffman Coding
  4. Water Connection Problem
  5. Fractional Knapsack Problem
  6. Greedy Algorithm to find Minimum number of Coins
  7. Maximum trains for which stoppage can be provided
  8. Minimum Platforms Problem
  9. Buy Maximum Stocks if i stocks can be bought on i-th day
  10. Find the minimum and maximum amount to buy all N candies
  11. Minimize Cash Flow among a given set of friends who have borrowed money from each other
  12. Minimum Cost to cut a board into squares
  13. Check if it is possible to survive on Island
  14. Find maximum meetings in one room
  15. Maximum product subset of an array
  16. Maximize array sum after K negations
  17. Maximize the sum of arr[i]*i
  18. Maximum sum of absolute difference of an array
  19. Maximize sum of consecutive differences in a circular array
  20. Minimum sum of absolute difference of pairs of two arrays
  21. Program for Shortest Job First (or SJF) CPU Scheduling
  22. Program for Least Recently Used (LRU) Page Replacement algorithm
  23. Smallest subset with sum greater than all other elements
  24. Chocolate Distribution Problem
  25. DEFKIN -Defense of a Kingdom
  26. DIEHARD -DIE HARD
  27. GERGOVIA -Wine trading in Gergovia
  28. Picking Up Chicks
  29. CHOCOLA –Chocolate
  30. ARRANGE -Arranging Amplifiers
  31. K Centers Problem
  32. Minimum Cost of ropes
  33. Find smallest number with given number of digits and sum of digits
  34. Rearrange characters in a string such that no two adjacent are same
  35. Find maximum sum possible equal sum of three stacks

BackTracking

  1. Rat in a maze Problem
  2. Printing all solutions in N-Queen Problem
  3. Word Break Problem using Backtracking
  4. Remove Invalid Parentheses
  5. Sudoku Solver
  6. m Coloring Problem
  7. Print all palindromic partitions of a string
  8. Subset Sum Problem
  9. The Knight’s tour problem
  10. Tug of War
  11. Find shortest safe route in a path with landmines
  12. Combinational Sum
  13. Find Maximum number possible by doing at-most K swaps
  14. Print all permutations of a string
  15. Find if there is a path of more than k length from a source
  16. Longest Possible Route in a Matrix with Hurdles
  17. Print all possible paths from top left to bottom right of a mXn matrix
  18. Partition of a set intoK subsets with equal sum
  19. Find the K-th Permutation Sequence of first N natural numbers

Stacks & Queues

  1. Implement Stack from Scratch
  2. Implement Queue from Scratch
  3. Implement 2 stack in an array
  4. find the middle element of a stack
  5. Implement "N" stacks in an Array
  6. Check the expression has valid or Balanced parenthesis or not.
  7. Reverse a String using Stack
  8. Design a Stack that supports getMin() in O(1) time and O(1) extra space.
  9. Find the next Greater element
  10. The celebrity Problem
  11. Arithmetic Expression evaluation
  12. Evaluation of Postfix expression
  13. Implement a method to insert an element at its bottom without using any other data structure.
  14. Reverse a stack using recursion
  15. Sort a Stack using recursion
  16. Merge Overlapping Intervals
  17. Largest rectangular Area in Histogram
  18. Length of the Longest Valid Substring
  19. Expression contains redundant bracket or not
  20. Implement Stack using Queue
  21. Implement Stack using Deque
  22. Stack Permutations (Check if an array is stack permutation of other)
  23. Implement Queue using Stack
  24. Implement "n" queue in an array
  25. Implement a Circular queue
  26. LRU Cache Implementationa
  27. Reverse a Queue using recursion
  28. Reverse the first “K” elements of a queue
  29. Interleave the first half of the queue with second half
  30. Find the first circular tour that visits all Petrol Pumps
  31. Minimum time required to rot all oranges
  32. Distance of nearest cell having 1 in a binary matrix
  33. First negative integer in every window of size “k”
  34. Check if all levels of two trees are anagrams or not.
  35. Sum of minimum and maximum elements of all subarrays of size “k”.
  36. Minimum sum of squares of character counts in a given string after removing “k” characters.
  37. Queue based approach or first non-repeating character in a stream.
  38. Next Smaller Element

Heap

  1. Implement a Maxheap/MinHeap using arrays and recursion.
  2. Sort an Array using heap. (HeapSort)
  3. Maximum of all subarrays of size k.
  4. “k” largest element in an array
  5. Kth smallest and largest element in an unsorted array
  6. Merge “K” sorted arrays. [ IMP ]
  7. Merge 2 Binary Max Heaps
  8. Kth largest sum continuous subarrays
  9. Leetcode- reorganize strings
  10. Merge “K” Sorted Linked Lists [V.IMP]
  11. Smallest range in “K” Lists
  12. Median in a stream of Integers
  13. Check if a Binary Tree is Heap
  14. Connect “n” ropes with minimum cost
  15. Convert BST to Min Heap
  16. Convert min heap to max heap
  17. Rearrange characters in a string such that no two adjacent are same.
  18. Minimum sum of two numbers formed from digits of an array

Graph

  1. Create a Graph, print it
  2. Implement BFS algorithm
  3. Implement DFS Algo
  4. Detect Cycle in Directed Graph using BFS/DFS Algo
  5. Detect Cycle in UnDirected Graph using BFS/DFS Algo
  6. Search in a Maze
  7. Minimum Step by Knight
  8. flood fill algo
  9. Clone a graph
  10. Making wired Connections
  11. word Ladder
  12. Dijkstra algo
  13. Implement Topological Sort
  14. Minimum time taken by each job to be completed given by a Directed Acyclic Graph
  15. Find whether it is possible to finish all tasks or not from given dependencies
  16. Find the no. of Isalnds
  17. Given a sorted Dictionary of an Alien Language, find order of characters
  18. Implement Kruksal’sAlgorithm
  19. Implement Prim’s Algorithm
  20. Total no. of Spanning tree in a graph
  21. Implement Bellman Ford Algorithm
  22. Implement Floyd warshallAlgorithm
  23. Travelling Salesman Problem
  24. Graph ColouringProblem
  25. Snake and Ladders Problem
  26. Find bridge in a graph
  27. Count Strongly connected Components(Kosaraju Algo)
  28. Check whether a graph is Bipartite or Not\
  29. Detect Negative cycle in a graph
  30. Longest path in a Directed Acyclic Graph
  31. Journey to the Moon
  32. Cheapest Flights Within K Stops
  33. Oliver and the Game
  34. Water Jug problem using BFS
  35. Find if there is a path of more thank length from a source
  36. M-ColouringProblem
  37. Minimum edges to reverse o make path from source to destination
  38. Paths to travel each nodes using each edge(Seven Bridges)
  39. Vertex Cover Problem
  40. Chinese Postman or Route Inspection
  41. Number of Triangles in a Directed and Undirected Graph
  42. Minimise the cashflow among a given set of friends who have borrowed money from each other
  43. Two Clique Problem

Trie

  1. Construct a trie from scratch
  2. Find shortest unique prefix for every word in a given list
  3. Word Break Problem | (Trie solution)
  4. Given a sequence of words, print all anagrams together
  5. Implement a Phone Directory
  6. Print unique rows in a given boolean matrix

DP

  1. Coin ChangeProblem
  2. Kapsack Problem
  3. Binomial CoefficientProblem
  4. Permutation CoefficientProblem
  5. Program for nth Catalan Number
  6. Matrix Chain Multiplication 
  7. Edit Distance
  8. Subset Sum Problem
  9. Friends Pairing Problem
  10. Gold Mine Problem
  11. Assembly Line SchedulingProblem
  12. Painting the Fenceproblem
  13. Maximize The Cut Segments
  14. Longest Common Subsequence
  15. Longest Repeated Subsequence
  16. Longest Increasing Subsequence
  17. Space Optimized Solution of LCS
  18. LCS (Longest Common Subsequence) of three strings
  19. Maximum Sum Increasing Subsequence
  20. Count all subsequences having product less than K
  21. Longest subsequence such that difference between adjacent is one
  22. Maximum subsequence sum such that no three are consecutive
  23. Egg Dropping Problem
  24. Maximum Length Chain of Pairs
  25. Maximum size square sub-matrix with all 1s
  26. Maximum sum of pairs with specific difference
  27. Min Cost PathProblem
  28. Maximum difference of zeros and ones in binary string
  29. Minimum number of jumps to reach end
  30. Minimum cost to fill given weight in a bag
  31. Minimum removals from array to make max –min <= K
  32. Longest Common Substring
  33. Count number of ways to reacha given score in a game
  34. Count Balanced Binary Trees of Height h
  35. LargestSum Contiguous Subarray [V>V>V>V IMP ]
  36. Smallest sum contiguous subarray
  37. Unbounded Knapsack (Repetition of items allowed)
  38. Word Break Problem
  39. Largest Independent Set Problem
  40. Partition problem
  41. Longest Palindromic Subsequence
  42. Count All Palindromic Subsequence in a given String
  43. Longest Palindromic Substring
  44. Longest alternating subsequence
  45. Weighted Job Scheduling
  46. Coin game winner where every player has three choices
  47. Count Derangements (Permutation such that no element appears in its original position) [ IMPORTANT ]
  48. Maximum profit by buying and selling a share at most twice [ IMP ]
  49. Optimal Strategy for a Game
  50. Optimal Binary Search Tree
  51. Palindrome PartitioningProblem
  52. Word Wrap Problem
  53. Mobile Numeric Keypad Problem [ IMP ]
  54. Boolean Parenthesization Problem
  55. Largest rectangular sub-matrix whose sum is 0
  56. Largest area rectangular sub-matrix with equal number of 1’s and 0’s [ IMP ]
  57. Maximum sum rectangle in a 2D matrix
  58. Maximum profit by buying and selling a share at most k time
  59. Find if a string is interleaved of two other strings
  60. Maximum Length of Pair Chain

Bit Manipulation

  1. Count set bits in an integer
  2. Find the two non-repeating elements in an array of repeating elements
  3. Count number of bits to be flipped to convert A to B
  4. Count total set bits in all numbers from 1 to n
  5. Program to find whether a no is power of two
  6. Find position of the only set bit
  7. Copy set bits in a range
  8. Divide two integers without using multiplication, division and mod operator
  9. Calculate square of a number without using *, / and pow()
  10. Power Set