Skip to content

Home

Jump to bottom Edit New page
mission-peace edited this page Jul 30, 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

###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
Add a custom footer
Add a custom sidebar

Clone this wiki locally