Skip to content

Latest commit

 

History

History
327 lines (227 loc) · 16.3 KB

README.md

File metadata and controls

327 lines (227 loc) · 16.3 KB
Raw

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.

I have a cloned repo https://github.com/techpanja/interviewproblemspublic which is open for contribution. Feel free to email me if you want to be a contributor.

A COMPILATION OF COMMON INTERVIEW QUESTIONS AND SOLUTIONS.

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:

  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

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

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:

  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. ***