**Array**- Rearrange the array with alternate high and low elements
- Sort binary array in linear time
- Sort an array containing 0’s, 1’s and 2’s (Dutch national flag problem)
- Find pair with given sum in the array
- Shuffle a given array of elements (Fisher–Yates shuffle)
- 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
- Inplace merge two sorted arrays
- Merge two arrays by satisfying given constraints
- Find sub-array with 0 sum
- Find maximum length sub-array having given sum
- Find maximum length sub-array having equal number of 0’s and 1’s
- Find index of 0 to replaced to get maximum length sequence of continuous ones
- Find maximum product of two integers in an array
- Replace each element of array with product of every other element without using / operator
- Find a duplicate element in a limited range array
- Find largest sub-array formed by consecutive integers
- 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
- Decode the array constructed from another array
- 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
- 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 ? between hour and minute hand
- Add two numbers without using addition operator | 4 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

# Algorithms and Data Structures

## Sunday, January 1, 2017

### 350+ Problems

Subscribe to:
Posts (Atom)