Data Structure and Algorithms Problems

Current Status	Stats
Total Problems	64
Current Streak	45
Longest Streak	45 ( August 17, 2015 - September 30, 2015 )

LinkedList Problems

Problem	Solution
Find the nth node of linked list from last.	[nthToLastNode.cpp] (linked_list_problems/nthToLastNode.cpp)
Add numbers where each digit of the number is represented by node of a linkedlist. Give output as a linked list.	[add_two_numbers_lists.cpp] (linked_list_problems/add_two_numbers_lists.cpp)
Swap nodes of a linkedlist without swapping data.	[swapNodesWithoutSwappingData.cpp] (linked_list_problems/swapNodesWithoutSwappingData.cpp)
Given a linked list, reverse alternate nodes and append at the end.	reverseAlternateNodes.cpp
Only given a node pointer, delete the node from the linked list.	deleteNode.cpp
Delete the entire linkedlist.	deleteLinkedlist.cpp
Print middle node of linkedlist without iterating twice.	printMiddleNode.cpp
Determine if a linked list is a pallindrome.	listPallindrome.cpp
Insert data in a sorted linked list.	insertInASortedLinkedList.cpp
Determine the intersection(merging) point of two given linked list.	findIntersectionPointOfLists.cpp
Clone a linkedlist which has next and an random pointer, Space Complexity - O(1).	cloneListWithRandomPtr.cpp
Given a sorted linked list with duplicates, remove duplicates in one iteration.	removeDuplicatesFromSortedList.cpp
Find the nth node of linked list from last.	[nthToLastNode.cpp] (linked_list_problems/nthToLastNode.cpp)
Sort a linked list using merge sort	[merge_sort.cpp] (linked_list_problems/merge_sort.cpp)
Given a singly linked list L0 -> L1 -> … -> Ln-1 -> Ln. Rearrange the nodes in the list (in place) so that the new formed list is : L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 ....	rearrange_list.cpp

Include

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

DS/ALG	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] (include/list.h)
Binary Search Tree Implementation	[binarySearchTree.h] (include/binarySearchTree.h)
Quick Sort Implementation	[quickSort.h] (include/quickSort.h)
Merge Sort Implementation	[mergeSort.h] (include/bubbleSort.h)
Selection Sort Implementation	[selectionSort.h] (include/selectionSort.h)
Bubble Sort Implementation	[bubbleSort.h] (include/bubbleSort.h)
Linux Kernel Double LinkedList Implementation	double_linked_list.h
Generic Graph Implementation (Adjacency List)	graph.h

###Bit Manipulation Problems

Problem	Solution
Determine if a number is a power of 2.	power_of_2.cpp
Add two binary number represented as string.	addBin.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
Add two numbers without using any arithmetic operators	addition_without_operators.cpp

Cracking the coding interview problems

Problem	Solution
Problem 1 : Edition 6: Write an algorithm to determine whether a string has unique characters or not. Can we do it without using addtional data structures?	1-1-hasUniqueChars.cpp
Problem 2 : Edition 5: Reverse a string when you are a pass a null terminated C string.	1-2-edi5-reverseString.cpp
Problem 2 : Edition 6: Given two strings, determine if one is permutation of other.	1-2-perm-strings.cpp
Problem 3 : Edition 5: Write an algorithm to remove duplicate chars from a string.	1-3-edi5-removeDuplicates.cpp
Problem 3 : Edition 6: URLify: Replace all the spaces in a string with '%20'. Preferebly Inplace	1-3-URLify.cpp
Problem 4 : Edition 6: Given a string, write a function to check if it is a permutation of a pallindrome.	1-4-pallindrome-permutations.cpp
Problem 5 : Edition 6: There are three possible edits that can be performed on a string - Insert a char, Delete a char, Replace a char. Given two strings, determine if they are one or 0 edit away.	1-5-one-edit-away.cpp

Tree Problems

Problem	Solution
Iterative Level order traversal of Tree using queue	levelOrderTraversalIterative.cpp
Recursive Level order traveral of Tree	levelOrderTraversalRecursive.cpp
ZigZag Traversal of Tree	zigZagTraversal.cpp
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
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

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

Common Data Structure and logic problems

| 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

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] (math_problems/string_permutations.cpp)
Euclidean algorithm to find greatest common divisor of two numbers. (Iterative and recursive)	gcd.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

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

Graph Problems

Problem	Solution
Depth First Traversal of a Graph	dfsDemo.cpp
Breadth First Traversal of a Graph	bfsDemo.cpp