# algorithms_and_data_structures

## Data Structure and Algorithms Problems

![alt tag](https://raw.githubusercontent.com/mandliya/algorithms_and_ds_playground/master/image.jpg) | Current Status| Stats | | :------------: | :----------: | | Total C++ Problems | 188 | | Total Python Problems | 15 | | Current Daily Streak| 11 | | Last Streak | 06/20/2019 - 06/21/2019| | Current Streak | 06/23/2019 - 07/03/2019|

Note: Some of the code here is old and was written when I was learning C++. It might be possible that code is not safe or making wrong assumptions. Please use with caution. Pull requests are always welcome.

### Include

Include contains single header implementation of data structures and some algorithms.

Data Structure/Algorithm Implementation
Generic Macros and Algorithms like swap, random number generation generic.h
Generic Stack Implementation stack.h
Generic Queue Implementation queue.h
Generic List Implementation list.h
Binary Search Tree Implementation binarySearchTree.h
Quick Sort Implementation quickSort.h
Merge Sort Implementation mergeSort.h
Selection Sort Implementation selectionSort.h
Bubble Sort Implementation bubbleSort.h
Generic Graph Implementation (Adjacency List) graph.h
Heap Sort Implementation heap_sort.h
My own string library implementation pstring.h pstring.cpp

### Bit Manipulation Problems

Problem Solution
Determine if a number is a power of 2. power_of_2.cpp
Determine the next power of 2 for a given number. next_power_of_2.cpp
Using bit manipulation determine if a number is multiple of 3. multiple_of_3.cpp
Determine endianess of the machine, print a number in reverse Endianess. reverseEndianness.cpp
Find the parity of given number. find_parity.cpp
Implement fast multiplication of a number to 7 using bit manipulation. multiply_by_7.cpp
Reverse bits of unsigned integer (two methods - Reversing bit by bit & divide and conquer). reverseBitsOfAnInteger.cpp
Small function to determine position of right most set bit in a given integer. right_most_set_bit.cpp
Given a vector of numbers, only one number occurs odd number of times, find the number. find_odd_one_out.cpp
Given two integers, determine if their sum would be interger overflow. integerOverflow.cpp
How many bit flip operation would require to convert number A to B. countNumberOfBitFlips.cpp
Given a number x and two positions (from right side) in binary representation of x, write a function that swaps n right bits at given two positions and returns the result. It is also given that the two sets of bits do not overlap. swapSetOfBits.cpp
Louise and Richard play a game. They have a counter set to N. Louise gets the first turn and the turns alternate thereafter. In the game, they perform the following operations: <ul><li>If N is not a power of 2, reduce the counter by the largest power of 2 less than N.</li></ul><ul><li>If N is a power of 2, reduce the counter by half of N.</li></ul> The resultant value is the new N which is again used for subsequent operations.The game ends when the counter reduces to 1, i.e., N == 1, and the last person to make a valid move wins. <ul><li> Given N, your task is to find the winner of the game. If they set counter to 1, Richard wins, because its Louise’ turn and she cannot make a move.</li></ul><ul><li>Input Format : -The first line contains an integer T, the number of testcases. T lines follow. Each line contains N, the initial number set in the counter.</ul></li> counter_game.cpp
Determine if two integers are of opposite signs. check_opposite_signs.cpp
Swap two bits at position p and q of a given integer. swapBits.cpp
Check if a number is power of 4. check_if_power_of_4.cpp

### Dynamic Programming Problems

| Problem | Solution | | :———— | :———-: | | Nth Fibonacci term using different memoization techniques | fibonacci.cpp| | Longest Common Subsequence Problem | lcs.cpp, longest_common_subsequence.py | | Maximum Value Contigous Subsequence Problem wiki| max_subsequence.cpp| | Catalan number - Count the number of possible Binary Search Trees with n keys | catalan_number.cpp| | Calculate the number of unique paths from source origin (0, 0) to destination (m-1, n-1) in a m x n grid. You can only move either in down or right direction.|unique_paths.cpp| | 0-1 Knapsack Problem: Imagine you are a thief and you want to steal things with room full of things. You have a knapsack which can handle maximum capacity of weight W, and you want to fill it up such that it’s worth is maximum. Being an intelligent thief, you know weights and values of each item in room. How would you fill your knapsack, such that you get the maximum possible value, such that you can only fill upto capacity W.|0_1_knapsack_problem.cpp|

### Tree Problems

| Problem | Solution | | :———— | :———-: | |Iterative Level order traversal of Tree using queue |levelOrderTraversalIterative.cpp, level_order_tree_traversal_iterative.py| |Recursive Level order traveral of Tree | levelOrderTraversalRecursive.cpp, level_order_tree_traversal_recursive.py| |ZigZag Traversal of Tree | zigZagTraversal.cpp, zig_zag_traversal.py| |Predecessor and Successor of a given node in Binary Search Tree | predecessorSuccessor.cpp| |Given values of two nodes in a Binary Search Tree, find the Lowest Common Ancestor (LCA). Assume that both the values exist in the tree.| lowest-common-ancestor.cpp, lowest_common_ancestor.py| |Given a binary tree (unlike binary search tree), find the Lowest Common Ancestor (LCA).|lowest-common-ancestor-binary-tree.cpp| |Given a binary tree, print out all of its root-to-leaf paths one per line.| printAllRootToLeafPath.cpp |Determine if a tree is sum tree. A SumTree is a Binary Tree where the value of a node is equal to sum of the nodes present in its left subtree and right subtree. An empty tree is SumTree and sum of an empty tree can be considered as 0. A leaf node is also considered as SumTree.| sumTree.cpp| |Convert a tree to sumTree, such that each node is sum of left and right subtree of the original tree.| convert_to_sum_tree.cpp, convert_to_sum_tree.py| | Convert a sorted array to balanced binary search tree.| sortedArrayToBST.cpp| | Given a binary tree, generate sum of each vertical column.|verticalSum.cpp| | Given a binary tree and key, node with key exists in tree. Find all the ancestors of the node with key, ancestor here are the nodes which are in straight path from node to root.| node_ancestors_in_root_path.cpp| | Given a binary tree and key, return the level of the node with key. Root is at level 1, and if node with key does not exists in tree, return 0| level_of_node.cpp| | Given a binary tree, find all the paths from root to nodes, whose sum is k. | k_sum_paths.cpp| | Given a binary tree, print its nodes level by level in reverse order. i.e. all nodes present at last level should be printed first followed by nodes of second-last level and so on.. All nodes for any level should be printed from left to right. | reverseLevelOrderTraversal.cpp | | Invert a binary tree, recursively and iteratively.| invert_a_tree.cpp | | Given a Binary Search Tree, find ceil and floor of a given key in it. If the given key lie in the BST, then both floor and ceil is equal to that key, else ceil is equal to next greater key (if any) in the BST and floor is equal to previous greater key (if any) in the BST | floor_ceil_bst.cpp | | Find kth smallest element in a binary search tree | kth_smallest.cpp| | Validate if a given binary tree is a binary search tree. | validate_bst.cpp | | Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.| find_target_k.cpp | | Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target. Also, to note that the target value is a floating point. There will be only one unique value which is closest to the target. |closest_bst_value.cpp, closest_bst_value.py | | Given a binary tree, traversing preorder, construct a string output containing node values and parenthesis. The null node needs to be represented by empty parenthesis pair “()”. And you need to omit all the empty parenthesis pairs that don’t affect the one-to-one mapping relationship between the string and the original binary tree. Examples in code file| string_from_tree.cpp|

### String Problems

| Problem | Solution | | :———— | :———-: | | Implementation of Robin-Karp algorithm for string search | robinKarpStringMatching.cpp | | Find next permutation of a given string, ie. rearrange the given string sucht a way that is next lexicographically greater string than given string | next_permutation.cpp| | Implementation of Z algorithm for pattern matching | z.cpp| | Test cases for self created string library | pstring_test.cpp| | Get the length of the last word in a string. | length_of_last_word.cpp| | Find the difference between two string. String t is generated by random shuffling string s and then add one more letter at a random position. Determine the character which is different in t| find_difference.cpp|

### Common Data Structure and logic problems

| Problem | Solution | | :———— | :———-: | | Print the contents of matrix in a spiral order | matrix_spiral_print.cpp | Given a M x N matrix, rotate it by R rotations anticlockwise, and show the resulting matrix. | rotate_matrix.cpp| | Rotate an array by r elements ( left or right ) | array_rotation.cpp | Given an array of repeating/non-repeating intergeres, determine the first non-repeating int in this array | first_non_repeating_int.cpp| | In Quantumland, there are n cities numbered from 1 to n. Here, ci denotes the ith city. There are n−1 roads in Quantumland. Here, ci and ci+1 have a bidirectional road between them for each i < n.There is a rumor that Flatland is going to attack Quantumland, and the queen wants to keep her land safe. The road between ci and ci+1 is safe if there is a guard in ci or ci+1. The queen has already placed a few guards in some of the cities, but she is not sure if they are enough to keep the roads safe. She wants to know the minimum number of new guards she needs to hire. See comments in solution for input/output details. | save_quantamland.cpp| | You are given an integer N. Find the digits in this number that exactly divide N (division that leaves 0 as remainder) and display their count. For N=24, there are 2 digits (2 & 4). Both of these digits exactly divide 24. So our answer is 2. See more details in header comment of the solution file. | findDigits.cpp| | Encrypt and then decrypts a text using Caeser Cipher. | caeser_cipher.cpp| | Encrypt and then decrypts a text using Vigenère cipher. | vigenere_cipher.cpp| | Generate binary numbers between 1 to N efficiently. |n_binary.cpp| | Implement power function | power_function.cpp|

### Math Problems

| Problem | Solution | | :———— | :———-: | | Print all the permutations of a string. Example: Permutations of ABC are ABC, ACB, BCA, BAC, CAB, CBA | string_permutations.cpp | | Euclidean algorithm to find greatest common divisor of two numbers. (Iterative and recursive)|gcd.cpp| | Implement pow(x,y) using divide and conquer approach. Try implementing it in O(logn)| pow.cpp| | Calculate factorial of large number, say 100 (it will have 158 digits) |factorial_of_large_num.cpp| | Generate all possible words from a number entered on a traditional mobile keypad | phone_digits.cpp| | Given a string representation of a number, remove n characters from the string such that number representation is lowest possible.| lowest_possible_number.cpp| | Detect if a number is a happy number. A number is happy number if sequence of operations where number is replaced by sum of square of its digits leads eventually to 1. A number is not a happy number if we are in an infinite loop when above operations are performed.| happy_number.cpp|

### Stack Problems

| Problem | Solution | | :———— | :———-: | | We have series of n daily price quotes for a stock. We need to calculate span of stock’s price for all n days. Span for ith day is defined as maximum number of consecutive days, for which the price of the stock was less than or equal to ith day. For stock quotes {100, 60, 70, 65, 80, 85} span will be {1, 1, 2, 1, 4, 5}. Span for day 1 is always 1, now for day 2 stock is at 60, and there is no day befor it when stock was less than 60. So span remains 1. For day 3, the stock is priced at 70, so its span is 2, as previous day it was 60, and so on. | stock_span_problem.cpp | | Given an infix expression, convert it to postfix expression, Example (A+B)*C –> AB+C* | infix_to_postfix.cpp | | Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.| valid_parenthesis.cpp|

### Sort and Search Problems

| Problem | Solution | | :———— | :———-: | | Given a sorted vector, return first index of the occurrence of a value in vector, if number does not exist, return -1 | first_occurrence_binary_search.cpp | | Find the first repeating element in an array of integers. Given an array of integers, find the first repeating element in it. We need to find the element that occurs more than once and whose index of first occurrence is smallest.| firstRepeatingElement.cpp| | Given a list of unsorted integers, A={a1,a2,…,aN}, Find the pair of elements that have the smallest absolute difference between them? If there are multiple pairs, find them all.| closest_numbers.cpp| | Given a sorted array, determine index of fixed point in this array. If array does not have a fixed point return -1. An array has a fixed point when index of the element is same as index i.e. i == arr[i], Expected time complexity O(logn)| fixedPoint.cpp| | Find the maximum element in an array which is first increasing and then decreasing. Input: arr[] = {8, 10, 20, 80, 100, 200, 400, 500, 3, 2, 1}, output : 500. Array may be strictly increasing or decreasing as well. ExpectedTime complexity is O(logn).| findMaximum.cpp| | Given an array of positive and/or negative integers, find a pair in the array whose sum is closest to 0.| findClosestPairToZero.cpp| | Numeros, the Artist, had two lists A and B, such that B was a permutation of A. Numeros was very proud of these lists. Unfortunately, while transporting them from one exhibition to another, some numbers were left out of A. Can you find the missing numbers? Notes: <ul><li>If a number occurs multiple times in the lists, you must ensure that the frequency of that number in both lists is the same. If that is not the case, then it is also a missing number.</li></ul><ul><li>You have to print all the missing numbers in ascending order.</li></ul><ul><li>Print each missing number once, even if it is missing multiple times.</li></ul><ul><li>The difference between maximum and minimum number in B is less than or equal to 100.</li></ul>. <ul><li> There will be four lines of input: n - the size of the first list, This is followed by n space-separated integers that make up the first list. m - the size of the second list. This is followed by m space-separated integers that make up the second list. Output the missing numbers in ascending order.| missingNumbers.cpp| | Find the closest pair from two sorted arrays. Given two sorted arrays and a number x, find the pair whose sum is closest to x and the pair has an element from each array. We are given two arrays ar1[0…m-1] and ar2[0..n-1] and a number x, we need to find the pair ar1[i] + ar2[j] such that absolute value of (ar1[i] + ar2[j] – x) is minimum.| closestPairSorted.cpp| | Given an array A of n elements, find three indices i, j and k such that A[i]^2 + A[j]^2 = A[K]^2. O(n2) time complexity and O(1) space complexity | squareSum.cpp| | Given an unsorted array arr[0..n-1] of size n, find the minimum length subarray arr[s..e] such that sorting this subarray makes the whole array sorted. |minLengthUnsortedArray.cpp| | Find the missing number in Arithmetic Progression | missingNumber2.cpp | | Find the common elements in 3 sorted vectors | commonIn3Arrays.cpp | | Find all the pairs with a given sum in an unsorted array/vector | find_pairs_with_sum.cpp | | Given an array, find peak element in it. A peak element is an element that is greater than its neighbors.| peak_element.cpp | | Given a sorted array of distinct non-negative integers, find smallest missing element in it.| smallest_missing.cpp| | Move all zeros in the vector to the end | move_zeros.cpp|

### Graph Problems

| Problem | Solution | | :———— | :———-: | | Depth First Traversal of a Graph | dfsDemo.cpp | | Breadth First Traversal of a Graph | bfsDemo.cpp | | calculate the shortest distance from the start position (Node S) to all of the other nodes in the graph using Dijkstra algorithm. | dijkstra-shortest-reach.cpp| | Calculate total weight of Minimum Spanning Tree of a given graph ( sum of weights of edges which forms MST) using Prim’s algorithm | primsMST.cpp| | Print Minimum Spanning Tree( MST ) of a given graph using Kruskal’s algorithm.| kruskalMST.cpp| | Create a program to generate a Huffman encoding for each character as a table.|huffman_encoding.cpp| | Search a given word in a 2D board containing letters. The word can be constructed by sequentially traversing adjacent horizontal or vertical cells. In a sequence to form word, letter on same position can not be used more than once. (Check top of file for examples.)|grid_word_search.cpp| | Given a 2D screen, location of the pixel and new value of the color to fill, replace the color of the pixel and all the adjacent(up, below, left, right) same colored pixel with new color. This is same as flood fill (remember the bucket symbol) a region in MS-PAINT.| flood_fill.cpp|

### Greedy Problems

| Problem | Solution | | :———— | :———-: | | Given two integer arrays, A and B, each containing N integers. You are free to permute the order of the elements in the arrays. Is there an permutation A’, B’ possible of A and B, such that, A’i+B’i ≥ K for all i, where A’i denotes the ith element in the array A’ and B’i denotes ith element in the array B’.| two_arrays.cpp| | John is taking orders. The ith order is placed by the ith customer at ti time and it takes di time to procees. What is the order in which the customers will get their orders? (see more details in solutions’s comments)|orders_order.cpp|

### Backtracking Problems

| Problem | Solution | | :———— | :———-: | | You are given a digit string (e.g “1234”, “567” etc), provide all possible letter combinations we could generate from this digit string, based on the mapping we see on the telphone/mobile dialpad. If you have typed SMS in old style phones, you would know. For e.g. “1” is mapped to “abc”, 2 is mapped to “def”. You can refer to the image.. <ul><li> Example: “34” will give output: {“dg”,”dh”,”di”,”eg”,”eh”,”ei”,”fg”,”fh”,”fi”} </li></ul> Note that order does not matter in result set.|dialpad_combinations.cpp| | Implement wildcard pattern maching with support for ‘?’ & ‘’. <ul><li>’?’ Matches any single character.</li></ul><ul><li>‘’ Matches any sequence of character.</li></ul>. Checkout examples in file for more details.|wild_card_matching.cpp| | Given a 2D board and list of words from a dictionary, find all the possible words on board fromt the list. (Check example in the solution)| word_search.cpp|