# Data Structures and Algorithms

My implementation of some popular data structures and algorithms and interview questions relating to them in Python 3 and C++

## 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 -

Contains implementation of Linked List data structure and some common questions and algorithms related to it.

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 -

Get A Weekly Email With Trending Projects For These Topics
No Spam. Unsubscribe easily at any time.
python (48,438
cpp (1,172
algorithm (462
graph (357
data-structures (341
interview-questions (175
tree (170
mathematics (142
matrix (119
datastructures (66
strings (40
dynamic-programming (38
heap (30
arrays (24