Home

##Contact Info## Contact me on IRC channel if you have a question. Server: irc.foonetic.net Channel: #tusharroy

###Facebook Page### Like my Facebook page for updates on new video. https://www.facebook.com/tusharroy25

###Private Tutoring### If you are interested in one on one private online tutoring from author of this github repository, please send email to [email protected]

###Contribution to this repository### Please contribute to this repository to help it make better. Any change like new question, code improvement, doc improvement etc. is very welcome. Just send me a pull request and I will review the request and approve it if it looks good.

###Video Link###

1. [Youtube channel] (https://www.youtube.com/user/tusharroy2525)
2. Dynamic Programming Youtube playlist
3. Binary Tree Youtube playlist
4. Stack Queue Youtube playlist
5. Suffix/Prefix Youtube playlist
6. Graph Youtube playlist

###Arrays###

1. Given two numbers in form of array add them - ArrayAddition.java
2. Given stock prices for number of days BuySellStockProfit.java

• Buy sell stock once to maximize profit
• Buy sell stocks any number of times to maximum profit

3. Given an array of elements check if elements in the array are consecutive or not. - CheckIfArrayElementsAreConsecutive.java
4. Write a function to determine if array contains duplicate elements within k distance from each other - DuplicateWithinkIndices.java
5. Given an array and a number k < n, find all elements occurring more than n by k times - FindElementsOccurringNByKTimesTetris.java
6. Given a list of gas stations and amount of fuel they have, find a tour which travels all gas stations - GasStationCircle.java
7. Given an unordered array of positive integers, create an algorithm that makes sure no group of integers of size bigger than M have the same integers - GroupElementsInSizeM.java
8. Given an array find an increasing subsequence of length 3 which has maximum product - IncreasingSubsequnceOfLength3WithMaxProduct.java
9. Given an array find maximum circular contiguous sum - KadaneWrapArray.java
10. kth largest element in an unsorted array using quick select - KthElementInArray.java
11. kth largest element in two sorted array - KthLargestInTwoSortedArray.java
12. Print next greater element for every element in array - LargerElementOnRight.java
13. Given an array of 0s and 1s find the largest subarray with equal number of 0s and 1s - LargestSubArrayWithEqual0sAnd1s.java
14. Longest increasing subsequence in an array with O(NlogN) time complexity - LongestIncreasingSubSequenceOlogNMethod.java
15. Given an array maximize i - j such that a[i] > a[j] - MaximumIminusJSuchThatAiGTAj.java
16. Given an array, find maximum of all subarrays of size k - MaximumOfSubarrayOfSizeK.java
17. Given an array of positive and negative numbers, find a subarray which has maximum product - MaxProductSubarray.java maxproductsubarray.py
18. Given an array of size n, the array contains numbers in range from 0 to k-1 where k is a positive integer and k <= n. Find the maximum repeating number in this array - MaxRepeatingNumber.java
19. Given an array and two numbers, find minimum distance between these numbers. There could duplicates of these numbers in array - MinimumDistanceBetweenTwoNumbers.java
20. Find minimum length unsorted subarray, sorting which makes entire array sorted - MinimumSortedWhichSortsEntireArray.java
21. Given array of 0 and non zero numbers, move all 0s to the end in O(n) time - MoveAllZerosToEnd.java
22. Given an array, return a new array which has multiplication of all elements except own index - MultiplyAllFieldsExceptOwnPosition.java
23. Given an unsorted array, find total number of triangles formed taking 3 elements of this array - NumberOfTrianglesInUnsortedArray.java numberoftrianglesunsortedarray.py
24. Given an array with first negative and then positive numbers, position negative and positive numbers alternately - PositiveAndNegativeNumberAlternatively.java
25. Given an array arr[] of size n where every element is in range from 0 to n-1. Rearrange the given array so that arr[i] becomes arr[arr[i]] in O(n) time and O(1) space - RearrangeSuchThatArriBecomesArrArri.java
26. Given an array with elements in range of 0 to n-1, one number is repeated and one number is missing. Find both the numbers - RepeatingAndMissingNumber.java
27. Stable marriage problem - StableMarriageProblem.java
28. Given an unsorted array of nonnegative numbers , find a contiguous subarray with given sum - SubarrayWithGivenSum.java
29. Given an array, find triplet which sums to a given value - https://github.com/mission-peace/interview/blob/master/src/com/interview/array/TripletInArray.java
30. Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible - TugOfWar.java
31. Given an unsorted array convert it into a < b > c < d > e < f > g fashion - ConvertAnArrayIntoDecreaseIncreaseFashion.java
32. Given multiple sorted lists, sort them into one list - ChunkMerge.java
33. Given an array which represents bars how much rain water will be trapped - TrappingWater.java
34. Print nth number of count sequence. Sequence is like 1 11 21 1211 111221 and so on. NthElementOfCountNumberSequence.java
35. Given 2 arrays of same length consisting of 0s and 1s find max span i,j in two arrays such that sum b/w i to j is same. LongestSameSumSpan.java longestsamesumspan.py
36. Count number of inversions where i < j < k and input[i] > input[j] > input[k] in array. CountInversionOfSize3.java countinversionofsize3.py
37. Given an array of unique integers and total, find all triplets whose sum is less than total. TripletSumLessThanTotal.java tripletsumlessthantotal.py
38. Given array of 0s and 1s and maximum flip allowed from 0 to 1, find maximum number of consecutive 1s you can have in array. Flip0sMaximum1s.java flip0smaximum1s.py
39. Given two arrays, arrange elements of first element by values in second array. ReorderArrayByIndex.java reorderarraybyindex.py
40. Given an array find which rotation will give max sum of i*arr[i] - RotationWithMaxSum.java rotationwithmaxsum.py
41. Zig zag arrangement of array. ZigZagArrangement.java zigzagarrangement.py
42. Rearrange array with elements in range 0 to n-1 such that arr[i] = j becomes arr[j] = i. RearrangeArrayPerIndex.java rearrangearrayperindex.py
43. Given sorted array of positive integers find smallest positive integer not represented by sum of some subset of this array. SmallestIntegerNotRepresentedBySubsetSum.java smallestintegernotrepresentedbysubsetsum.py
44. Arrange positive and negative numbers alternatively maintaining order in input array. PositiveAndNegativeNumberAlternativelyMaintainingOrder.java positiveandnegativealternativelymaintainingorder.py
45. Given two sorted arrays find max sum path from start of any array to end of any array. Switch only happens at common array element. MaximumSumPathTwoArrays.java maximumsumpathtwoarrays.py
46. Find common elements in 3 sorted array. CommonThreeSortedArray.java commonthreesortedarray.py
47. Generate minimum number from give sequence of D and I where D indicates decrease and I indicates increase.[MinimumNumberFromSequence.java] (https://github.com/mission-peace/interview/blob/master/src/com/interview/array/MinimumNumberFromSequence.java)
48. Count smaller numbers on right side of every element in given array - CountSmallerOnRight.java
49. Find max array created by picking k elements from array1 and array2 by maintaining order in both the arrays - MaxNumberFromTwoArray
50. Find duplicate in array of size n + 1 with elements from 1 to n in O(1) space - DuplicateNumberDetection.java
51. Shortest palindrome from a string - ShortestPalindrome.java
52. Find if there exists an increasing subsequence of length 3 or increasing triplet -IncreasingTripletSubsequence.java

###Binary Search###

1. Given an arithmetic progression with one number mission find that missing number - ArithmeticProgressionSearch.java
2. Search an element in sorted array - BinarySearch.java
3. Search an element in array which is first increasing then decreasing then increasing or other way round - CircularBinarySearch.java
4. Given a sorted array find total number of pairs whose difference is k - CountNDistinctPairsWithDifferenceK.java
5. Given a sorted array with duplicates, find first occurrence of a given element - FirstOccurrenceOfNumberInSortedArray.java
6. Find floor and ceiling of given element in sorted array - FloorAndCeilingSortedArray.java
7. Find median of two sorted array of same size - MedianOfTwoSortedArray.java
8. Find a missing number in array of consecutive numbers - MissingNumberInConsecutiveNumbers.java
9. Find a value of function in which this monotonically increasing function becomes positive - MonotonicallyIncreasingFunctionBecomesPositive.java
10. Find number of pairs where x^y > y^x - NumberOfPairWithXPowerYGreaterThanYPowerX.java
11. Given an array find an element which is larger than both its neighbors - PeakElement.java
12. Given an array which is sorted and rotated find an element - SortedAndRotatedArraySearch.java
13. Minimum element in sorted and rotated array

###Bits###

1. Add two number in binary representation - AddTwoNumberInBinaryRepresentation.java
2. Given an integer and number k, right or left rotate bits in this integer by k - BitRotation.java
3. Using byte array for storing information - ByteAsStorage.java
4. Count number of set bits in an integer - CountBits.java
5. Given a screen in form of byte array with width and start and end points of a horizontal line. Draw this line DrawHorizontalLine.java
6. Given an array in which every number occurs 3 times find this one number occurring only once - FindNumberOccurringOnceOtherNumbers3Times.java
7. Given two numbers M and N, insert M into N from i to j bits of N - InsertMintoNiTojBits.java
8. Given an integer find next higher/lower integer with same number of set bits as original integer - NextHigherAndNextLowerWithSameNumberBits.java
9. Given an integer find next power of 2 greater than this integer - NextPowerOf2.java
10. Given an array find one/two number occurring odd number of times - NumberOccuringOddTimes.java
11. Given two numbers M and N, how many bit flips are required to convert M into N - NumberOfBitsFlipToConvertNToM.java
12. Convert a real number(with decimals) into a binary number - RealNumberToBinary.java
13. Given an integer reverse bits of this integer - ReverseBits.java
14. Given an integer swap its odd bits with even bits at every position - SwapOddEvenBits.java
15. Given an integer and two numbers i and j, swap bits at these positions in this integer - SwapTwoBits.java
16. Initially there is a number n. Two players start playing a game turn by turn. Each player has to replace the number n written on the board by n-2^k (for some k >= 0 such that 2^k < n) - WinnerWithBeautifulNumber.java
17. Square of a number without using * or ^ operator - SquareOfNumber.java
18. Find two missing number where there are n-2 unique numbers in range 1 to n. Find one missing and one repeated number where all numbers are in range 1 to n. MissingNumbers.java
19. Repeated dna sequence of length 10 - RepeatedDnaSequence.java

###Dynamic Programming###

1. Given a sequence of words, and a limit on the number of characters that can be put in one line (line width). Put line breaks in the given sequence such that the lines are printed neatly. TextJustification.java
2. Find longest bitonic subsequence in an array. Bitonic subsequence first increases and then decreases - BitonicSequence.java Youtube link
3. Given a long word which is made up of multiple words, split the long word into individual words - BreakMultipleWordsWithNoSpaceIntoSpace.java Youtube Link
4. Coin changing problem. Given set of coins and a total t. - CoinChanging.java CoinChangingMinimumCoin.java

• Total solutions possible to form t. Youtube link
• Minimum numbers of coin needed to form t. Youtube link

5. Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1′s - CountNumberOfBinaryWithoutConsecutive1s.java
6. Count number of trees that can be formed given a preorder sequence - CountNumberOfTreePreorder.java Youtube link
7. Count number of binary search trees formed by an array of size n - CountNumberOfTreesInBST.java Youtube link
8. Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces - CuttingRod.java Youtube link
9. Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown - DiceThrowWays.java
10. Given two strings of size m, n and set of operations replace (R), insert (I) and delete (D) all at equal cost. Find minimum number of edits (operations) required to convert one string into another - EditDistance.java Youtube link
11. Given number of floors and certain number of eggs, find the floor from which egg will break using minimum number of drops - EggDropping.java Youtube link
12. Given a bag which can only take certain weight W. Given list of items with their weights and price. Stuff these items in the bag such that it maximizes the value of bag - Knapsack01.java Youtube link
13. Given two strings. Find longest common subsequence/substring between the two strings - LongestCommonSubsequence.java Youtube link
14. Given an unsorted array. Find the longest increasing subsequence in this array - LongestIncreasingSubsequence.java Youtube Link
15. Given a sequence, find the length of the longest palindromic subsequence in it - LongestPalindromicSubsequence.java Youtube link
16. Given array of matrices, find a sequence which will have minimum multiplication cost - MatrixMultiplicationCost.java Youtube link
17. Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array - MaxSumForNonAdjacentElements.java
18. Given set of jobs with start and end interval and profit, how to maximize profit such that jobs in subset do not overlap - WeightedJobSchedulingMaximumProfit.java Youtube link
19. Find the longest chain which can be formed from a given set of pairs.In every pair, the first number is always smaller than the second number.Chain of pair (c, d) can follow another pair (a, b) if b < c - MaximumLengthChainPair.java
20. Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts - MaximumProductCutting.java
21. Given a matrix, find maximum size square sub matrix - MaximumSizeSubMatrix.java Youtube link
22. Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the integers in the subsequence are sorted in increasing order - MaximumSumSubsequence.java Youtube link
23. Given a cost matrix cost[][] and a position (m, n) in cost[][], write a function that returns cost of minimum cost path to reach (m, n) from (0, 0) - MinCostPath.java Youtube link
24. Given an array of integers where each element represents the max number of steps that can be made forward from that element. Write a function to return the minimum number of jumps to reach the end of the array - MinJumpToReachEnd.java Youtube link
25. Given an array of gold coins with different values and two players. Each player picks gold coin from either side. Write an algorithm to maximize your winning chance - NPotGold.java Youtube link
26. Given a matrix. Find total paths to reach from 0,0 to m,n in this matrix - NumberOfPathsInMxNMatrix.java Youtube link
27. Finding the number of ways a given score could be reached for a game with 3 different ways of scoring (e.g. 3, 5 and 10 points) - NumberOfWaysToScorePoints.java
28. Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible - OptimalTreeSearch.java
29. Given a string, partition the string with fewest cuts such that each partition is a palindrome - PalindromePartition.java Youtube link
30. Remove minimum number of elements from either end of array such that 2*min > max in this remaining elements of array - RemoveFromEndToMake2IntoMinGreaterThanMax.java
31. Given a matrix, find a rectangular submatrix with maximum sum - SubRectangularMatrixWithMaximumSum.java
32. Given an array and a total. Tell if elements of this array can form this total - SubsetSum.java Youtube link
33. Given an array of X and Os. Find largest subsquare which is surrounded by Xs - SubsquareSurrounedByXs.java
34. Given three strings, determine if first two strings can interleave to form third string - TwoStringInterleavingToFormThird.java Youtube link
35. Given a number n, find all numbers from 1 to n which are multiples of 2,3 or 5 only. UglyNumbers.java
36. Given the mobile numeric keypad. You can only press buttons that are up,left,right or down to the current button.You are not allowed to press bottom row corner buttons (i.e. * and # ).Given a N find out the number of numbers possible of given length - PhoneDialNumberOfCombinationOfSizeK.java
37. Given a keyboard which only does 4 things, print A, select screen, copy screen and append to screen and given n, how many total As you can print on screen. CountAs.java
38. Given an array, find a sequence of equal length such that sum of each half is same LongestEvenLengthSubstringOffEqualHalf.java
39. Longest common substring between two strings. LongestCommonSubstring.java Youtube link
40. There are N stations on route of a train. The train goes from station 0 to N-1. The ticket cost for all pair of stations (i, j) is given where j is greater than i. Find the minimum cost to reach the destination. MinimumCostTrainTicket.java
41. Fibonacci series FibonacciSeries.java Youtube link
42. Given a 2D array of 0s and 1s, find size of maximum rectangular submatrix - MaximumRectangularSubmatrixOf1s.java
43. Given boxes of different dimensions, stack them on top of each other to get maximum height. But box on top should have strictly less length and width then box under it. BoxStacking.java
44. Given a rod with markings. Cut the rod along markings but reduce the cost of cutting. Cost if cutting is proportional to the length of rod being cut.CutRodToMinimizeCost.java
45. Given two strings, tell if one string is scrambled of another or not. Read question on the code to see what scrambled means. ScrambledString.java
46. Maximize Ski gates passage MaximizeSkiGates.java
47. Given stock prices for certain days how to maximize profit by buying or selling with at most K transactions StockBuySellKTransactions.java stockbuysellktransactions.py
48. Given symbols expression and binary operation result b/w symbols, tell if given expression with any parenthesis combination can produce a given result. SymbolExpressionEvaluation.java symbolexpressionevaluation.py
49. Given expression with +, -, *, / operators, tell if given expression with any parenthesis combination can produce a given result. ExpressionEvaluation.java
50. Given balloons with certain values in what order should you burst them to get max value. BurstBalloons.java

###Graph###

1. A vertex in an undirected connected graph is an articulation point (or cut vertex) iff removing it (and edges through it) disconnects the graph. ArticulationPoint.java
2. Find shortest path from one vertex to all vertex using bellman ford algorithm - BellmanFordShortestPath.java
3. Binary max heap - BinaryMaxHeap.java
4. Binary min heap - BinaryMinHeap.java
5. A Bipartite Graph is a graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U - BiparteGraph.java
6. Design a game of boggle - Boggle.java
7. An edge in an undirected connected graph is a bridge iff removing it disconnects the graph. Given a graph find all bridges in this graph - Bridge.java
8. Given two words of equal length convert first word to second word in such a way that all intermediate words are in dictionary - ConvertOneWordToAnother.java
9. Find cycle in directed graph - CycleInDirectedGraph.java
10. Find cycle in undirected graph - CycleUndirectedGraph.java
11. Given a directed acyclic graph(DAG) find shortest path from one vertex to all vertices - DAGShortestPathTopological.java
12. Given a graph with weighted edges, find shortest path from one vertex to all vertices - DijkstraShortestPath.java
13. Given a directed graph, return true if you can reach every node of graph from any node else false - DirectedGraphConnectivity.java
14. Given a graph, tell if it is eulirian, semi eulirian or non eulirian - EulerianPathAndCircuit.java
15. Given a 2D matrix of Xs and Os, convert all Os to Xs if it is surrounded by Xs - FillOsWIthXsIfSurroundedByXs.java
16. Flood fill algorithm - FloodFillAlgorithm.java
17. All pair shortest path using flyod warshall algorithm - FloydWarshallAllPairShortestPath.java
18. Given a directed graph with source and end point, find maximum flow from source to end - FordFulkerson.java
19. Graph basic data structure - Graph.java
20. Given a graph, color each vertex such that neighboring vertex does not have same color - GraphColoring.java
21. BSF and DFS graph traversal - GraphTraversal.java
22. Given a graph, find hamiltonian cycle in the graph if it exists. Hamiltonian cycle in undirected graph starts and ends at same point and traverses each vertex exactly once - HamiltonianCycle.java
23. Find minimum spanning tree using Krushkal's algorithm - KrushkalMST.java
24. A matching in a Bipartite Graph is a set of the edges chosen in such a way that no two edges share an endpoint - MaximumBiparteMatching.java
25. Given a graph of 0s and 1s, find total number of islands of 1s - NumberOfIsland.java
26. Given a graph, find total number of triangles in the graph - NumberofTriangles.java
27. Prim's algorithm for minimum spanning tree - PrimMST.java
28. Print all paths from source to destination in undirected graph - PrintAllPathFromSourceToDestination.java
29. Given a directed graph, find strongly connected components of the graph - StronglyConnectedComponent.java
30. Given a directed acyclic graph, sort is topologically - TopologicalSort.java
31. Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph - TransitiveClosure.java
32. Clone directed graph - CloneDirectedGraph.java
33. Disjoint set using path compression and union by rank DisjointSet.java
34. Given a 2D floor plan of empty spaces, walls and multiple exits. Find distance of every empty space to closest exit. ShortestDistanceFromExit.java
35. Tarjan's strongly connected component - TarjanStronglyConnectedComponent.java
36. Tarjan's algorithm to find all simple cycles in directed graph - AllCyclesInDirectedGraphTarjan.java
37. Johnson's algorithm for finding all cycles in directed graph - AllCyclesInDirectedGraphJohnson.java
38. Traveling salesman problem using Held Karp Dynamic programming method - TravelingSalesmanHeldKarp.java
39. Given a graph representing tree find minimum height tree - MinimumHeightTree.java

###LinkList###

1. Add two numbers represented by link list - AddNumberRepresentedByLinkList.java
2. Create a copy of a link list in which one pointer points to next node while other pointer can point to any node in the list - CopyLinkListWIthArbitPointer.java
3. Given a linklist, delete m nodes after every n nodes - DeleteNAfterMNodes.java
4. Delete nodes which has greater value on right side - DeleteNodeWithGreaterValueOnRight.java
5. Given a linklist in which down pointer could point to another linklist and this happens recursively, flatten this linklist - FlattenLinkList.java
6. Implement a LRU cache using linklist and map - LRUCache.java
7. Basic link list structure - LinkList.java
8. Sort linklist using merge sort - MergeSortLinkList.java
9. Quick sort linklist - QuickSortSingleLinkList.java
10. Remove duplicates from a sorted linklist - RemoveDuplicatesSortedList.java
11. Given a linklist and k,reverse alternate k nodes in the linklist - ReverseAlternateKNodes.java
12. Given a linklist, reverse alternate nodes and append it at the end - ReverseAlternateNodeAndAppendAtEnd.java
13. Reverse every k nodes in a linklist - ReverseKNodes.java
14. Sort a nearly sorted linklist - SortNearlySortedList.java
15. Insert into sorted circular linklist - SortedCircularLinkList.java
16. Given a sorted linklist, convert it into a balanced binary search tree - SortedLLToBalancedBST.java
17. Stack with also support find/delete middle operation - StackWithLinkListMiddleOperation.java
18. Given three linklist and a sum, find a triplet from each list which adds up to sum - TripletToSumInLinkList.java
19. Insertion sort for link list - InsertionSortLinkList.java
20. Double link list - DoubleLinkList.java
21. Given two nodes of double link list swap them - SwapTwoNodesInDoubleLL.java
22. Given a linklist, return true if elements form a palindrome or not - LinkListIsPalindrome.java
23. Multiply two numbers given in form of linklist. Result should also be linklist - MultiplyTwoNumbersLinkList.java
24. Convert linklist to complete binary tree - LinkListToCompleteBinaryTree.java
25. Given a linklist, find middle element of the linklist - MiddleElementOfLinkList.java
26. Shuffle merge linklist - ShuffleMerge.java
27. Given a linked list of co-ordinates where adjacent points either form a vertical line or a horizontal line. Delete points from the linked list which are in the middle of a horizontal or vertical line.RemoveMiddleElementsOfLineSegment.java
28. Find if there is a loop in linklist LoopInLinkList.java
29. Given two sorted linked lists, construct a linked list that contains maximum sum path from start to end. The result list may contain nodes from both input lists. MergeForLargestSum.java

###Multi Array###

1. Given a boolean matrix mat[M][N] of size M X N, modify it such that if a matrix cell mat[i][j] is 1 (or true) then make all the cells of ith row and jth column as 1 - Fill2DMatrixWith1.java
2. Design game of life - GameOfLife.java
3. Find the length of the longest chain of consecutive integers in an unsorted 2D square array (non-diagonal) - LongestConsecutiveIntegerInUnsorted2DArray.java
4. Given a 2D array, create a new 2D array which joins first row elements with every other element from second row onwards - MatrixCalculation.java
5. Given a 2D array, find sum of all rectangular and square sub matrix - MatrixFindAllSubSquareRectangleMatrix.java
6. Print a 2D array in diagonal format - MatrixInDiagonalOrder.java
7. Create a 2D array of alternating Xs and 0s rectangles - MatrixOf0sAnd1s.java
8. Move in 2D array as per cell value - MoveCellPerCellValue.java
9. Turn image by 90 degree - TurnImageBy90.java
10. Given a n by n board where n is of form 2k where k >= 1 (Basically n is a power of 2 with minimum value as 2). The board has one missing cell (of size 1 x 1). Fill the board using L shaped tiles. TilingProblem.java
11. Print matrix in spiral way - SpiralPrinting.java

###Numbers###

1. Given a large number tell where it is an aggregate number or not - AggregateNumber.java
2. Given an array of sorted numbers, tell if there are 3 numbers which form arithmetic progression - ArithemeticProgressionExists.java
3. Given two numbers in form of an array, multiply them - ArrayMultiplication.java
4. Given a number n and k, find binomial coefficient of n to k - BinomialCoefficient.java
5. Covert a decimal number into any other base N < 10 - ConvertToBaseN.java
6. Given a number n, find counts of 2 from 1 to n - CountNoOf2s.java
7. Given a number n, find number of numbers which does not have digit 4 in them - CountNumbersNotIncluding4.java
8. Given a dividend and a divisor, return remainder and quotient - DivisionWithoutDivisionOperator.java
9. Given two numbers find their GCD(greatest common divisor) - EuclideanAlgoForGCD.java
10. Given an array of numbers, generate a signature where D represent decrease and I represents increase. Now given Ds and Is generate pattern of number - GenerateSignature.java
11. Given an array, find elements combining which forms largest multiple of 3 - https://github.com/mission-peace/interview/blob/master/src/com/interview/number/LargestMultipleOf3inArray.java
12. Given a number n, tell if this number is a lucky number - LuckyNumbers.java
13. Given an array of 3 numbers, find their median - https://github.com/mission-peace/interview/blob/master/src/com/interview/number/MedianOf3Number.java
14. Write a program to determine whether n/2 distinctinctive pairs can be formed from given n integers where n is even and each pair's sum is divisible by given k - NBy2PairSumToK.java
15. Given an array representing a number, find next larger palindrome which can be formed - NextLargestPalindrome.java
16. Given a chinese number which never has 4, convert it into decimal format - NotIncluding4.java
17. Given an array representing a number, return a new array consisting of same numbers but larger than this number - PermutationBiggerThanNumber.java
18. Given two arrays representing numbers, convert first array into number which is next larger than second array - PermutationLargerThanGivenArray.java
19. Calculate power function using divide and conquer - PowerFunction.java
20. Given an array of numbers, arrange them in a way that yields the largest value - RearrangeNumberInArrayToFormLargestNumber.java
21. Russian peasant multiplication - RussianPeasantMultiplication.java
22. Smallest number greater than given number but all digits in increasing order - SmallestNumberGreaterThanGiveNumberIncreasingSequence.java
23. Calculate square root of a number without using any library - SquareRoot.java
24. Given a positive integer n, generate all possible unique ways to represent n as sum of positive integers -https://github.com/mission-peace/interview/blob/master/src/com/interview/number/UniquePartitionOfInteger.java
25. A man is walking up a set of stairs. He can either take 1 or 2 steps at a time. Given n number of steps,find out how many combinations of steps he can take to reach the top of the stairs - NumberOfCombinationsForStairs.java
26. Given a number, find number of trailing zeros in the factorial of this number - Trailing0sinFactorial.java
27. Factorial of a large number - FactorialOfLargeNumber
28. Find mth number in array of [1..n] where m is defined by lexicographically order - MthNumberInNSizeArray.java

###Tree###

1. Self balancing tree AVL tree - AVLTree.java
2. Given an arbitrary binary tree, convert it to a binary tree that holds Children Sum Property. You can only increment data values in any node - ArbitaryTreeToChildSumTree.java
3. Given Preorder traversal of a BST, check if each non-leaf node has only one child. Assume that the BST contains unique entries - BSTOneChildPreOrderTraversal.java
4. Btree implementation - BTree.java
5. Binary tree operations - BinaryTree.java
6. Convert a binary tree to circular link list - BinaryTreeToCircularLinkList.java
7. Write a function to connect all the adjacent nodes at the same level in a binary tree - ConnectNodesAtSameLevel.java
8. Given two arrays that represent preorder and postorder traversals of a full binary tree, construct the binary tree - ConstructFullTreeFromPreOrderPostOrder.java
9. Construct tree from preorder and inorder traversal - ConstructTreeFromInOrderPreOrder.java
10. Given inorder and level-order traversals of a Binary Tree, construct the Binary Tree - ConstructTreeFromLevelOrderInOrder.java
11. Write a function to count number of smaller elements on right of each element in an array - CountNumberOfSmallerElementOnRight.java
12. Given binary tree and two nodes, tell if these two nodes are cousins of each other or not - CousinNodes.java
13. Diameter of binary tree - DiameterOfTree.java
14. Huffman encoding - HuffmanEncoding.java
15. Given two arrays which represent a sequence of keys. Imagine we make a Binary Search Tree (BST) from each array. We need to tell whether two BSTs will be identical or not without actually constructing the tree - IdenticalTrees.java
16. Given a binary tree, find largest BST in this binary tree - LargestBSTInBinaryTree.java
17. Given a Binary Tree, find size of the Largest Independent Set(LIS) in it. A subset of all tree nodes is an independent set if there is no edge between any two nodes of the subset - LargestIndependentSetInTree.java
18. Level order traversal of binary tree - LevelOrderTraversal.java
19. Create an iterator to traverse a binary tree. When the next function is called on the binary tree return the value at the next node as if you are doing an inorder traversal of the tree - NextInorderSuccessorIterator.java
20. Given a binary tree and a number k, print nodes at distance k from given node - NodesAtDistanceK.java
21. Populate inorder successor for all nodes - PopulateInOrderSuccessor.java
22. Inorder successor of two tree -NextInorderSucessorOfTwoTree.java
23. Given preorder traversal of a binary search tree, construct the BST - ConstructBSTFromPreOrderArray.java
24. Print two BST in sorted form - PrintTwoBSTInSortedForm.java
25. Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given number - RootToLeafToSum.java
26. Range query segment tree - SegmentTree.java segmenttreesum.py
27. Segment tree for minimum range query - SegmentTreeMinimumRangeQuery.java
28. Given a binary tree with positive and negative numbers, sink negative numbers to the bottom of the tree - SinkNegativeToBottom.java
29. Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order - SortedOrderPrintCompleteTreeArray.java
30. Write a function that returns true if the given Binary Tree is SumTree else false. 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 - SumTree.java
31. Inorder,preorder,postorder,morris travesals - TreeTraversals.java
32. Given a binary tree, print it vertically - VerticalTreePrinting.java
33. Given a Binary Search Tree (BST), modify it so that all greater values in the given BST are added to every node - AddGreaterValueNodeToEveryNode.java
34. Print all nodes with no sibling - NodesWithNoSibling.java
35. Boundary traversal of binary tree - BoundaryTraversal.java
36. Convert a binary tree into double link list - BinaryTreeToDoubleLinkList.java
37. Given a binary tree, tell if it is a complete tree or not. IsCompleteBinaryTree.java
38. Given a preorder traversal of a tree with 0 or 2 children and char array where L stands for leaf node and N stands for inner node, create binary tree from it - ConstructTreeFromPreOrderTraversalWith0or2Child.java
39. Convert a binary tree(not BST) to a sorted link list - BinaryTreeToSortedLinkList.java
40. Given an inorder traversal of tree where each node is greater than its child nodes, create binary tree - ContructTreeFromInOrderTraversalRootGreaterThanChild.java
41. Given two nodes value find lowest common ancestor of these two nodes - LowestCommonAncestorInBinaryTree.java
42. Write a function to detect if two trees are isomorphic. Two trees are called isomorphic if one of them can be obtained from other by a series of flips - TreeIsomorphism.java
43. Vertex cover for binary tree using DP - VertexCoverBinaryTreeDP.java
44. Convert a binary tree(Not BST) to sorted linklist. DegenerateBinaryTreeToSortedLL
45. Search in binary search tree - BSTSearch.java
46. Given a binary tree, return true if is binary search tree else return false -IsBST.java
47. Given two tree return true if they represent same tree else return false. SameTree.java
48. Tree traversal in level and spiral order - TreeTraversalInSpiralOrder.java
49. Tree traversal printing each level on new line - TreeTraversalLevelByLevel.java
50. Level order traversal in reverse - LevelOrderTraversalInReverse.java
51. Fenwick tree - FenwickTree.java
52. Red black tree - RedBlackTree.java
53. Given an preorder sequence determine if it is of binary search tree or not IsPreOrderArrayBST.java
54. Succinct encoding/decoding of binary tree SuccinctTree.java
55. Create binary tree from parent representation - BinaryTreeFromParentRepresentation.java
56. Given pre/inorder traversal of binary tree, create post order traversal - PrintPostOrderFromPreOrderInOrder.java
57. Construct all binary search tree from inorder traversal ConstructAllBinaryTreeFromInorderTraversal.java
58. Interval tree IntervalTree.java
59. Morris inorder/preorder traversal of tree - MorrisTraversal.java

###String###

1. Given two strings tells if anagram of first is substring of another - AnagramOfFirstAsSubstring.java
2. Cycle leader iteration - CycleLeaderIteration.java
3. Given alternate digits and numbers, move them so that all digits are on one side and numbers on other side - InPlaceTransformationOfString.java
4. Lexicographic rank of a string - LexicographicRankInPermutation.java
5. Given a string, find longest palindromic substring in this string - LongestPalindromeSubstring.java
6. Given a string find longest substring without repetition of characters - LongestSubstringWithoutRepetingCharacter.java
7. Given an input string S write a function which returns true if it satisfies S = nT - NTMatch.java
8. Given list of strings, print them in groups if they are anagrams of each other - PrintAnagramTogether.java
9. Rabin karp substring search - RabinKarpSearch.java
10. Given a string, rearrange characters in string so that characters are at least d distance away from repeated characters - RearrangeDuplicateCharsdDistanceAway.java
11. Regex matching - RegexMatching.java
12. Run length encoding - RunLengthEncoding.java
13. Given two strings, find smallest window in first string which contains all characters of second string - SmallestWindowContaingAllCharacters.java
14. KMP substring search - SubstringSearch.java
15. Wild card searching - WildCardSearch.java
16. Remove consecutive duplicate elements in character array - RemoveConsecutiveDuplicate.java
17. Print all combinations of word abbreviation WordAbbreviationCombination.java

###Recursion###

1. Generate all combination of size k and less of adjacent numbers - AllAdjacentCombination.java
2. Generate all bracket combination, check if brackets open and closing is correct or not - Bracketology.java
3. Given an array of strings, find if the given strings can be chained to form a circle. A string X can be put before another string Y in circle if the last character of X is same as first character of Y - ChainWordsToFormCircle.java
4. Generate all combinations - Combination.java
5. Generate all combination of size k - CombinationOfSizeK.java
6. Generate all combination which prints star in place of absent characters - CombinationWithStar.java
7. Consider a coding system for alphabets to integers where ‘a’ is represented as 1, ‘b’ as 2, .. ‘z’ as 26. Given an array of digits (1 to 9) as input, write a function that prints all valid interpretations of input array - InterpretationOfArray.java
8. Generate all possible string combinations of a given phone number - KeyPadPermutation.java
9. Minimum edits required to generate reverse polish notation - MinimumEditForReversePolishNotation.java
10. Given a board of size nxn and n queens, place them on the board so that they don't attack each other - NQueenProblem.java
11. Given two strings check if they are one distance away from each other where you can delete,edit or add characters - OneEditApart.java
12. Print all paths from top left corner to bottom right corner - PrintAllPathFromTopLeftToBottomRight.java
13. Given an array find number of interpretations possible for combinations of adjacent characters - PrintArrayInAdjacentWay.java
14. Print array in tree fashion - PrintArrayInCustomizedFormat.java
15. Permutation of string in both sorted and unsorted order - StringPermutation.java stringpermutation.py StringPermutationRotation.java
16. Given two strings, generate all interleavings of these strings - StringInterleaving.java
17. Shuffle a character array so that no two repeated characters are together. [FancyShuffle.java] (https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/FancyShuffle.java)
18. Given an input and total, print all combinations with repetitions in this input which sums to given total. PrintSumCombination.java
19. Given a List of List of Strings. Print cartesian product of List. WordCombination.java
20. Given input of unique elements and pair among those elements. How many minimum swaps are needed to arrange pair adjacent to each other. SetPairTogether.java setpairtogether.py
21. Given input string e.g 123 and target e.g 6, place operator +, - and * so that 123 evaluates to 6. OperatorAdditionForTarget.java
22. Print all permutations of given input array - PrintAllSubsequence.java
23. Reconstruct itinerary based on ticket - ReconstructItinerary.java

###Suffix/Prefix Tree###

1. A suffix array is a sorted array of all suffixes of a given string. Given an array create suffix array for it - SuffixArray.java
2. A ternary search tree is a special trie data structure where the child nodes of a standard trie are ordered as a binary search tree. Write a program to insert and search in ternary tree - TernaryTree.java
3. Write a program to insert,search and delete in trie - Trie.java
4. Ukkonen's suffix tree - SuffixTree.java
5. Z algorithm for pattern matching ZAlgorithm.java

###Sorting###

1. Counting sort - CountingSort.java
2. Iterative quick sort - IterativeQuickSort.java
3. Pancake sorting - PanCakeSorting.java
4. Quick sort - QuickSort.java
5. Radix sort - RadixSort.java
6. Sort an array in range of 0 to N^3(or 0 to N^2) - Sort0toN3.java
7. Sort an array by frequency of number in that array - SortArrayByFrequence.java
8. Merge sort MergeSort.java
9. Heap sort HeapSort.java

###Multithreading### 2. Executor service example - ThreadPoolExample.java 3. Thread pool implementation - ThreadPoolImpl.java 4. Given a queue which gets millions of messages. Message is of form <Domain,Update>.You have 10000 domain tables. Also you have 50 worker threads. You can only get data from front of the queue. Threads get data from the front and then update the domain table - SingleQueueDomainTableUpdate.java 4. Design a spinlock mutex using two varialbles - SpinLockMutex.java 5. Design threadsafe real time counter - RealTimeCounter.java 6. Design threadsafe program to keep counts of word - CountingWord.java 7. Fill up 2D boolean matrix in thread safe way from top left to bottom right - FillupMatrix.java 8. Design threadsafe program to keep min and max - MinMaxKeeper.java 9. BoundedBlockingQueue implementation(producer consumer) - BoundedBlockingQueue.java

###Regex###

1. Given a sentence with multiple spaces between words and also spaces in front and back of sentence how do you remove these extra spaces - MultiSpaceReplacement.java

###Randomization###

1. Given a method to generate random number between 1 to 5, create a new method to generate random number between 1 to 7 - Rand7UsingRand5.java
2. Given a list of countries with population, how do you select random country from this list. Higher the population higher the probability of selection - RandomCountrySelectionByPopluation.java
3. Reservior sampling algorithm. In stream of numbers select k random numbers - SelectMRandomNumbersInStream.java
4. Given an array shuffle it - ShuffleArray.java

###Stack Queues###

1. Implement a circular queue using an array of fixed size - CircularQueue.java
2. Find maximum size rectangle in histogram - MaximumHistogram.java
3. Move from current folder to new folder as specified in argument - MoveFromCurrentToNewFolder.java
4. Reverse stack using recursion - ReverseStackUsingRecursion.java
5. Given a string with unbalanced brackets how do you remove minimum number of extra brackets so that you are left with balanced brackets in the string - RemoveExtraBrackets.java
6. Remove duplicates from a string while maintaining order and getting lexicographically smallest string - RemoveDuplicateMaintainingOrder.java
7. Find median in stream of numbers - MedianFinder.java

###Geometry###

1. Given points with x and y coordinates. Find distance between closest pair of points among the given points. ClosestPairOfPoints.java
2. Given skyline of city with overlapping buildings. Merge the buildings. SkylineDrawing.java
   skylinedrawing.py

###Misc###

1. Given two sets of intervals. Ranges in the same set do not overlap each other. Merge these sets - AddingTwoSetOfIntervals.java
2. Given a time(hour and min), find angle between hour and min hand - AngleBetweenHourAndMinuteHand.java
3. Given an excel sheet kind of numbering, convert it into decimal and vice versa - ConvertNumberIntoBase26.java
4. Given two dates in AD, find number of days between these 2 dates - DayDifferenceBetweenTwoDates.java
5. Given a floating point number in string, convert it into actual float number - FloatPointConversion.java
6. Given an array, find hamming distance between each pair of numbers in the array - HammingDistanceBetweenPair.java
7. Given horizons of building in form of height and start end point, merge them into single horizon - HorizonMapping.java
8. kth largest element in row wise and column wise sorted 2D array - KthLargestInRowiseColumnWiseSorted2DArray.java
9. Design a load balancer where you can add,remove and find random server in O(1) time - LoadBalancers.java
10. Given an integer, return a string which represents this integer in words - NumberToWord.java
11. Convert a roman number into decimal number and vice versa - RomanNumberToDecimal.java
12. Given cordinates of four points, say if they will form a square or not - FourPointsFormSquare.java
13. Given two times in 4 digit number, find difference between them - DifferenceBetweenTwoTime.java
14. All prime numbers before n - PrimeNumbersBeforeN.java
15. How to give minimum number of candies to children with ratings. Every child with higher rating should get more candy then its neighbor with lower rating. Everyone should get at least one candy. CandiesProblem
16. Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive - CountRanges.java