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:

Data Structures and Algorithms
- Index:
- Content:
  - Bit Manipulation
  - Dynamic Programming
  - Graph
  - Heaps
  - Linked List
    - Singly Linked List
  - Mathematics
  - Matrix
  - Misc
  - String or Array
    - Searching
    - Sorting
  - Tree
    - Binary Search Tree
    - Binary Tree
    - Trie

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	-

Data-Structures-Algorithms
Data-Structures-Algorithms copied to clipboard

Metadata

Data Structures and Algorithms

Index:

Content:

Bit Manipulation

Dynamic Programming

Graph

Heaps

Linked List

Singly Linked List

Mathematics

Matrix

Misc

String or Array

Searching

Sorting

Tree

Binary Search Tree

Binary Tree

Trie

← Metadata

Owner

Metadata

Data-Structures-Algorithms Data-Structures-Algorithms copied to clipboard

Metadata

Data Structures and Algorithms

Index:

Content:

Bit Manipulation

Dynamic Programming

Graph

Heaps

Linked List

Singly Linked List

Mathematics

Matrix

Misc

String or Array

Searching

Sorting

Tree

Binary Search Tree

Binary Tree

Trie

← Metadata

Owner

Metadata

Data-Structures-Algorithms
Data-Structures-Algorithms copied to clipboard