Most Asked DSA Interview Programs Solved in Python

Array Programs

  1. Reverse an array
  2. Find the maximum and minimum elements in an array
  3. Find the Kth maximum and minimum elements in an array
  4. Sort an array containing only 0, 1, and 2 without using a standard sorting algorithm
  5. Move all negative elements to one side of an array
  6. Find the union and intersection of two sorted arrays
  7. Cyclically rotate an array by one position
  8. Find the largest sum contiguous subarray in an array
  9. Minimize the maximum difference between heights in an array
  10. Find the minimum number of jumps to reach the end of an array
  11. Detect duplicates in an array of N+1 integers
  12. Merge two sorted arrays without using extra space
  13. Apply Kadane’s algorithm on an array for the maximum sum subarray
  14. Merge overlapping intervals in an array
  15. Generate the next permutation of an array
  16. Count inversions in an array
  17. Determine the best time to buy and sell stock using an array
  18. Find all pairs in an array whose sum equals a given number
  19. Find common elements in three sorted arrays
  20. Rearrange an array in alternating positive and negative order with O(1) extra space
  21. Check if any subarray within an array has a sum equal to 0
  22. Calculate the factorial of a large number using an array
  23. Find the maximum product subarray in an array
  24. Identify the longest consecutive subsequence in an array
  25. Find all elements in an array that appear more than n/k times
  26. Calculate maximum profit by buying and selling stock at most twice using an array
  27. Check whether one array is a subset of another array
  28. Find a triplet in an array that sums to a given value
  29. Solve the trapping rain water problem using an array
  30. Solve the chocolate distribution problem using an array
  31. Find the smallest subarray in an array with a sum greater than a given value
  32. Partition an array into three parts around a given value
  33. Find the minimum swaps required to bring elements less than or equal to a given value together in an array
  34. Determine the minimum operations required to make an array a palindrome
  35. Find the median of two sorted arrays of equal size
  36. Find the median of two sorted arrays of different sizes

Searching and Sorting Programs

  1. Search in a rotated sorted array
  2. Find the repeating and missing elements in an array
  3. Find first and last positions of an element in a sorted array
  4. Find a fixed point (value equal to index) in an array
  5. Find the square root of an integer
  6. Find the maximum and minimum of an array using minimum comparisons
  7. Find the optimum location of a point to minimize total distance
  8. Find the majority element in an array
  9. Search in an array where adjacent elements differ by at most k
  10. Find a pair in an array with a given difference
  11. Find four elements in an array that sum to a given value
  12. Find the maximum sum in an array such that no two elements are adjacent
  13. Count triplets in an array with a sum smaller than a given value
  14. Merge two sorted arrays
  15. Print all subarrays with zero sum
  16. Solve the product array puzzle
  17. Sort an array according to the count of set bits
  18. Find the minimum number of swaps required to sort an array
  19. Solve the “Bishu and Soldiers” problem
  20. Solve the “Rasta and Kheshtak” problem
  21. Find the kth smallest number in an array
  22. Find the pivot element in a sorted array
  23. Find the kth element of two sorted arrays
  24. Solve the “Aggressive Cows” problem
  25. Solve the Book Allocation problem
  26. Solve the EKOSPOJ problem
  27. Implement a job scheduling algorithm
  28. Find the missing number in an arithmetic progression
  29. Find the smallest number with at least n trailing zeroes in factorial
  30. Solve the Painters Partition problem
  31. Solve the ROTI-Prata SPOJ problem
  32. Solve the Double Helix SPOJ problem
  33. Solve the Subset Sums problem
  34. Find the inversion count in an array
  35. Implement merge sort in-place
  36. Partition and sort arrays with many repeated entries

Matrix Programs

  1. Spiral traversal of a matrix
  2. Search for an element in a matrix
  3. Find the median in a row-wise sorted matrix
  4. Find the row with the maximum number of 1’s in a matrix
  5. Print elements in sorted order using a row-column wise sorted matrix
  6. Find the maximum size rectangle in a matrix
  7. Find a specific pair in a matrix
  8. Rotate a matrix by 90 degrees
  9. Find the kth smallest element in a row-column wise sorted matrix
  10. Find common elements in all rows of a matrix

String Programs

  1. Reverse a string
  2. Check whether a string is a palindrome
  3. Find duplicate characters in a string
  4. Why are strings immutable in Java?
  5. Check whether one string is a rotation of another
  6. Check whether a string is a valid shuffle of two strings
  7. Count and say problem
  8. Find the longest palindrome in a string (Longest Palindromic Substring)
  9. Find longest recurring subsequence in a string
  10. Print all subsequences of a string
  11. Print all permutations of a string
  12. Split a binary string into two substrings with equal 0’s and 1’s
  13. Solve the word wrap problem
  14. Solve the edit distance problem
  15. Find the next greater number with the same set of digits
  16. Solve the balanced parenthesis problem
  17. Solve the word break problem
  18. Implement the Rabin-Karp algorithm
  19. Implement the KMP algorithm
  20. Convert a sentence into its equivalent mobile numeric keypad sequence
  21. Find the minimum number of bracket reversals needed to balance an expression
  22. Count all palindromic subsequences in a string
  23. Count the occurrences of a given string in a 2D character array
  24. Search for a word in a 2D grid of characters
  25. Implement the Boyer-Moore algorithm for pattern searching
  26. Convert Roman numerals to decimal
  27. Find the longest common prefix among strings
  28. Count the number of flips needed to make a binary string alternate
  29. Find the first repeated word in a string
  30. Find the minimum number of swaps required for bracket balancing
  31. Find the longest common subsequence between two strings
  32. Generate all possible valid IP addresses from a given string
  33. Find the smallest window that contains all characters of the string
  34. Rearrange characters in a string so that no two adjacent are the same
  35. Find the minimum characters to add at the front to make a string palindrome
  36. Print all anagrams together from a sequence of words
  37. Find the smallest window in a string containing all characters of another string
  38. Recursively remove all adjacent duplicates in a string
  39. Perform string matching with wildcard characters
  40. Find the number of customers who could not get a computer
  41. Transform one string to another using the minimum number of operations
  42. Check if two given strings are isomorphic
  43. Recursively print all sentences that can be formed from a list of word lists

LinkedList Programs

  1. Reverse a linked list (Iterative and Recursive)
  2. Reverse a linked list in groups of given size
  3. Detect a loop in a linked list
  4. Delete a loop in a linked list
  5. Find the starting point of a loop in a linked list
  6. Remove duplicates in a sorted linked list
  7. Remove duplicates in an unsorted linked list
  8. Move the last element to the front of a linked list
  9. Add 1 to a number represented as a linked list
  10. Add two numbers represented by linked lists
  11. Find the intersection of two sorted linked lists
  12. Find the intersection point of two linked lists
  13. Merge sort for linked lists
  14. Quicksort for linked lists
  15. Find the middle element of a linked list
  16. Check if a linked list is circular
  17. Split a circular linked list into two halves
  18. Check if a singly linked list is a palindrome
  19. Delete a node from a circular linked list
  20. Reverse a doubly linked list
  21. Find pairs with a given sum in a doubly linked list
  22. Sort a k-sorted doubly linked list
  23. Rotate a doubly linked list by N nodes
  24. Rotate a doubly linked list in groups of given size
  25. Can we reverse a linked list in less than O(n)?
  26. Why is quicksort preferred for arrays and merge sort for linked lists?
  27. Flatten a linked list
  28. Sort a linked list of 0’s, 1’s, and 2’s
  29. Merge k sorted linked lists
  30. Multiply two numbers represented by linked lists
  31. Count triplets in a sorted doubly linked list whose sum equals a given value
  32. Clone a linked list with next and random pointers
  33. Delete nodes that have a greater value on the right side
  34. Segregate even and odd nodes in a linked list
  35. Find the nth node from the end of a linked list
  36. Find the first non-repeating character from a stream of characters

Binary Trees

  1. Preorder traversal of a binary tree (recursive and iterative)
  2. Postorder traversal of a binary tree (recursive and iterative)
  3. Level order traversal of a binary tree
  4. Reverse level order traversal of a binary tree
  5. Height of a binary tree
  6. Diameter of a binary tree
  7. Mirror of a binary tree
  8. Inorder traversal of a binary tree (recursive and iterative)
  9. Left view of a binary tree
  10. Right view of a binary tree
  11. Top view of a binary tree
  12. Bottom view of a binary tree
  13. Zigzag traversal of a binary tree
  14. Check if a binary tree is balanced
  15. Diagonal traversal of a binary tree
  16. Boundary traversal of a binary tree
  17. Construct a binary tree from a string with bracket representation
  18. Convert a binary tree into a doubly linked list
  19. Convert a binary tree into a sum tree
  20. Construct a binary tree from inorder and preorder traversals
  21. Find minimum swaps required to convert a binary tree into a BST
  22. Check if a binary tree is a sum tree
  23. Check if all leaf nodes are at the same level in a binary tree
  24. Find the lowest common ancestor (LCA) in a binary tree
  25. Solve the tree isomorphism problem
  26. Check if a binary tree contains duplicate subtrees of size 2 or more
  27. Check if two binary trees are mirror images of each other
  28. Calculate the sum of nodes on the longest path from root to leaf
  29. Verify if a given graph is a tree
  30. Find the largest subtree sum in a binary tree
  31. Find the maximum sum of nodes in a binary tree such that no two are adjacent
  32. Print all paths in a binary tree with a given sum
  33. Find the distance between two nodes in a binary tree
  34. Find the kth ancestor of a node in a binary tree
  35. Find all duplicate subtrees in a binary tree

Binary Search Trees

  1. Find a value in a BST
  2. Delete a node in a BST
  3. Find the minimum and maximum values in a BST
  4. Find the inorder successor and inorder predecessor in a BST
  5. Check if a tree is a BST
  6. Populate the inorder successor for all nodes in a BST
  7. Find the lowest common ancestor (LCA) of two nodes in a BST
  8. Construct a BST from a preorder traversal
  9. Convert a binary tree into a BST
  10. Convert a BST into a balanced BST
  11. Merge two BSTs
  12. Find the kth largest element in a BST
  13. Find the kth smallest element in a BST
  14. Count pairs from two BSTs whose sum is equal to a given value
  15. Find the median of a BST in O(n) time and O(1) space
  16. Replace every element with the least greater element on its right
  17. Find conflicting appointments given n appointments using a BST approach
  18. Flatten a BST into a sorted list
  19. Count BST nodes that lie within a given range
  20. Check if a preorder traversal is valid for a BST
  21. Check whether a BST contains a dead end
  22. Find the largest BST within a binary tree

Greedy Algorithm Problems

  1. Find the minimum and maximum amount to buy all N candies
  2. Minimize cash flow among a given set of friends who have borrowed money from each other
  3. Minimum cost to cut a board into squares
  4. Check if it is possible to survive on an island
  5. Activity Selection Problem
  6. Job Sequencing Problem
  7. Huffman Coding
  8. Water Connection Problem
  9. Fractional Knapsack Problem
  10. Find the minimum number of coins (coin change problem)
  11. Maximum trains for which stoppage can be provided
  12. Minimum Platforms Problem
  13. Buy maximum stocks if i stocks can be bought on i-th day
  14. 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 differences of pairs of two arrays
  21. Shortest Job First (SJF) CPU Scheduling
  22. 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. ARRANGE – Arranging Amplifiers
  27. K Centers Problem
  28. Minimum cost of ropes
  29. Find maximum sum possible from equal sum of three stacks
  30. Find the smallest number with a given number of digits and sum of digits
  31. Rearrange characters in a string such that no two adjacent are the same

Back Tracking Programs

  1. Rat in a Maze Problem
  2. Printing All Solutions for the 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 the Shortest Safe Route in a Path with Landmines
  12. Combination Sum
  13. Find the Maximum Number Possible by Doing At-Most K Swaps
  14. Print All Permutations of a String
  15. Find if There Is a Path Longer Than K from a Given Source
  16. Longest Possible Route in a Matrix with Hurdles
  17. Print All Possible Paths from Top Left to Bottom Right in an m×n Matrix
  18. Partition a Set into K Subsets with Equal Sum
  19. Find the K-th Permutation Sequence of the First N Natural Numbers

Stacks and Queues Programs

  1. Implement a stack from scratch
  2. Implement a queue from scratch
  3. Implement two stacks in an array
  4. Find the middle element of a stack
  5. Implement N stacks in an array
  6. Check if an expression has valid (balanced) parentheses
  7. Reverse a string using a stack
  8. Design a stack that supports getMin() in O(1) time and O(1) extra space
  9. Find the next greater element using a stack
  10. Solve the celebrity problem using stacks/queues
  11. Evaluate an arithmetic expression using a stack
  12. Evaluate a postfix expression
  13. Insert an element at the bottom of a stack without using any additional data structure
  14. Reverse a stack using recursion
  15. Sort a stack using recursion
  16. Merge overlapping intervals using a stack
  17. Find the largest rectangular area in a histogram
  18. Find the length of the longest valid substring
  19. Check if an expression contains redundant brackets
  20. Implement a stack using a queue
  21. Implement a stack using a deque
  22. Check if one array is a valid stack permutation of another
  23. Implement a queue using a stack
  24. Implement N queues in an array
  25. Implement a circular queue
  26. Implement an LRU cache
  27. Reverse a queue using recursion
  28. Reverse the first K elements of a queue
  29. Interleave the first half of a queue with the second half
  30. Find the first circular tour that visits all petrol pumps
  31. Find the minimum time required to rot all oranges
  32. Find the distance of the nearest cell having 1 in a binary matrix
  33. Find the first negative integer in every window of size K
  34. Check if all levels of two trees are anagrams
  35. Calculate the sum of the minimum and maximum elements of all subarrays of size K
  36. Calculate the minimum sum of squares of character counts in a string after removing K characters
  37. Find the next smaller element using a queue-based approach

Heap Programs

  1. Implement a max heap/min heap using arrays and recursion
  2. Heap sort an array using a heap
  3. Find the maximum of all subarrays of size k using a heap
  4. Find the k largest elements in an array using a heap
  5. Find the kth smallest and kth largest element in an unsorted array using a heap
  6. Merge k sorted arrays using a heap [IMP]
  7. Merge 2 binary max heaps
  8. Find the kth largest sum of continuous subarrays using a heap
  9. Reorganize strings using a heap (Leetcode)
  10. Merge k sorted linked lists using a heap [V.IMP]
  11. Find the smallest range in k lists using a heap
  12. Find the median in a stream of integers using a heap
  13. Check if a binary tree is a heap
  14. Convert a BST to a min heap
  15. Convert a min heap to a max heap
  16. Find the minimum sum of two numbers formed from digits of an array using a heap
  17. Rearrange characters in a string such that no two adjacent characters are the same using a heap

Graph Programs

  1. Create a graph and print it
  2. Implement BFS algorithm
  3. Implement DFS algorithm
  4. Detect cycle in a directed graph using BFS/DFS
  5. Detect cycle in an undirected graph using BFS/DFS
  6. Search in a maze
  7. Find the minimum steps for a knight
  8. Flood fill algorithm
  9. Clone a graph
  10. Making wired connections
  11. Word ladder
  12. Dijkstra algorithm
  13. Implement topological sort
  14. Find the minimum time to complete each job in a DAG
  15. Determine if it is possible to finish all tasks given dependencies
  16. Count the number of islands
  17. Given a sorted dictionary of an alien language, determine the order of characters
  18. Implement Kruskal’s algorithm
  19. Implement Prim’s algorithm
  20. Count the total number of spanning trees in a graph
  21. Implement Bellman-Ford algorithm
  22. Implement Floyd-Warshall algorithm
  23. Travelling Salesman Problem
  24. Graph colouring problem
  25. Snake and Ladders problem
  26. Find bridges in a graph
  27. Count strongly connected components (Kosaraju algorithm)
  28. Check if a graph is bipartite
  29. Detect a negative cycle in a graph
  30. Find the 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 longer than K from a given source
  36. m-Colouring problem
  37. Find the minimum edges to reverse to make a path from source to destination
  38. Find paths that traverse each node using every edge (Seven Bridges problem)
  39. Vertex Cover problem
  40. Chinese Postman (Route Inspection) problem
  41. Count the number of triangles in a graph (directed and undirected)
  42. Minimize cash flow among a set of friends who have borrowed money
  43. Two Clique problem

Dynamic Programming Programs

  1. Knapsack Problem
  2. Binomial Coefficient Problem
  3. Permutation Coefficient Problem
  4. nth Catalan Number
  5. Matrix Chain Multiplication
  6. Edit Distance
  7. Subset Sum Problem
  8. Coin Change Problem
  9. Friends Pairing Problem
  10. Gold Mine Problem
  11. Assembly Line Scheduling Problem
  12. Painting the Fence Problem
  13. Maximize the Cut Segments
  14. Longest Common Subsequence (LCS)
  15. Longest Repeated Subsequence
  16. Longest Increasing Subsequence
  17. Space-Optimized LCS
  18. LCS of Three Strings
  19. Maximum Sum Increasing Subsequence
  20. Count All Subsequences with Product Less Than K
  21. Longest Subsequence with Adjacent Difference of One
  22. Maximum Subsequence Sum with No Three Consecutive Elements
  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. Minimum Cost Path Problem
  28. Maximum Difference of Zeros and Ones in a Binary String
  29. Minimum Number of Jumps to Reach the End
  30. Minimum Cost to Fill a Given Weight in a Bag
  31. Minimum Removals from an Array to Make Max – Min ≤ K
  32. Longest Common Substring
  33. Count the Number of Ways to Reach a Given Score in a Game
  34. Count Balanced Binary Trees of Height h
  35. Largest Sum Contiguous Subarray
  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 Subsequences in a String
  43. Longest Palindromic Substring
  44. Longest Alternating Subsequence
  45. Weighted Job Scheduling
  46. Coin Game Winner (Each Player Has Three Choices)
  47. Count Derangements (Permutations with No Element in Its Original Position)
  48. Maximum Profit by Buying and Selling a Share at Most Twice
  49. Optimal Strategy for a Game
  50. Optimal Binary Search Tree
  51. Palindrome Partitioning Problem
  52. Word Wrap Problem
  53. Mobile Numeric Keypad Problem
  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
  57. Maximum Sum Rectangle in a 2D Matrix
  58. Maximum Profit by Buying and Selling a Share at Most k Times
  59. Find if a String is an Interleaving of Two Other Strings
  60. Maximum Length of Pair Chain

Bit Manipulation Programs

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