Source : https://techiedelight.quora.com/500-Data-structures-and-algorithms-interview-questions-and-their-solutions

**Array**

Find pair with given sum in the array

Find sub-array with 0 sum

Sort binary array in linear time

Find a duplicate element in a limited range array

Find largest sub-array formed by consecutive integers

Find maximum length sub-array having given sum

Find maximum length sub-array having equal number of 0’s and 1’s

Sort an array containing 0’s, 1’s and 2’s(Dutch national flag problem)

Inplace merge two sorted arrays

Merge two arrays by satisfying given constraints

Find index of 0 to replaced to get maximum length sequence of continuous ones

Find maximum product of two integers in an array

Shuffle a given array of elements (Fisher–Yates shuffle)

Rearrange the array with alternate high and low elements

Find equilibrium index of an array

Find majority element in an array (Boyer–Moore majority vote algorithm)

Move all zeros present in the array to the end

Replace each element of array with product of every other element without using / operator

Find Longest Bitonic Subarray in an array

Find maximum difference between two elements in the array by satisfying given constraints

Maximum subarray problem (Kadane’s algorithm)

Maximum Sum Circular Subarray

Find all distinct combinations of given length

Find all distinct combinations of given length with repetition allowed

Find maximum sequence of continuous 1’s formed by replacing at-most k zeroes by ones

Find minimum sum subarray of given size k

Find subarray having given sum in given array of integers

Find the length of smallest subarray whose sum of elements is greater than the given number

Find largest number possible from set of given numbers

Find the smallest window in array sorting which will make the entire array sorted

Find maximum sum path involving elements of given arrays

Maximum profit earned by buying and selling shares any number of times

Trapping Rain Water within given set of bars

Longest Increasing Subsequence

Find maximum product subarray in a given array

Find maximum sum of subsequence with no adjacent elements

Find minimum platforms needed in the station so to avoid any delay in arrival of any train

Length of longest continuous sequence with same sum in given binary arrays

Merging Overlapping Intervals

Activity Selection Problem

Job Sequencing Problem with Deadlines

Introduction to Priority Queues using Binary Heaps

Min Heap and Max Heap Implementation in C++

Heap Sort (Out-of-place and In-place implementation in C++ and C)

Check if given array represents min heap or not

Convert Max Heap to Min Heap in linear time

Find K’th largest element in an array

Sort a K-Sorted Array

Merge M sorted lists of variable length

Find K’th smallest element in an array

Find smallest range with at-least one element from each of the given lists

Merge M sorted lists each containing N elements

Insertion sort | Iterative & Recursive

Selection sort | Iterative & Recursive

Bubble sort | Iterative & Recursive

Merge Sort

Quicksort

Iterative Implementation of Quicksort

Hybrid QuickSort

External merge sort

Custom Sort | Sort elements by their frequency and Index

Custom Sort | Sort elements of the array by order of elements defined by the second array

Inversion Count of an array

Segregate positive and negative integers in linear time

Binary Search

Ternary Search vs Binary search

Interpolation search

Exponential search

Find number of rotations in a circularly sorted array

Search an element in a circular sorted array

Find first or last occurrence of a given number in a sorted array

Count occurrences of a number in a sorted array with duplicates

Find smallest missing element from a sorted array

Find Floor and Ceil of a number in a sorted array

Search in a nearly sorted array in O(logn) time

Find number of 1’s in a sorted binary array

Find the peak element in an array

Maximum Sum Subarray using Divide & Conquer

Find Minimum and Maximum element in an array using minimum comparisons

Matrix Chain Multiplication

0-1 Knapsack problem

Maximize value of the expression A[s] – A[r] + A[q] – A[p] where s > r > q > p

Partition problem

Subset sum problem

Minimum Sum Partition problem

Rod Cutting

Coin change-making problem (unlimited supply of coins)

Coin Change Problem – Find total number of ways to get the denomination of coins

Longest alternating subsequence

Combinations of words formed by replacing given numbers with corresponding English alphabets

Decode the given sequence to construct minimum number without repeated digits

All combinations of elements satisfiying given constraints

**Backtracking**

Print all possible solutions to N Queens problem

Print all Possible Knight’s Tours in a chessboard

Magnet Puzzle

Find Shortest Path in Maze

Find Longest Possible Route in a Matrix

Find path from source to destination in a matrix that satisfies given constraints

Find total number of unique paths in a maze from source to destination

Print All Hamiltonian Path present in a graph

Print all k-colorable configurations of the graph (Vertex coloring of graph)

Find all Permutations of a given string

All combinations of elements satisfiying given constraints

Find all binary strings that can be formed from given wildcard pattern

**Binary**

Bit Hacks – Part 1 (Basic)

Bit Hacks – Part 2 (Playing with k’th bit)

Bit Hacks – Part 3 (Playing with rightmost set bit of a number)

Bit Hacks – Part 4 (Playing with letters of English alphabet)

Bit Hacks – Part 5 (Find absolute value of an integer without branching)

Bit Hacks – Part 6 (Random Problems)

Brian Kernighan’s Algorithm to count set bits in an integer

Compute parity of a number using lookup table

Count set bits using lookup table

Find the minimum or maximum of two integers without using branching

Multiply 16-bit integers using 8-bit multiplier

Round up to the next highest power of 2

Round up to the previous power of 2

Swap individual bits at given position in an integer

Reverse Bits of a given Integer

Generate binary numbers between 1 to N

Efficiently implement power function | Recursive and Iterative

Find square of a number without using multiplication and division operator | 3 methods

Generate power set of a given set

Huffman Coding

**Binary Tree**

Check if two given binary trees are identical or not | Iterative & Recursive

Calculate height of a binary tree | Iterative & Recursive

Delete given Binary Tree | Iterative & Recursive

Inorder Tree Traversal | Iterative & Recursive

Preorder Tree Traversal | Iterative & Recursive

Postorder Tree Traversal | Iterative & Recursive

Level Order Traversal of Binary Tree

Spiral Order Traversal of Binary Tree

Reverse Level Order Traversal of Binary Tree

Print all nodes of a given binary tree in specific order

Print left view of binary tree

Print Bottom View of Binary Tree

Print Top View of Binary Tree

Find next node in same level for given node in a binary tree

Check if given binary tree is complete binary tree or not

Determine if given two nodes are cousins of each other

Print cousins of given node in a binary tree

In-place convert given binary tree to its sum tree

Check if given binary tree is a sum tree or not

Combinations of words formed by replacing given numbers with corresponding English alphabets

Determine if given binary tree is a subtree of another binary tree or not

Find diameter of a binary tree

Check if given binary Tree has symmetric structure or not

Convert binary tree to its mirror

Check if binary tree can be converted to another by doing any no. of swaps of left & right child

Find Lowest Common Ancestor (LCA) of two nodes in a binary tree

Print all paths from root to leaf nodes in given binary tree

Find ancestors of given node in a Binary Tree

Find the distance between given pairs of nodes in a binary tree

Find Vertical Sum in a given Binary Tree

Print nodes in vertical order of a given Binary Tree (Vertical Traversal)

Find the diagonal sum of given binary tree

Print Diagonal Traversal of Binary Tree

Print corner nodes of every level in binary tree

In-place convert convert given Binary Tree to Doubly Linked List

Sink nodes containing zero to the bottom of the binary tree

Convert given binary tree to full tree by removing half nodes

Truncate given binary tree to remove nodes which lie on a path having sum less than K

Find maximum sum root-to-leaf path in a binary tree

Check if given binary tree is height balanced or not

Determine if given Binary Tree is a BST or not

**Binary Search Tree (BST)**

Insertion in BST

Search given key in BST

Deletion from BST

Construct balanced BST from given keys

Determine if given Binary Tree is a BST or not

Check if given keys represents same BSTs or not without building the BST

Find inorder predecessor for given key in a BST

Find Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree

Find K’th smallest and K’th largest element in BST

Floor and Ceil in a Binary Search Tree

Find optimal cost to construct binary search tree

**Divide & Conquer**

Binary Search

Ternary Search vs Binary search

Exponential search

Interpolation search

Find number of rotations in a circularly sorted array

Search an element in a circular sorted array

Find first or last occurrence of a given number in a sorted array

Count occurrences of a number in a sorted array with duplicates

Find smallest missing element from a sorted array

Find Floor and Ceil of a number in a sorted array

Search in a nearly sorted array in O(logn) time

Find number of 1’s in a sorted binary array

Find the peak element in an array

Maximum Sum Subarray using Divide & Conquer

Find Minimum and Maximum element in an array using minimum comparisons

Efficiently implement power function | Recursive and Iterative

Merge Sort

Merge Sort for Singly Linked List

Inversion Count of an array

Quicksort

Iterative Implementation of Quicksort

Hybrid QuickSort

**Dynamic Programming**

Introduction to Dynamic Programming

Longest Common Subsequence | Introduction & LCS Length

Longest Common Subsequence | Space optimized version

Longest Common Subsequence of K-sequences

Longest Common Subsequence | Finding all LCS

Longest Common Substring problem

Longest Palindromic Subsequence using Dynamic Programming

Longest Repeated Subsequence problem

Shortest Common Supersequence | Introduction & SCS Length

Shortest Common Supersequence | Finding all SCS

Shortest Common Supersequence | Using LCS

Longest Increasing Subsequence using Dynamic Programming

Longest Bitonic Subsequence

Increasing Subsequence with Maximum Sum

The Levenshtein distance (Edit distance) problem

Find size of largest square sub-matrix of 1’s present in given binary matrix

Matrix Chain Multiplication

Find the minimum cost to reach last cell of the matrix from its first cell

Find longest sequence formed by adjacent numbers in the matrix

Count number of paths in a matrix with given cost to reach destination cell

0-1 Knapsack problem

Maximize value of the expression A[s] – A[r] + A[q] – A[p] where s > r > q > p

Partition problem

Subset sum problem

Minimum Sum Partition problem

Find all N-digit binary strings without any consecutive 1’s

Rod Cutting

Maximum Product Rod Cutting

Coin change-making problem (unlimited supply of coins)

Coin Change Problem – Find total number of ways to get the denomination of coins

Longest alternating subsequence

Count number of times a pattern appears in given string as a subsequence

Collect maximum points in a matrix by satisfying given constraints

Count total possible combinations of N-digit numbers in a mobile keypad

Find optimal cost to construct binary search tree

Word Break Problem

Wildcard Pattern Matching

Find probability that a person is alive after taking N steps on the island

Calculate sum of all elements in a sub-matrix in constant time

Find maximum sum K x K sub-matrix in a given M x N matrix

Find maximum sum submatrix present in a given matrix

Find maximum sum of subsequence with no adjacent elements

Maximum subarray problem (Kadane’s algorithm)

Single-Source Shortest Paths – Bellman Ford Algorithm

All-Pairs Shortest Paths – Floyd Warshall Algorithm

**Graphs**

Terminology and Representations of Graphs

Graph Implementation using STL

Graph Implementation in C++ without using STL

Breadth First Search (BFS) | Iterative & Recursive Implementation

Depth First Search (DFS) | Iterative & Recursive Implementation

Arrival and Departure Time of Vertices in DFS

Types of edges involved in DFS and relation between them

Bipartite Graph

Minimum number of throws required to win Snake and Ladder game

Topological Sorting in a DAG

Transitive Closure of a Graph

Check if an undirected graph contains cycle or not

Total number of paths in given digraph from given source to destination having exactly m edges

Determine if an undirected graph is a Tree (Acyclic Connected Graph)

2-Edge Connectivity in the graph

2-Vertex Connectivity in the graph

Check if given digraph is a DAG (Directed Acyclic Graph) or not

Disjoint-Set Data Structure (Union-Find Algorithm)

Chess Knight Problem – Find Shortest path from source to destination

Check if given Graph is Strongly Connected or not

Check if given Graph is Strongly Connected or not using one DFS Traversal

Union-Find Algorithm for Cycle Detection in undirected graph

Kruskal’s Algorithm for finding Minimum Spanning Tree

Single-Source Shortest Paths – Dijkstra’s Algorithm

Single-Source Shortest Paths – Bellman Ford Algorithm

All-Pairs Shortest Paths – Floyd Warshall Algorithm

Print all k-colorable configurations of the graph (Vertex coloring of graph)

Print All Hamiltonian Path present in a graph

Greedy coloring of graph

**Heaps**

Introduction to Priority Queues using Binary Heaps

Min Heap and Max Heap Implementation in C++

Heap Sort (Out-of-place and In-place implementation in C++ and C)

Check if given array represents min heap or not

Convert Max Heap to Min Heap in linear time

Find K’th largest element in an array

Sort a K-Sorted Array

Merge M sorted lists of variable length

Find K’th smallest element in an array

Find smallest range with at-least one element from each of the given lists

Merge M sorted lists each containing N elements

External merge sort

Huffman Coding

Find first k maximum occurring words in given set of strings

Find first k non-repeating characters in a string in single traversal

**Linked List**

Introduction to Linked Lists

Linked List Implementation | Part 1

Linked List Implementation | Part 2

Static Linked List in C

Clone given Linked List

Delete Linked List

Pop operation in linked list

Insert given node into the correct sorted position in the given sorted linked list

Given a linked list, change it to be in sorted order

Split the nodes of the given linked list into front and back halves

Remove duplicates from a sorted linked list

Move front node of the given list to the front of the another list

Move even nodes to the end of the list in reverse order

Split given linked list into two lists where each list containing alternating elements from it

Construct a linked list by merging alternate nodes of two given lists

Merge given sorted linked lists into one

Merge Sort for Singly Linked List

Intersection of two given sorted linked lists

Reverse linked list | Part 1 (Iterative Solution)

Reverse linked list | Part 2 (Recursive Solution)

Reverse every group of k nodes in given linked list

Find K’th node from the end in a linked list

Merge alternate nodes of two linked lists into the first list

Merge two sorted linked lists from their end

Delete every N nodes in a linked list after skipping M nodes

Rearrange linked list in specific manner in linear time

Check if linked list is palindrome or not

Move last node to front in a given Linked List

Rearrange the linked list in specific manner

Detect Cycle in a linked list (Floyd’s Cycle Detection Algorithm)

**Matrix**

Print Matrix in Spiral Order

Create Spiral Matrix from given array

Shift all matrix elements by 1 in Spiral Order

Find Shortest path from source to destination in a matrix that satisfies given constraints

Change all elements of row i and column j in a matrix to 0 if cell (i, j) has value 0

Print diagonal elements of the matrix having positive slope

Find all paths from first cell to last cell of a matrix

Replace all occurrences of 0 that are not surrounded by 1 in a binary matrix

In-place rotate the matrix by 90 degrees in clock-wise direction

Count negative elements present in sorted matrix in linear time

Report all occurrences of an element in row wise and column wise sorted matrix in linear time

Calculate sum of all elements in a sub-matrix in constant time

Find maximum sum K x K sub-matrix in a given M x N matrix

Find maximum sum submatrix present in a given matrix

Find probability that a person is alive after taking N steps on the island

Count the number of islands

Flood fill Algorithm

Find shortest safe route in a field with sensors present

Find all occurrences of given string in a character matrix

Lee algorithm | Shortest path in a Maze

Travelling Salesman Problem using Branch and Bound

Collect maximum points in a matrix by satisfying given constraints

Count number of paths in a matrix with given cost to reach destination cell

Find longest sequence formed by adjacent numbers in the matrix

Find the minimum cost to reach last cell of the matrix from its first cell

Matrix Chain Multiplication

Find size of largest square sub-matrix of 1’s present in given binary matrix

Chess Knight Problem – Find Shortest path from source to destination

Find Duplicate rows in a binary matrix

Print all possible solutions to N Queens problem

Print all Possible Knight’s Tours in a chessboard

Find Shortest Path in Maze

Find Longest Possible Route in a Matrix

**Queue**

Chess Knight Problem – Find Shortest path from source to destination

Lee algorithm | Shortest path in a Maze

Find shortest safe route in a field with sensors present

Flood fill Algorithm

Count the number of islands

Find Shortest path from source to destination in a matrix that satisfies given constraints

Generate binary numbers between 1 to N

Calculate height of a binary tree | Iterative & Recursive

Delete given Binary Tree | Iterative & Recursive

Level Order Traversal of Binary Tree

Spiral Order Traversal of Binary Tree

Reverse Level Order Traversal of Binary Tree

Print all nodes of a given binary tree in specific order

Print left view of binary tree

Find next node in same level for given node in a binary tree

Check if given binary tree is complete binary tree or not

Print Diagonal Traversal of Binary Tree

Print corner nodes of every level in binary tree

Breadth First Search (BFS) | Iterative & Recursive Implementation

Minimum number of throws required to win Snake and Ladder game

Check if an undirected graph contains cycle or not

**Sorting**

Insertion sort | Iterative & Recursive

Selection sort | Iterative & Recursive

Bubble sort | Iterative & Recursive

Merge Sort

Quicksort

Iterative Implementation of Quicksort

Hybrid QuickSort

External merge sort

Custom Sort | Sort elements by their frequency and Index

Custom Sort | Sort elements of the array by order of elements defined by the second array

Inversion Count of an array

Segregate positive and negative integers in linear time

Find the smallest window in array sorting which will make the entire array sorted

Find largest number possible from set of given numbers

Move all zeros present in the array to the end

Sort binary array in linear time

Merge Sort for Singly Linked List

Group anagrams together from given list of words

Activity Selection Problem

Lexicographic sorting of given set of keys

Heap Sort (Out-of-place and In-place implementation in C++ and C)

Merge M sorted lists of variable length

Merge M sorted lists each containing N elements

Find all palindromic permutations of a string

Find all lexicographically next permutations of a string sorted in ascending order

Merge two sorted linked lists from their end

Sort an array containing 0’s, 1’s and 2’s (Dutch national flag problem)

Find pair with given sum in the array

Inplace merge two sorted arrays

Merge two arrays by satisfying given constraints

Find maximum product of two integers in an array

Find all distinct combinations of given length

Find all distinct combinations of given length with repetition allowed

Merging Overlapping Intervals

**Stack**

Check if given expression is balanced expression or not

Find duplicate parenthesis in an expression

Evaluate given postfix expression

Decode the given sequence to construct minimum number without repeated digits

Inorder Tree Traversal | Iterative & Recursive

Preorder Tree Traversal | Iterative & Recursive

Postorder Tree Traversal | Iterative & Recursive

Find ancestors of given node in a Binary Tree

Check if two given binary trees are identical or not | Iterative & Recursive

Reverse given text without reversing the individual words

Find all binary strings that can be formed from given wildcard pattern

Iterative Implementation of Quicksort

Depth First Search (DFS) | Iterative & Recursive Implementation

**String**

Check if given set of moves is circular or not

Check if given string is a rotated palindrome or not

Longest Palindromic Substring (Non-DP Space Optimized Solution)

Check if repeated subsequence is present in the string or not

Check if strings can be derived from each other by circularly rotating them

Convert given number into corresponding excel column name

Determine if two strings are anagram or not

Find all binary strings that can be formed from given wildcard pattern

Find all interleavings of given strings

Isomorphic Strings

Find all possible palindromic substrings in a string

Find all possible combinations of words formed from mobile keypad

Find all possible combinations by replacing given digits with characters of the corresponding list

Find all words from given list that follows same order of characters as given pattern

Find first k non-repeating characters in a string in single traversal

Group anagrams together from given list of words

Introduction to Pattern Matching

Inplace remove all occurrences of ‘AB’ and ‘C’ from the string

Longest even length palidromic sum substring

Print string in zig-zag form in k rows

Reverse given text without reversing the individual words

Run Length Encoding (RLE) data compression algorithm

Validate an IP address

Find the longest substring of given string containing k distinct characters

Find all palindromic permutations of a string

Find all substrings of a string that are permutation of a given string

Find the longest substring of given string containing all distinct characters

Find all Permutations of a given string

Find all lexicographically next permutations of a string sorted in ascending order

Find Lexicographically minimal string rotation

Find all strings of given length containing balanced parentheses

Find all N-digit binary numbers with k-bits set where k ranges from 1 to N

Generate binary numbers between 1 to N

Find all combinations of non-overlapping substrings of a string

Check if given sentence is syntactically correct or not

Find all N-digit strictly increasing numbers (Bottom-Up and Top-Down Approach)

Combinations of words formed by replacing given numbers with corresponding English alphabets

Word Break Problem

Wildcard Pattern Matching

Count number of times a pattern appears in given string as a subsequence

The Levenshtein distance (Edit distance) problem

Longest Common Subsequence | Introduction & LCS Length

Longest Common Subsequence | Space optimized version

Longest Common Subsequence of K-sequences

Longest Common Subsequence | Finding all LCS

Longest Repeated Subsequence problem

Longest Palindromic Subsequence using Dynamic Programming

Longest Common Substring problem

Shortest Common Supersequence | Introduction & SCS Length

Shortest Common Supersequence | Finding all SCS

Shortest Common Supersequence | Using LCS

**Trie**

Trie Implementation | Insert, Search and Delete

Memory efficient Trie Implementation using Map | Insert, Search and Delete

Longest Common Prefix in given set of strings (using Trie)

Lexicographic sorting of given set of keys

Find maximum occurring word in given set of strings

Find first k maximum occurring words in given set of strings

Find Duplicate rows in a binary matrix

**Greedy**

Activity Selection Problem

Huffman Coding

Shortest Superstring Problem

Job Sequencing Problem with Deadlines

Greedy coloring of graph

**Puzzles**

Clock angle problem – Find angle between hour and minute hand

Add two numbers without using addition operator | 5 methods

Generate power set of a given set

Implement power function without using multiplication and division operators

Print all numbers between 1 to N without using semicolon

Swap two numbers without using third variable | 5 methods

Determine the if condition to print specific output

Find maximum, minimum of three numbers without using conditional statement and ternary operator | 4 methods

Find numbers represented as sum of two cubes for two different pairs

Print “Hello World” with empty main() function | 3 methods

Tower of Hanoi Problem

Print all numbers between 1 to N without using any loop | 4 methods

Print a semicolon without using semicolon anywhere in the program

Multiply two numbers without using multiplication operator or loops

Find square of a number without using multiplication and division operator | 3 methods

Magnet Puzzle