PLEASE FILE AN ISSUE IN CASE OF A BUG OR ADD A COMMENT. Feel free to email me: [email protected] with issues or new problems.

A COMPILATION OF COMMON INTERVIEW QUESTIONS AND SOLUTIONS.

Note - This compilation is to give an overview of different types of interview questions. Obviously, it won't cover all of the interview questions since possibilities are endless :). Some solution may not be optimal but still would give you an idea about the question types.

Sections:---

Arrays

1. Given +ve numbers in an array.Put the even #s to the left of the array and the odd to the right side of the array . Don't use extra array. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/allevennumberstoleft/AllEvensToLeftandOddsToRight.java

2. Given M * N matrix find count of all distinct paths from top left cell to bottom right. You can only move downwards and to the right from a given cell. Link:

3. Given a sequence of non-negative integers find a subsequence of length 3 having maximum product with the numbers of the subsequence being in ascending order. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/ascsubsequencemaxproduct/SubsequenceProduct.java

4. Shift array of integers circularly given input array and shift size. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/circularshiftintarray/CircularShiftArray.java

5. 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. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/fillmatrixwithones/FillBinaryMatrixWithOnes.java

6. Check if a sub-array exists in parent array. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/findarray/FindArrayImpl.java

7. Find duplicates count in sorted array. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/findduplicatecountsortedarray/DuplicatesCountInSortedArray.java

8. Write a program takes array input{1,0,2,3} and num = 3 and provides output {1,2}{0,3}{2,1}{3,0} sum equals the num. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/findpairsequaltosum/FindPairsEqualToSum.java

9. Given a sorted array (ascending order and distinct elements), find i such that inputArr[i] = i. Return -1 if nothing found. Link:

10. Find the contiguous subarray which has the largest sum. Kadane's algorithm. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/maxsubarray/FindMaxSubArray.java

11. Given two sorted (ascending) arrays of integers, find the minimum difference between two integers in that array. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/mindiffsortedarrays/MinimumDifferenceSortedArrays.java

12. Print numbers with frequency. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/numberfrequency/PrintNumbersWithFrequency.java

13. Find Number with Highest frequency in sorted array. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/numberwithhighestfreq/FindNumberWithHighestFreq.java

14. Given an array, write a program to generate a random permutation of array elements. Also asked as “shuffle a deck of cards” or “randomize a given array”. Link:

15. Search for a number in rotated sorted array (Ascending or Descending). Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/searchrotatedsortedarray/SearchInRotatedSortedArray.java

16. Find first missing positive number in an un-sorted array. Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/findfirstmissingpositivenumber/FindFirstMissingPositive.java

17. Re-arrange zeroes, ones and twos in an array. (Dutch-Flag problem)
    Link: https://github.com/techpanja/interviewproblems/blob/master/src/arrays/dutchflagproblem/RearrangeZeroesOnesTwos.java

Collections

1. Find cartesian of lists. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/cartesianproblem/CartesianOfLists.java

2. Find the common elements accross sorted sets/lists. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/commonelementsortedsets/FindCommonElementsInSortedSetsOrLists.java

3. Implement custom linked list. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/customlinkedlist/LinkedListImpl.java

4. Check if a linked list has loops. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/customlinkedlist/LinkedListImpl.java

5. Find nth element from end of the linked list. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/findNTHlastelement/FindNthLastElement.java

6. Find the loop starting point in a LinkedList if it contains loop. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/customlinkedlist/LinkedListImpl.java

7. Flatten a nested list. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/nestedliststring/NestedList.java

8. Given a nested list of integers, returns the sum of all integers in the list weighted by their depth. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/nestedlistsum/NestedListSum.java

9. Remove duplicate links from LinkedList. Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/removeduplicatesfromlinkedlist/RemoveDuplicatesFromLinkedList.java

10. Reverse a linked list. (In-place and using stack.) Link: https://github.com/techpanja/interviewproblems/blob/master/src/collections/customlinkedlist/LinkedListImpl.java

Iterator

1. Implement custom iterator. Link: https://github.com/techpanja/interviewproblems/blob/master/src/customiterator/AnimalIterator.java

Graphs

1. Breadth First Search Link: https://github.com/techpanja/interviewproblems/blob/master/src/graphs/breadthfirstsearch/BFS.java

2. Depth First Search Link: https://github.com/techpanja/interviewproblems/blob/master/src/graphs/depthfirstsearch/DFS.java

3. File Dependency Resolution Link: https://github.com/techpanja/interviewproblems/blob/master/src/graphs/graph/AbstractGraph.java

Heaps

1. Max Heaps Link: https://github.com/techpanja/interviewproblems/blob/master/src/heaps/heap/MaxHeap.java

2. Min Heaps Link: https://github.com/techpanja/interviewproblems/blob/master/src/heaps/heap/MinHeap.java

Maps

1. Custom HashMap implementation. Link: https://github.com/techpanja/interviewproblems/blob/master/src/maps/customhashmap/CustomHashMapImpl.java

2. Least Recently Used (LRU) cache implementation. Link: https://github.com/techpanja/interviewproblems/blob/master/src/maps/lrucache/LRUCache.java

3. Map that should be sorted on the basis of values and not keys. (Use of treemap and comparator.) Link:

Number-Problems

1. Concatenate two numbers. for e.g. 123, 0456 = 1230456 Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/concatenatenumbers/ConcatenateNumbers.java

2. Convert string to number. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/convertstringtonumber/ConvertStringToNum.java

3. Find exponential of a number in fastest time. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/exponentialnumber/ExponentialOfNumber.java

4. Find factorial of a number. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/factorial/Factorial.java

5. Find no. of trailing zeroes in a factorial of number. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/factorial/FactorialNoOfTrailingZeroes.java

6. Find missing number in stream of numbers. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/findmissingnumber/FindMissingNumber.java

7. Check if a number is odd or even without using / % * + - operators. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/oddoreven/OddOrEven.java

8. Print prime factors of a number. Link:

9. Given a number N, find the smallest number K such that product of digits of K is equal to N. For e.g. N = 100 then K = 455 Link:

10. Swap Numbers. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/swapnumbers/SwapNumbers.java

11. Add binary numbers. Link: https://github.com/techpanja/interviewproblems/blob/master/src/numberproblems/addbinarynumbers/AddBinaryNumbers.java

Objects

1. Cloning example (Linked List). Link: https://github.com/techpanja/interviewproblems/blob/master/src/objects/cloning/linkedlistclone/LinkedListCloning.java

2. Implement an Immutable class. Link: https://github.com/techpanja/interviewproblems/blob/master/src/objects/immutableclass/ImmutableClass.java

3. Pass by value example. Link: https://github.com/techpanja/interviewproblems/blob/master/src/objects/passbyvalue/PassByValue.java

4. Implement a singleton class. (Double-check Locking and Static) Link: https://github.com/techpanja/interviewproblems/tree/master/src/objects/singleton

Sorting

1. Bubble Sort. Link: https://github.com/techpanja/interviewproblems/blob/master/src/sorting/algorithms/BubbleSort.java

2. Insertion Sort. Link: https://github.com/techpanja/interviewproblems/blob/master/src/sorting/algorithms/InsertionSort.java

3. Merge Sort. Link: https://github.com/techpanja/interviewproblems/blob/master/src/sorting/algorithms/MergeSort.java

4. Quick Sort. Link: https://github.com/techpanja/interviewproblems/blob/master/src/sorting/algorithms/QuickSort.java

5. Selection Sort. Link: https://github.com/techpanja/interviewproblems/blob/master/src/sorting/algorithms/SelectionSort.java

6. Shell Sort. Link: https://github.com/techpanja/interviewproblems/blob/master/src/sorting/algorithms/ShellSort.java

Stack/Queues

1. Custom Stack with push(), pop() and getMin(). Link:

2. Check if opening parenthesis pattern matches closing parenthesis pattern. Link: https://github.com/techpanja/interviewproblems/blob/master/src/stackqueues/parenthesismatching/ParenthesisMatching.java

3. Implement a queue using stack. Link: https://github.com/techpanja/interviewproblems/blob/master/src/stackqueues/queueusingstack/QueueUsingStack.java

4. Sort a stack using only one additional stack and no other data structure. Link: https://github.com/techpanja/interviewproblems/blob/master/src/stackqueues/stacksorting/StackSorting.java

Strings

1. Check string palindrome. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/checkpalindrome/CheckPalindrome.java

2. Find minimum distance between two words (order preserved. Followup: Unpreserved order.) in a big string. (Kadane's Algo) Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/distancebetweenwords/DistanceBetweenWords.java

3. Find common prefix for a given list of strings. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/findcommonprefix/CommonPrefix.java

4. Find duplicate strings in list of strings. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/findduplicates/FindDuplicates.java

5. Find latest version problem. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/findlatestversion/FindLatestVersion.java

6. Find Longest Common Subsequence. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/findlongestcommonsubsequence/LCS.java

7. Find Longest Palindrome in a string. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/findlongestpalindrome/FindLongestPalindrome.java

8. Print permutations of all characters in a string. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/findpermutations/FindPermutations.java

9. Find total number of palindromes in a String. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/findtotalpalindromes/FindTotalNoOfPalindromes.java

10. Find first non-repeated character. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/firstnonrepeatedchar/FirstNonRepeatedChar.java

11. Given two (dictionary) words as Strings, determine if they are isomorphic. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/isomorphicstrings/Isomorphic.java

12. Given s string, find max size of a sub-string, in which no duplicate chars present. (Kadane's Algo) Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/longestsubstringnorepeatedchar/LongestSubstringUnrepeatedChar.java

13. Find min substring that contains all the char of target string. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/minimumsubstringcontains/MinimumSubstring.java

14. Print diamonds on basis of input size. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/printdiamonds/PrintDiamonds.java

15. Identify all the 'n' (n will be input) letter-long sequences that occur more than once in any given input string. OR Find repeating sequence of specified length in given DNA chromosome sequence. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/repeatingstringsofspecifiedlength/RepeatingStringOfSpecificLength.java

16. Reverse a string. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/reversestring/ReverseString.java

17. Find all dictionary words in a given string. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/segmentstringfindalldictwords/StringSegmentation.java

18. Return true if stringA is subsequence of stringB. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/stringsubsequencecheck/CheckStringSubsequence.java

19. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/substringcheckforrotatedstring/RotatedStringSubStringCheck.java

20. Check if a string has all unique characters. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/uniquecharscheck/CheckUniqueCharacters.java

21. Count word occurrence in a large text file. Link: https://github.com/techpanja/interviewproblems/blob/master/src/strings/wordcountinlargefile/WordOccurencesInLargeFile.java

Threads

1. Implement blocking queue. Link: https://github.com/techpanja/interviewproblems/blob/master/src/threads/blockingqueue/BlockingQueue.java

2. Simulate a deadlock. Link: https://github.com/techpanja/interviewproblems/blob/master/src/threads/simulatedeadlock/DeadLockOreilly.java

Trees

1. Check Balanced Tree. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/checkbalancedtree/CheckBalancedTree.java

2. Check if a tree is Subtree of parent tree. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/checksubtree/CheckSubtree.java

3. Find common ancestor of two nodes in a binary tree (not necessarily BST). Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/commonancestorbinarytree/CommonAncestorBinaryTree.java

4. Find diameter Of Tree. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/diameteroftree/DiameterOfTree.java

5. Find All Paths Equal To Sum. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/findallpathsequaltosum/FindAllPathsEqualToSum.java

6. Find Sum Of All Nodes Except Leaf. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/findsumofallnodesexceptleaf/FindSumOfAllNodesExceptLeaf.java

7. Check is a given tree is binary search tree. (recursive and non recursive) Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/isbst/CheckIfTreeIsBst.java

8. Find least common ancestor (LCA) of a binary search tree given two nodes. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/leastcommonancestorbst/FindLeastCommonAncestorBST.java

9. Left View of a Tree. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/leftviewofatree/LeftViewOfATree.java

10. Mirror Given Tree. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/mirrorgiventree/MirrorGivenTree.java

11. Check if a tree is Mirror of another Tree. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/mirrortree/MirrorTree.java

12. Print Nary Tree With Levels. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/printnarytreewithlevels/PrintNaryTreeWithLevels.java

13. Given a sorted array, create a balanced tree. Link: https://github.com/techpanja/interviewproblems/blob/master/src/trees/sortedarraytobalancedtree/SortedArrayToBalancedTree.java

*** NOTE: Some problems might be in-complete. I have added TODO for such problems. ***