Data Structures and Algorithms
My implementation of some popular data structures and algorithms and interview questions relating to them in Python 3 and C++
Index:
Content:
Bit Manipulation
Contains some popular questions based on bit manipulations.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Check whether a given number n is a power of 2 or 0 | py | cpp |
| Count number of bits needed to be flipped to convert A to B | py | cpp |
| Find the two non-repeating elements in an array of repeating elements | py | cpp |
| Find the next greater and next smaller number with same number of set bits | py | cpp |
Dynamic Programming
Contains some popular questions based on dynamic programming approach.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| 0-1 Knapsack Problem | py | - |
| Cutting Rod problem | py | - |
| minimum number of edits (operations) required to convert ‘str1’ into ‘str2’ | py | - |
| Given a 2-D matrix of 0s and 1s, find the Largest Square which contains all 1s in itself | py | - |
| Given two sequences, print the longest subsequence present in both of them. | py | - |
| Length of the longest subsequence in an array such that all elements of the subsequence are sorted in increasing order | py | - |
| Find minimum cost path in a matrix from (0,0) to given point (m,n) | py | - |
| Partition a set into two subsets such that the difference of subset sums is minimum | py | - |
| Minimum number of umbrellas of m different sizes required to accomodate N people | py | cpp |
| Determine if there is a subset of the given set with sum equal to given sum | py | - |
| Maximum Subarray Problem | py | - |
| Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps | py | - |
Graph
Contains implementation of Graph data structure and some common questions and algorithms related to it.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Find all possible words in a board of characters | py | - |
| Breadth First Search Traversal | py | - |
| Depth First Search Traversal | py | - |
| Detect Cycle in directed graph | py | - |
| Detect cycle in undirected graph | py | - |
| Dijkstra’s Shortest Path Algorithm | py | - |
| Find shortest distances between each pair of vertices in a given edge weighted directed Graph | py | - |
| Graph implementation | py | - |
| Kruskal's Algorithm for Minimum Spanning Tree | py | - |
| Topological Sort | py | - |
Heaps
Contains implementation of Heap data structure and some common questions and algorithms related to it.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Heap Sort algorithm | py | - |
| Max Heap implementation | py | - |
| Min Heap implementation | py | - |
| Find the median for an incoming stream of numbers after each insertion in the list of numbers | py | - |
Linked List
Contains implementation of Linked List data structure and some common questions and algorithms related to it.
Singly Linked List
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Clone a linked list with next and random pointer | py | - |
| Given a linked list of line segments, remove middle points if any | py | - |
| Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes. | py | - |
| Merge a linked list into another linked list at alternate positions | py | - |
| Perform Merge Sort | py | - |
| Find Middle Node | py | cpp |
| Point to next higher value node in a linked list with an arbitrary pointer | py | - |
| Find if linked list contains any cycle | py | - |
| To select a random node in a singly linked list | py | - |
| Find and remove cycle if any | py | cpp |
| Reverse sub list of K nodes each | py | cpp |
| Reverse alternate sub list of K nodes each | py | cpp |
| Reverse a linked list | py | cpp |
| Bring even valued nodes to the front | py | - |
| Implementation of Singly Linked List | py | cpp |
| Skip M nodes and then delete N nodes alternately | py | cpp |
Mathematics
Contains implementation of some common questions and algorithms related to Mathematics.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Fine the number of trailing zeros in factorial of a number | py | cpp |
| Find the greatest common divisor of 2 numbers | py | - |
| print all prime factors of a given number | py | - |
| Sieve of Eratosthenes (find prime numbers up to n efficiently) | py | - |
Matrix
Contains some common algorithms and questions based on Matrix.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Given the Coordinates of King and Queen on a chessboard, check if queen threatens the king | py | - |
| Search in a row wise and column wise sorted matrix | py | - |
| Given a 2D array, print it in spiral form | py | - |
Misc
Contains some miscellaneous questions and algorithms.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Given a dictionary, write a function to flatten it | py | - |
String or Array
Contains some common questions and algorithms related to strings or 1-d arrays.
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Find the longest substring with k unique characters in a given string | py | - |
| Find a pattern in a string using KMP search algorithm | py | - |
| Find the Kth smallest element in the array | py | - |
| Find a pair in an array with sum x | py | - |
| Print all valid (properly opened and closed) combinations of n pairs of parentheses | py | - |
| reverse the order of the words in the array | py | - |
| Find index of given number in a sorted array shifted by an unknown offset | py | - |
| Print all permutations of a given string | py | - |
Searching
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Linear Search in an array | py | - |
| Binary Search in an array | py | - |
| Interpolation Search in an array | py | - |
Sorting
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Bubble sort Algorithm | py | - |
| Counting sort Algorithm (non-comparision based sorting) | py | - |
| Insertion sort Algorithm | py | - |
| Sort an array where each element is at most k places away from its sorted position | py | - |
| Merge Sort Algorithm | py | - |
| Quick Sort Algorithm using last element as pivot | py | - |
| Selection sort Algorithm | py | - |
Tree
Contains implementation of Tree data structure and some common questions and algorithms related to it.
Binary Search Tree
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Binary Search Tree implementation | py | - |
| Check if a given array can represent Preorder Traversal of Binary Search Tree | py | - |
| Find the in-order ancestor of a given node in BST | py | - |
| Find the Lowest Common Ancestor | py | - |
| Given a sorted array, create a BST with minimal height | py | - |
Binary Tree
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Print Nodes in Bottom View of Binary Tree | py | - |
| Check if a binary tree is height balanced | py | - |
| Check whether a binary tree is a full binary tree or not | py | - |
| Given two binary trees, check if the first tree is subtree of the second one | py | - |
| Find the Lowest Common Ancestor in a Binary Tree | py | - |
| Create a list of all nodes at each depth | py | - |
| Find the maximum path sum i.e. max sum of a path in a binary tree | py | - |
| Find minimum depth of a binary tree | py | - |
| Remove nodes on root to leaf paths of length < K | py | - |
| Given a Perfect Binary Tree, reverse the alternate level nodes of the tree | py | - |
| Print Nodes in Top View of Binary Tree | py | - |
Trie
| Topic/Question | Code in Python | Code in C++ |
|---|---|---|
| Implementation of Trie data structure | py | - |