Skip to content

Home

Jump to bottom Edit New page
mission-peace edited this page Aug 13, 2014 · 279 revisions

Interview Questions##

###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
  1. Given an array of elements check if elements in the array are consecutive or not. - CheckIfArrayElementsAreConsecutive.java
  2. Given elements in array divide elements into two groups of closest possible sum Conflict with TugOfWar - DivideNumbersInEqualGroupWithClosestSum.java
  3. Write a function to determine if array contains duplicate elements within k distance from each other - DuplicateWithinkIndices.java
  4. Given an array and a number k < n, find all elements occurring more than n by k times - FindElementsOccurringNByKTimesTetris.java
  5. Given a list of gas stations and amount of fuel they have, find a tour which travels all gas stations - GasStationCircle.java
  6. 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
  7. Given an array find an increasing subsequence of length 3 which has maximum product - IncreasingSubsequnceOfLength3WithMaxProduct.java
  8. Given an array find maximum circular contiguous sum - KadaneWrapArray.java
  9. kth largest element in an unsorted array using quick select - KthElementInArray.java
  10. kth largest element in two sorted array - KthLargestInTwoSortedArray.java
  11. Print next greater element for every element in array - LargerElementOnRight.java
  12. Given an array of 0s and 1s find the largest subarray with equal number of 0s and 1s - LargestSubArrayWithEqual0sAnd1s.java
  13. Longest increasing subsequence in an array with O(logN) speed - LongestIncreasingSubSequenceOlogNMethod.java
  14. Given an array maximize i - j such that a[i] > a[j] - MaximumIminusJSuchThatAiGTAj.java
  15. Given an array, find maximum of all subarrays of size k - MaximumOfSubarrayOfSizeK.java
  16. Given an array of positive and negative numbers, find a subarray which has maximum product - MaxProductSubarray.java
  17. 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
  18. Given an array and two numbers, find minimum distance between these numbers. There could duplicates of these numbers in array - MinimumDistanceBetweenTwoNumbers.java
  19. Find minimum length unsorted subarray, sorting which makes entire array sorted - MinimumSortedWhichSortsEntireArray.java
  20. Given array of 0 and non zero numbers, move all 0s to the end in O(n) time - MoveAllZerosToEnd.java
  21. Given an array, return a new array which has multiplication of all elements except own index - MultiplyAllFieldsExceptOwnPosition.java
  22. Given an unsorted array, find total number of triangles formed taking 3 elements of this array - NumberOfTrianglesInUnsortedArray.java
  23. Given an array with first negative and then positive numbers, position negative and positive numbers alternately - PositiveAndNegativeNumberAlternatively.java
  24. 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
  25. 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
  26. Stable marriage problem - StableMarriageProblem.java
  27. Given an unsorted array of nonnegative numbers , find a contiguous subarray with given sum - SubarrayWithGivenSum.java
  28. 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
  29. 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 - Conflict with DivideNumbersInEqualGroupWithClosestSum - TugOfWar.java
  30. Given an unsorted array convert it into a < b > c < d > e < f > g fashion - ConvertAnArrayIntoDecreaseIncreaseFashion.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

###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. AdjustWordsInLine.java
  2. Find longest bitonic subsequence in an array. Bitonic subsequence first increases and then decreases - BitonicSequence.java
  3. Given a long word which is made up of multiple words, split the long word into individual words - BreakMultipleWordsWithNoSpaceIntoSpace.java
  4. Coin changing problem. Given set of coins and a total t. - CoinChanging.java
  • Total solutions possible to form t.
  • Minimum numbers of coin needed to form t.
  1. Given a positive integer N, count all possible distinct binary strings of length N such that there are no consecutive 1′s - CountNumberOfBinaryWithoutConsecutive1s.java
  2. Count number of trees that can be formed given a preorder sequence - CountNumberOfTreePreorder.java
  3. Count number of binary search trees formed by an array of size n - CountNumberOfTreesInBST.java
  4. 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
  5. 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
  6. 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
  7. Given number of floors and certain number of eggs, find the floor from which egg will break using minimum number of drops - EggDropping.java
  8. 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
  9. Given two strings. Find longest common subsequence/substring between the two strings - LongestCommonSubsequence.java
  10. Given an unsorted array. Find the longest increasing subsequence in this array - LongestIncreasingSubsequence.java
  11. Given a sequence, find the length of the longest palindromic subsequence in it - LongestPalindromicSubsequence.java
  12. Given array of matrices, find a sequence which will have minimum multiplication cost - MatrixMultiplicationCost.java
  13. 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
  14. Given set of jobs with start and end interval and profit, how to maximize profit such that jobs in subset do not overlap - MaximizeProfitWithJob.java
  15. 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
  16. 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
  17. Given a matrix, find maximum size square sub matrix - MaximumSizeSubMatrix.java
  18. 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 intgers in the subsequence are sorted in increasing order - MaximumSumSubsequence.java
  19. 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
  20. 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
  21. 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
  22. Given a matrix. Find total paths to reach from 0,0 to m,n in this matrix - NumberOfPathsInMxNMatrix.java
  23. 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
  24. Given a string, partition the string with fewest cuts such that each partition is a palindrome - PalindromePartition.java
  25. Remove minimum number of elements from either end of array such that 2*min > max in this remaining elements of array - RemoveFromEndToMake2IntoMinGreaterThanMax.java
  26. Given a matrix, find a rectangular submatrix with maximum sum - SubArrayWithMaximumSum.java
  27. Given an array and a total. Tell if elements of this array can form this total - SubsetSum.java
  28. Given an array of X and Os. Find largest subsquare which is surrounded by Xs - SubsquareSurrounedByXs.java
  29. Given three strings, determine if first two strings can interleave to form third string - TwoStringInterleavingToFormThird.java
  30. Given a number n, find all numbers from 1 to n which are multiples of 2,3 or 5 only. UglyNumbers.java
  31. 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

###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. Path compression and rank algorithm - PathCompressionAndRank.java
  28. Prim's algorithm for minimum spanning tree - PrimMST.java
  29. Print all paths from source to destination in undirected graph - PrintAllPathFromSourceToDestination.java
  30. Given a directed graph, find strongly connected components of the graph - StronglyConnectedComponent.java
  31. Given a directed acyclic graph, sort is topologically - TopologicalSort.java
  32. 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

###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. Given two linklist, insert nodes of second list into first list at alternate position - InsertNodesAtAlternatePosition.java
  7. Implement a LRU cache using linklist and map - LRUCache.java
  8. Basic link list structure - LinkList.java
  9. Sort linklist using merge sort - MergeSortLinkList.java
  10. Quick sort linklist - QuickSortSingleLinkList.java
  11. Remove duplicates from a sorted linklist - RemoveDuplicatesSortedList.java
  12. Given a linklist and k,reverse alternate k nodes in the linklist - ReverseAlternateKNodes.java
  13. Given a linklist, reverse alternate nodes and append it at the end - ReverseAlternateNodeAndAppendAtEnd.java
  14. Reverse every k nodes in a linklist - ReverseKNodes.java
  15. Sort a nearly sorted linklist - SortNearlySortedList.java
  16. Insert into sorted circular linklist - SortedCircularLinkList.java
  17. Given a sorted linklist, convert it into a balanced binary search tree - SortedLLToBalancedBST.java
  18. Stack with also support find/delete middle operation - StackWithLinkListMiddleOperation.java
  19. Given three linklist and a sum, find a triplet from each list which adds up to sum - TripletToSumInLinkList.java
  20. Insertion sort for link list - InsertionSortLinkList.java
  21. Double link list - DoubleLinkList.java
  22. Given two nodes of double link list swap them - SwapTwoNodesInDoubleLL.java
  23. Given a linklist, return true if elements form a palindrome or not - LinkListIsPalindrome.java
  24. Multiply two numbers given in form of linklist. Result should also be linklist - MultiplyTwoNumbersLinkList.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

###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 a series of numbers as the input, the last one as the result.Use the rest numbers to calculate the result,only +, -, *, / are allowed - ArithmeticOperatorForFinalResult.java
  4. Given two numbers in form of an array, multiply them - ArrayMultiplication.java
  5. Given a number n and k, find binomial coefficient of n to k - BinomialCoefficient.java
  6. Covert a decimal number into any other base N < 10 - ConvertToBaseN.java
  7. Given a number n, find counts of 2 from 1 to n - CountNoOf2s.java
  8. Given a number n, find number of numbers which does not have digit 4 in them - CountNumbersNotIncluding4.java
  9. Given a dividend and a divisor, return remainder and quotient - DivisionWithoutDivisionOperator.java
  10. Given two numbers find their GCD(greatest common divisor) - EuclideanAlgoForGCD.java
  11. 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
  12. 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
  13. Given a number n, tell if this number is a lucky number - LuckyNumbers.java
  14. Given an array of 3 numbers, find their median - https://github.com/mission-peace/interview/blob/master/src/com/interview/number/MedianOf3Number.java
  15. 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
  16. Given an array representing a number, find next larger palindrome which can be formed - NextLargestPalindrome.java
  17. Given a chinese number which never has 4, convert it into decimal format - NotIncluding4.java
  18. Given an array representing a number, return a new array consisting of same numbers but larger than this number - PermutationBiggerThanNumber.java
  19. Given two arrays representing numbers, convert first array into number which is next larger than second array - PermutationLargerThanGivenArray.java
  20. Calculate power function using divide and conquer - PowerFunction.java
  21. Given an array of numbers, arrange them in a way that yields the largest value - RearrangeNumberInArrayToFormLargestNumber.java
  22. Russian peasant multiplication - RussianPeasantMultiplication.java
  23. Smallest number greater than given number but all digits in increasing order - SmallestNumberGreaterThanGiveNumberIncreasingSequence.java
  24. Calculate square root of a number without using any library - SquareRoot.java
  25. 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

###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 and spiral level order traversal - 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. Given preorder traversal of a binary search tree, construct the BST - PreOrderArrayToBST.java
  23. Print two BST in sorted form - PrintTwoBSTInSortedForm.java
  24. 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
  25. Range query segment tree - SegmentTree.java
  26. Given a binary tree with positive and negative numbers, sink negative numbers to the bottom of the tree - SinkNegativeToBottom.java
  27. Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order - SortedOrderPrintFullTreeArray.java
  28. 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
  29. Inorder,preorder,postorder,morris travesals - TreeTraversals.java
  30. Given a binary tree, print it vertically - VerticalTreePrinting.java
  31. Given a Binary Search Tree (BST), modify it so that all greater values in the given BST are added to every node - AddGreaterValueNodeToEveryNode.java
  32. Print all nodes with no sibling - NodesWithNoSibling.java
Add a custom footer
Add a custom sidebar

Clone this wiki locally