来自编码面试的20多种基本算法问题

disclosure: This post includes affiliate links; I may receive compensation if you purchase products or services from the different links provided in this article.

Hello All, If you are preparing for Programming job interviews 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.

但是，是的，这对于初学者来说是最困难的。

这就是为什么您不能只是轻率抓住机会。您必须准备抓住这个机会，为此，您必须知道在面试中您期望得到的机会。问什么，应该准备哪些主题，等等？

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 data structure questions, System Design Questions, and Programming language specific questions like Java, C++, or Scala, most of the programming job interviews also ask algorithm based questions.

These are based upon common searching and sorting algorithms like String algorithms, binary search, graph algorithms, etc.

练习这些基于算法的问题很重要，因为即使它们看起来很明显且容易，但有时在实际面试中很难解决，特别是如果您从未亲自编码过。

在面试之前练习这些问题，不仅使您熟悉它们，而且使您更有信心向面试官解释解决方案，这在选择中起着非常重要的作用。

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 Recursion or 一世teration.

Sometime, if you use a data structure like the one I have used in finding duplicate characters on 小号tring, 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.

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 Data Structures and Algorithms: Deep Dive Using Java 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.

On the other hand, if you like to read books or prefer books over online courses then you must read a comprehensive book like Introduction to Algorithms by Thomas H. Cormen to get an understanding of common Computer Science Algorithms like Searching, Sorting, Cryptography, Graph Algorithms and some common ones like Fourier Transform.

Top 20 basic Algorithms interview questions for Programmers

无论如何，这是一些来自访谈的常见搜索和排序算法问题。我已经链接了解决方案，但是在查看解决方案之前，您应该尝试解决问题。

本文的目的是您应该知道如何自行解决这些问题，但是，是的，如果您陷入困境并想比较解决方案，则可以看到解决方案。

1个. Can you implement a Binary Search Algorithm? (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.

The easiest way to implement a binary search algorithm is by using Recursion, which is what the solution link contains but you should try it yourself before seeing the solution.

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.

2. Write a program to implement Linear search Algorithm? (solution)
It is even easier than binary search, all you need to do is go through all elements in the array using a for loop 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.

For example, if you are writing a contains() method 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).

Btw, if you have trouble calculating and understanding time and space complexity of algorithms then you should see a course like Data Structures & Algorithms --- Interview to understand them better before going for an interview.

3. Can you implement a Binary search Algorithm without recursion? (solution)
You might know that you can replace a recursive algorithm to an iterative one by using a loop and sometimes using a Stack 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.

如果目标元素大于中间元素，则必须向右移动，否则向左移动。

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 Algorithms and Data Structures --- Part 1 andPart 2 in Pluralsight to learn fundamentals better.

这些课程还将教您如何计算时间和空间复杂度，这从“编码面试”的角度以及提高算法的性能都非常重要。

4. Implement the Bubble sort Algorithm? (solution)
Isn't this was the first sorting algorithm you learn? Well, I did and that's why I remember that bubble sort is about comparing each number with every other number in an array so that after each pass the largest or smallest element bubble up to the top.

我的意思是数字已找到它的排序顺序。这是基本的排序算法之一，我们大多数人开始学习使用此算法进行排序。

这个的时间复杂度是O（n ^ 2）这使得它不能用于大量数字，但对于少量数字却效果很好。

5. Write Code to implement Level Order Search in a Binary Tree? (solution)
In level order search you first visit sibling nodes than going down into the next level. You can use a Queue to implement level order search in a binary tree.If you want to learn more, you can check any of these free data structure and algorithms courses on freeCodeCamp

And, if you are really serious about doing well, you can also check this list of courses to ***** your programming job interviews

6. Difference between a stable and unstable sorting algorithm? (answer)
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.

在稳定的排序算法中，即使在排序后，相同元素的顺序也保持不变，但是在不稳定的排序算法中，这会发生变化。

A good example is a quicksort and mergesort where former is unstable while later is a stable algorithm.

7.什么是二叉树的深度优先搜索算法？（解）这是另一种流行的搜索算法，主要用于树和图形。该算法首先在相同级别搜索之前先深入访问节点，这就是为什么使用深度优先搜索算法的原因。

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 Grokking Algorithms book by Aditya Bhargava, his explanation is probably the best explanation of this topic

8. How is an iterative quicksort algorithm implemented? (solution)
Obviously without recursion:-). If you remember, I have told you before that you can use a Stack to convert a recursive algorithm into an iterative one and that's what you can do as well to implement Quicksort algorithm without recursion. You can further see the solution if you need more help with respect to implementation.

9. How do you implement a counting sort algorithm? (solution)
Just like we have done with other O(n) sorting algorithms like Radix sort and Bucket sort.

If you don't know Counting sort is another integer sorting algorithm for sorting a collection of objects according to keys that are small integers.

It has O(n) time complexity which makes it faster than likes of Quicksort and Mergesort for a particular set of input. See the solution for more details.

1个0. How do you swap two numbers without using the third variable? (solution)
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

a = 3; \ b = 5；

a = a + b; // 8 \ b = a --- b; // 3 \ a = a --- b; // 5

现在您有a = 5和b = 3，因此无需使用第三个或temp变量就可以交换数字。

1个1. How is a radix sort algorithm implemented? (solution)
This is another integer sorting algorithm with O(n) time complexity. As per Wikipedia, Radix sort is a non-comparative sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.

You can further see Algorithms, Part I and Part IIby Robert Sedgewick on [Coursera] 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.

1个2. How do you implement an insertion sort algorithm? (solution)
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 insertion sort for you.

1个3. Write Algorithm to check if two rectangles overlap with each other? (solution)
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.

1个4. How is a merge sort algorithm implemented? (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.

For example to sort an array of numbers 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.

The only difference between Quicksort and Mergesort is that mergesort is stable while Quicksort is not-stable. This means equal elements retain their spot before and after sorting.

另一个值得注意的区别是，即使两者都有O（NLogN）平均时间，使用Quicksort比mergesort更好，因为对于相同数量的输入，Quicksort花费的时间更少，Quicksort中的常数因子比merge sort少。

1个5. How do you implement a bucket sort algorithm? (solution)
The Bucket sort is another awesome algorithm which can sort an array without even comparing elements.

It's known as non-comparison sorting algorithm and can give O(n) performance for the selected input.

If you don't know about the non-comparison based sorting Algorithm, please see Introduction to Algorithms book.

1个6. Write Algorithms to Check if Two String are Anagram (Solution)
An anagram is something where length and character matches but not the order like Army and Mary, both have the same number of characters.

One trick is to solve this problem is to sort the character array and check if they are the same or not.

1个7. Implement the QuickSort Algorithm in your Favorite Programing language? (solution)
This one is a very easy sorting algorithm, but only if you have practiced, if not then you may lose your way. Remember, Quicksort is a divide and conquer algorithm which means you keep dividing array, also known as partitioning. 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.

1个9, Difference between Comparison and Non-Comparison Sorting Algorithms? (answer)
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 Counting sort, you can sort elements without comparing it. Surprised?

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 seeData Structures and Algorithms: Deep Dive if you want to learn more about these O(n) sorting algorithms.

1个9. How to check if two String is rotations of each other? (solution)
There is a simple trick to solve this problem, just concatenate the String with itself and check if the rotation exists there. You can do that by using indexOf or substring method. If the concatenated String contains rotation then given String is a rotation of former.*\
*

20. Implement Sieve of Eratosthenes Algorithms for Prime Number? (solution)
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.

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 Cracking The Code Interview, by Gayle Laakmann McDowell which contains 189+ Programming questions and solution. A good book to prepare for programming job interviews in a short time.

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 50 programming questions for telephone interviews and these books and courses for more thorough preparation.

Now You're Ready for the Coding Interview

这些是数据结构和算法之外的一些最常见问题，可帮助您在面试中表现出色。

I have also shared a lot of these questions on my blog, so if you are really interested, you can always go there and search for them.

These common coding, data structure, and algorithms questions are the ones you need to know to successfully interview with any company, big or small, for any level of programming job.

If you are looking for a programming or software development job, you can start your preparation with this list of coding questions.

此列表提供了准备的好主题，还有助于评估您的准备工作，以找出您的长处和短处。

良好的数据结构和算法知识对于成功编写采访面试至关重要，因此您应该集中精力进行大部分工作。

Resources to Prepare for Interviews

Cracking The Code Interview, by [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

Closing Notes

谢谢，您到了本文的结尾。祝您编程采访顺利！这当然不是一件容易的事，但是通过遵循此搜索和排序算法问题，您比其他人迈了一步。

If you like this article, then please share with your friends and colleagues, and don't forget to follow javarevisited on Twitter as well!

来自编码面试的20多种基本算法问题

Top 20 basic Algorithms interview questions for Programmers

Now You're Ready for the Coding Interview

Resources to Prepare for Interviews

Closing Notes

Other Programming articles you may like:

相关推荐