Skip to content

Latest commit

 

History

History
222 lines (177 loc) · 20.5 KB

README.md

File metadata and controls

222 lines (177 loc) · 20.5 KB

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 -