Top 20 Sorting and Searching Algorithms Questions for Interviews A Collection of common coding problems from Interviews based on basic algorithms like searching, sorting, and string algorithms Hello All, If you are preparing for or looking for a new job then you know that it’s not an easy process. You got to be lucky to get the call and make to the first round of interview, not just when you are a beginner but at any stage of your career. Programming job interviews But, Yes, it is the most difficult at the beginner level when you are searching for your first job. That’s why you can’t just take your chance lightly. You got to be prepared to grab that chance and for that, you must know that is expected from you on the interview. What is asked, what topics should you prepare, etc? I have blogged a lot about what you can find helpful articles in this blog but to recap let me tell you that apart from , , and Programming language specific questions like , , or , most of the programming job interviews also ask algorithm based questions. data structure questions System Design Questions Java C++ Scala These are based upon common searching and sorting algorithms like , , , etc. String algorithms binary search graph algorithms It’s important that you practice these Algorithms based questions because even though they seem obvious and easy, sometimes they become tricky to solve in the actual interview, especially if you have never coded them by yourself. Practising these problems before interview not only makes you familiar with them but also gives you more confidence in explaining the solution to the interviewer, which plays a very important role in your selection. It also makes you ready for any twisted questions and alternative problems like Interviewers often like to ask you to solve a particular coding problem using or . Recursion Iteration Sometime, if you use a data structure like the one I have used in , they will ask you to solve that problem without using the Set data structure. That’s just some common example and that’s why practice matters a lot. finding duplicate characters on String Btw, if you are a complete beginner in the world of Data Structure and Algorithms, then I suggest you to first go through a comprehensive Algorithm course like on Udemy which will not only teach you basic data structure and algorithms but also how to use them on the real world and how to solve coding problems using them. Data Structures and Algorithms: Deep Dive Using Java Data Structures and Algorithms: Deep Dive Using Java On the other hand, if you like to read books or prefer books over online courses then you must read a comprehensive book like by Thomas H. Cormen to get an understanding of common Computer Science Algorithms like Searching, Sorting, Cryptography, and some common ones like Fourier Transform. Introduction to Algorithms Graph Algorithms Introduction to Algorithms, 3rd Edition (The MIT Press) 20+ Searching and Sorting Algorithms Questions from Coding Interviews Anyway, here is some of the frequently asked Searching and Sorting Algorithms questions from Interviews. I have linked the solution but you should try to solve the problem before looking at the solution. The purpose of this article is that you should know how to solve these problems on your own, but, yes, if you got stuck and want to compare your solution, you can see the solution. It’s easy, binary search is a divide and conquers algorithm, where the problem is divided into sub-problem and those are solved. It’s a search algorithm which means it is used to find things like a number in an integer array or an item in a catalog. 1. Can you implement a Binary Search Algorithm? ( solution ) The easiest way to implement a is by using Recursion, which is what the solution link contains but you should try it yourself before seeing the solution. binary search algorithm One of the worth noting this is that the input must be sorted, I mean you can only implement binary search in a . sorted array It is even easier than binary search, all you need to do is go through all elements in the array using a or recursive method and compare each element with the one you want to search. when an element matches you either return index or true/false depending upon your requirement. 2. Write a program to implement Linear search Algorithm? ( solution ) for loop For example, if you are writing a you can return true or false to indicate whether an element is present in the array or not. Since you need to scan the whole array to find the element, the time complexity of this algorithm is O(n). contains() method Btw, if you have trouble calculating and understanding time and space complexity of algorithms then you should see a course like to understand them better before going for an interview. Data Structures & Algorithms — Interview You might know that you can replace a recursive algorithm to an iterative one by using a loop and sometimes using a data structure. For binary search also you can do this, just divide the array and compare the middle element until you find the target element or there is no more element into an array. 3. Can you implement a Binary search Algorithm without recursion? ( solution ) Stack If the target element is greater than middle than you got to move towards the right, or otherwise towards left. Btw, if you have trouble understanding recursive algorithm or converting a recursive one to iterative one then I suggest you go through a good online course like and in Pluralsight to learn fundamentals better. Algorithms and Data Structures — Part 1 Part 2 These courses will also teach you about how to calculate time and space complexity which is very important from both Coding Interview perspective as well as improving the performance of an Algorithm. Isn’t this was the first sorting algorithm you learn? Well, I did and that’s why I remember that is about comparing each number with every other number in an array so that after each pass the bubble up to the top. 5. Implement the Bubble sort Algorithm? ( solution ) bubble sort largest or smallest element I mean the number has found it’s placed in the sorting order. This is one of the fundamental sorting algorithms and most of us started learning about sorting using this algorithm. The time complexity of this is O(n ^2) which makes it unusable for a large set of numbers but it does well for a small set of numbers. In level order search you first visit sibling nodes than going down into the next level. You can use a to implement level order search in a binary tree.If you want to learn more, you can check any of these on 4. Write Code to implement Level Order Search in a Binary Tree? (solution) Queue free data structure and algorithms courses freeCodeCamp And, if you are really serious about doing well, you can also check this list of courses to crack your programming job interviews 10 Data Structure, Algorithms, and SQL Courses to Crack Any Programming Job Interview This one was a tricky concept which I didn’t know until long ago. I haven’t come across any practical use case of this one yet but just knowing the concept is Ok from the interview perspective. 6. Difference between a stable and unstable sorting algorithm? ( answer ) In a stable sorting algorithm, the order of the same element remains the same even after sorting but during the unstable sorting algorithm, this changes. A good example is a and where former is unstable while later is a stable algorithm. quicksort mergesort It’s another popular searching algorithm which is mainly used in tree and graphs. This algorithm first visits nodes in depth before searching in the same level, that’s why the name Depth-first search algorithm. 7. What is Depth First Search Algorithm for a binary tree? (solution) It’s tricky to implement but you can use a Stack to implement DFS or Depth-first search algorithm. If you need more information on this topic, I suggest you check the book by Aditya Bhargava, his explanation is probably the best explanation of this topic Grokking Algorithms Obviously without recursion:-). If you remember, I have told you before that you can use a Stack to convert a into an iterative one and that’s what you can do as well to implement Quicksort algorithm without recursion. You can further see the if you need more help with respect to implementation. 8. How is an iterative quicksort algorithm implemented? ( solution ) recursive algorithm solution Just like we have done with other O(n) sorting algorithms like Radix sort and Bucket sort. 9. How do you implement a counting sort algorithm? ( solution ) If you don’t know is another integer sorting algorithm for sorting a collection of objects according to keys that are small integers. Counting sort It has O(n) time complexity which makes it faster than likes of and for a particular set of input. See the solution for more details. Quicksort Mergesort Another tricky question which is easy if you know the trick :-) Well you can swap two numbers without using a temporary or third variable if you can store the sum of numbers in one number and then minus the sum with other number something like 10. How do you swap two numbers without using the third variable? ( solution ) a = 3;b = 5; a = a + b; //8b = a — b; // 3a = a — b; //5 now you have a = 5 and b = 3, so numbers are swapped without using a third or temp variable. This is another integer sorting algorithm with O(n) time complexity. As per Wikipedia, Radix sort is a that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. 11. How is a radix sort algorithm implemented? ( solution ) non-comparative sorting algorithm You can further see and by Robert Sedgewick on to learn more about these O(n) or liner sorting algorithms. The course is free for learning and exploring but you need to pay if you also want a certification. Algorithms, Part I Part II Coursera Have you ever arranged the deck of cards, or maybe shirts in your cupboard? What is common between those two things? Well, you put the next card or shirt into their proper position, or, should I say you insert the next element in its proper position. That’s the for you. 12. How do you implement an insertion sort algorithm? ( solution ) insertion sort This is a tricky Algorithm question but if you have to listen to your teacher in your 2D Maths class then you can solve this problem. There is another trick, check for all the conditions when rectangle will not overlap and if any condition is false it means both rectangles are overlapping with each other. For example, if the upper side of one rectangle is below the lower side of other rectangles then they won’t overlap as they are vertically aligned. 13. Write Algorithm to check if two rectangles overlap with each other? ( solution ) Similar to Quicksort, merge sort is also a divide and conquer algorithm which means you keep divides the problem until you can sort the smallest of them. 14. How is a merge sort algorithm implemented? ( solution ) For example to you divide the array into smaller parts until you know how to sort them like an array with one or zero elements is already sorted. Once you sort small arrays you merge them to get the final result. sort an array of numbers The only is that mergesort is while Quicksort is . This means equal elements retain their spot before and after sorting. difference between Quicksort and Mergesort stable not-stable Another worth noting difference is that even though both have O(NLogN) average time, it’s better to use quicksort than mergesort because Quicksort takes less time for the same number of input, the constant factor is less in Quicksort than merge sort. The Bucket sort is another awesome algorithm which can sort an array without even comparing elements. 15. How do you implement a bucket sort algorithm? ( solution ) It’s known as and can give O(n) performance for the selected input. non-comparison sorting algorithm If you don’t know about the non-comparison based sorting Algorithm, please see book. Introduction to Algorithms An anagram is something where length and character matches but not the order like Army and Mary, both have the same number of characters. 16. Write Algorithms to Check if Two String are Anagram ( Solution ) One trick is to solve this problem is to and check if they are the same or not. sort the character array This one is a very easy sorting algorithm, but only if you have practiced, if not then you may lose your way. Remember, is a which means you keep dividing array, also known as . Then you solve the problem at the smallest level, also known as a base case like when your array contains just one or zero elements. 17. Implement the QuickSort Algorithm in your Favorite Programing language? ( solution ) Quicksort divide and conquer algorithm partitioning As the name suggests, in comparison based sorting algorithms you must compare elements to sort like quicksort, but in non-comparison based sorting algorithm like , you can sort elements without comparing it. Surprised? 19, Difference between Comparison and Non-Comparison Sorting Algorithms? ( answer ) Counting sort Well yes, then I suggest you check out this course to learn more about O(n) sorting algorithms like Radix Sort, Counting Sort, and Bucket Sort. You can further see if you want to learn more about these O(n) sorting algorithms. Data Structures and Algorithms: Deep Dive Data Structures and Algorithms: Deep Dive Using Java There is a simple trick to solve this problem, You can do that by using indexOf or substring method. If the concatenated String contains rotation then given String is a rotation of former. 19. How to check if two String is rotations of each other? ( solution ) just concatenate the String with itself and check if the rotation exists there. This is one of the tough algorithms to implement especially if you don’t remember it :-) Sometime interviewer gives you the explanation but other times you need to remember it. 20. Implement Sieve of Eratosthenes Algorithms for Prime Number? ( solution ) I hope these 20 questions should be enough to get you going on your preparation for Algorithms for Coding interviews. If you need more such coding questions you can take help from books like , by which contains 189+ Programming questions and solution. A good book to prepare for programming job interviews in a short time. Cracking The Code Interview Gayle Laakmann McDowell By the way, the more questions you solve in practice, the better your preparation will be. So, if you think this list of questions is not enough and you need more, then check out these additional for and these and for more thorough preparation. 50 programming questions telephone interviews books courses Now You’re Ready for the Coding Interview These are some of the most common questions outside of data structure and algorithms that help you to do really well in your interview. I have also shared a lot of these questions on my , so if you are really interested, you can always go there and search for them. blog These common coding, are the ones you need to know to successfully interview with any company, big or small, for any level of programming job. data structure, and algorithms questions If you are looking for a programming or software development job, you can start your preparation with this . list of coding questions This list provides good topics to prepare and also helps assess your preparation to find out your areas of strength and weakness. Good knowledge of data structure and algorithms is important for success in coding interviews and that’s where you should focus most of your attention. Resources to Prepare for Interviews , by Cracking The Code Interview Gayle Laakmann McDowell Data Structures and Algorithms: Deep Dive Using Java From 0 to 1: Data Structures and Algorithms in Java Data Structure and Algorithms Analysis — Job Interview My other articles you may like: 10 Books to Prepare Technical Programming/Coding Job Interviews 10 Algorithm Books Every Programmer Should Read Top 5 Data Structure and Algorithm Books for Java Developers My favorite free courses to learn Algorithms in depth 10 Free Data Structure Courses for Java Developers A list of courses to Crack Programming Job Interviews 10 Data Structure, Algorithms, and SQL Courses to Crack Coding Interview Closing Notes Thanks, You made it to the end of the article … Good luck with your programming interview! It’s certainly not going to be easy, but by following this searching and sorting algorithm questions, you are one step closer than others. If you like this article, then please share with your friends and colleagues, and don’t forget to follow on Twitter and and here on as well! javarevisited javinpaul javinpaul Medium P.S. — If you need some FREE resources, you can check out this list of to start your preparation. free data structure and algorithm courses
