I led a development team in Microsoft and worked as an interviewer for four years. I already know that children nowadays like to brush questions, so they will not be stupid enough to take the original leetcode questions. So it’s best not to memorize by rote, want to encounter the original question to dominate the interview.
Underline: programming interview, only high frequency knowledge points, no so-called high frequency questions.
As we all know, the interview algorithm questions of Microsoft and many other big companies are mainly adapted from Leetcode. Now I share some interview questions and my own and my colleagues’ adaptation ideas as interviewers, hoping to help students who are still struggling to brush the questions. I will go over most of the original leetcode questions, and then attach the rewriting ideas of the real interview questions, and try to speak foolishly. Due to space constraints, HERE I only give a few small chestnuts, more interview questions and rewriting you can pay attention to my column.
I try to keep replying to comments twice a week and decide whether to change the update frequency and increase or decrease the content to be shared depending on the subsequent feedback. I will read every comment and reply. I can also add longswordMAN on wechat and indicate the ID of gold digging. — — — — — — — — — — — — — — — — — — — — nonsense not much said, to start:
Let’s start with problem # 1 in Leetcode:
Given an array of integers and a target value, find two numbers that neutralize the target value in the array.
You can assume that there is only one answer for each input and that the same elements cannot be reused.
Example:
Given nums = [2, 7, 11, 15], target = 9
Because nums[0] + NUMs [1] = 2 + 7 = 9
So return [0, 1]
Simple question, test is the hash table, double cycle of violence will hang. Now all the posts on the Internet like to tell you that question XX of Leetcode is a high-frequency question. In fact, they are all lazy thinking, which belongs to the mistaken thinking of novices. Really high frequency is some specific knowledge points, if according to this “copy the original topic” thinking, the topic do a little change, the probability is to misstep.
Hash table hash table hash table hash table hash table hash table hash table hash table
Interviewer:
- Different rules, you could multiply and divide, you could invent a rule.
Bo:
Given an array of integers and a target value, find two numbers in the array whose product is the target value.
Example:
Given nums = [2, 7, 11, 15], target = 14
Because nums[0] * nums[1] = 2 * 7 = 14
So return [0, 1]
X ‘bla’ Y = X*Y – X -Y Again, I’m just going to change the table lookup rules a little bit, but I’m going to keep the boundary cases in mind.
- Change the data structure and see if the interviewer can take advantage of the rules to further optimize the time complexity.
Of course, ordered arrays can also be changed to other data structures such as binary trees, or some data structures with certain properties. For ordered arrays, if you use binary lookup, you can get down to order logn, and if you can build a hash table, it’s order n, so if you can use binary lookup, don’t worry about hashing.
Bo:
Given a “turned array”, a concatenation of two ordered arrays that fall in opposite order. [1,2,3] + [6, 5,4] –> [1,2,3, 6, 5,4]. Requires the given target to be found in the turn array.
So if we hash this, it’s O(n), but it’s not optimal, we don’t use arrays. We find the inflection point using dichotomy, and then we go to dichotomy in two ordered arrays, optimizing the complexity to order logn.
- It becomes the sum of the many, like 3 sum. This is easy to rewrite
Bo:
Given an ordered array of integers and a target value, find the array and the three numbers that are the target values.
Example:
Given nums = [2, 7, 11, 15], target = 20
Because nums[0] + NUMs [1] + NUMs [2] = 2 + 7 + 11 = 20
So return [0, 1, 2]
Similarly, I’m going to look it up twice, but I’m going to exclude the first term, like 2+2+2, where I’m going to use the same term multiple times. Of course, this is all easy, if you combine three numbers with the first change, you’ll still have two times to look up the table, but don’t get confused by the complexity of the operation, and then pay attention to the boundary conditions.
After reading these a few I out of the adaptation of the interview real question, do not know whether to see the officers of the original brush question way has changed? In short, there is no such thing as high frequency questions, but only high frequency knowledge points. When we brush questions, we should also think about the knowledge points behind, and even set questions for ourselves according to the ideas I shared above, so as to maximize the efficiency of brushing questions.
The three variants just said are essentially the investigation of the [hash table] knowledge point, if the topic itself rote memorization, and ignore the knowledge itself, it is very inefficient. So the meaning of the data structure of the hash table is that the time complexity of O (1) can be used to find whether an element exists in the set, rather than O (n) traversing the search. Next time, I will update some new real questions, focusing on some other hash table interview changes, which will be combined with the original question of Leetcode.
— — — — — — — — — — — — — — — — — — — —
This is going to be a series, and I’m going to post a series of rewrites. We set up a wechat group discussion group, and later posts will be published in the group first. My wechat: longswordMAN, the first scan in moments.
Many friends add me to wechat. If my wechat friends are full, if you need to join the discussion group, please add the doppelganger sxxZS3998 and note the id of gold nuggets.