This article focuses on a headache in the interview: algorithm

With the development of technology into the deep water area, including front-end programmers can not avoid the algorithm, today mainly combined with some of my own experience in studying algorithms, and we discuss how to improve their technical level through algorithm practice, easier to deal with the interview and daily work problems.

Algorithms and data structures

Before learning algorithms, you need to review the knowledge of data structures, such as: heap, stack, array, string, tree, linked list, graph. To master the basic characteristics and operations of these data structures, specific algorithms are often based on some combination of these structures

At the heart of rapidly improving algorithm power is to learn: classification

Algorithm problems are ever-changing, the core of the idea is enumerable, eliminate interference factors, master the core is you need to train. Here’s a look at some common algorithm ideas and how to learn them quickly:

  • The sliding window
  • Dynamic programming
  • back
  • recursive
  • Greedy algorithm

The sliding window

Sliding Windows use double Pointers to solve the problem, so it is generally called double pointer algorithm, because two Pointers form a window, generally used to solve array, string, linked list problems.

The core of sliding window is how to move the left or right or fast or slow two Pointers to get results.

The sum of three number

Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.

To solve the sum of two numbers, we do this by moving the single pointer and recording the values read in the map table. When it comes to the sum of three numbers, the single pointer is out of its depth.

First we sort the array, and the time of quicksort is O(nlogn).

If nums[I] > 0, the array will be skipped. If nums[I] > 0, the array will be incremented and the sum will always be greater than 0. Otherwise, perform window sliding, forming three points [I, I +1, n-1] first, so keep I fixed and keep the last two numbers, as long as their sum is greater than 0, move the third point to the left (the number will become smaller), otherwise move the second point to the right (the number will become larger), where the second and third numbers are sliding Windows, When the two Pointers meet, the round slide ends

var threeSum = function(nums) { let res = []; if(! nums || nums.length < 3) return res; nums.sort((a, b) => a - b); for(let i = 0, length = nums.length; i < length - 2; i++){ let cur = nums[i]; if(cur > 0) break; if(i > 0 && cur === nums[i - 1]) continue; let left = i+1; let right = length - 1; while(left < right){ let sum = cur + nums[left] + nums[right]; if(sum === 0){ res.push([cur,nums[left],nums[right]]); while(nums[left] === nums[left + 1]) left++; while(nums[right] === nums[right - 1]) right--; left++; right--; } if(sum > 0){ right--; } if(sum < 0){ left++; } } } return res; };Copy the code
Circular linked list

Given a linked list, determine whether there are rings in the list. Requirements: Space complexity O(1)

To tell the truth, when I first saw this problem, if I could think of a fast or slow pointer solution, it was absolutely very smart, because I had to have the ability to transfer knowledge. Imagine the school is holding a sports meeting, I believe that every time there is a slowest student, slow to be chased by the fastest students.

The idea is that the fast and slow Pointers run separately. As long as they meet, they are judged to be circular linked lists. Otherwise, they are not circular linked lists

var hasCycle = function(head) {
    let fast = head;
    let slow = head;

    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;

        if(fast === slow){
            return true;
        }
    }

    return false;
};
Copy the code

One thing to think about here is how to specify the speed of the fast and slow hands. If you look at the problem directly, you know that the slow hands take one step and the fast hands take two steps, but why not? The fast hands take three steps.

This is similar to quicksort using dichotomy rather than thirds, because dichotomy cuts the array to the smallest granularity with the smallest “depth”. So similarly, in the fast and slow hand, the slow hand might as well be half as fast as the fast hand in order to catch up with it as quickly as possible

But is going half as slow the fastest way to meet? Not necessarily. For example, if the linked list is a perfect circle and there are six nodes [1,6], then the slow pointer takes one step at a time and the fast pointer takes two steps at a time, then there are six steps in total [2,3], [3,5], [4,1], [5,3], [6,5], [1,1]. But what if the fast pointer takes three steps at a time? There are three steps: [2,4] [3,1] [4,4]. So general speed is not necessarily optimal? No, the cost of node access is also taken into account when the computer addresses the linked list. Although the latter looks faster, it actually accesses next more times and is not as fast for the computer as the first one. So it’s not exactly that the fast Pointers are twice as fast as the slow Pointers, but that the slow Pointers take one step at a time, and the fast Pointers take two steps at a time, because when they meet, the total number of moves is the least.

There are a lot of problems about the use of sliding Windows, especially what subproblem/substructure of the string, to master a certain kind of problem solving algorithm and ideas, we must carry out targeted training, can not be a shot in the east and a shot in the west, then basically forget all

Dynamic programming

Most of the problems solved by dynamic programming belong to intermediate problems, dynamic planning flexible, very exercise mental and thinking

The difference between dynamic programming and violent solution is that dynamic programming needs to work out the optimal solution of the next step according to the solution of the previous problem. Therefore, the solvable problem of dynamic programming should simultaneously satisfy the following three characteristics:

  1. There is an optimal substructure
  2. There is a duplication subproblem
  3. There was no aftereffect

There is an optimal substructure

The global optimal solution can be derived from the optimal solution of subproblems

What is a subproblem? For example, in the path-finding algorithm, the first few steps are the subproblem relative to the whole process. It is necessary to ensure that the shortest path to complete the whole process can be deduced by the first few steps before dynamic programming can be used. Finding optimal substructure is the process of establishing dynamic transfer equation, which is the core of dynamic programming.

There is a duplication subproblem

The same subproblem is duplicated in different scenarios

This is the key difference between dynamic programming and violent solution method. Dynamic programming has high performance because it does not repeat the calculation of the repeating subproblem. The algorithm is generally solved by caching the calculation results or bottom-up iteration, but the core is that the scene should have the repeating subproblem.

Typical example is the Fibonacci sequence, for f (3) and f (4), to calculate f (1) and f (2), because f (3) = f (2) + f (1), and f (4) = f (3) + f (2) = f (2) + f (1) + f (2).

There was no aftereffect

Previous choices do not affect the rules of the game

The problems that we solve with dynamic programming have no aftereffect, so maybe you don’t understand this very well, but in turn, what scenarios have aftereffect?

It is your current choices that affect the subsequent results. Career planning in life has after-effects. After the college entrance examination, your choice of studying again or working will have a huge impact on your future life results. What are the choices that don’t affect the result? For example, in the change question, whether I choose 1 dollar or 5 dollars at the moment doesn’t affect the total amount I have to pay at the end. In the backpack problem, the number of items I choose does not affect the overall quality of the backpack

The most difficult point of dynamic programming is how to construct the state transition equation to obtain the recursive relationship in the complex relationship, and then use the actual example to experience

Maximum suborder sum

Given an integer array nums, find a contiguous subarray with the maximum sum (the subarray contains at least one element) and return the maximum sum

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: The maximum sum of continuous subarrays [4,-1,2,1] is 6.

Now we construct the state transition equation, and we use dp(I) to represent the maximum sum at the end of the i-th string, so dp(i-1) is the maximum sum at the end of the i-1st string, and dp(i-1) has already been calculated, so it’s clear how to derive dp(I).

Since the array is continuous, dp(I) is either dp(i-1) + nums[I] or nums[I], depending on whether the preceding dp(i-1) is positive, since the end of I must contain nums[I]. So nums[I], whether positive or negative, must be carried. So it’s easy to say, dp of I minus one, if it’s positive then it’s connected, otherwise it’s not connected. The state transition equation is:

  • Dp (I) = dp(i-1) + nums[I] if dp(i-1) > 0.
  • Dp (I) = nums[I] if dp(i-1) <= 0.
var maxSubArray = function(nums) { let n = nums.length; let dp = new Array(n); dp[0] = nums[0]; let max = nums[0]; for (let i = 1; i < n; i++) { dp[i] = Math.max(dp[i- 1] + nums[i], nums[i]); max = Math.max(max, dp[i]); } return max; }; Sum = sum; sum = sum; sum = sum; sum = sum; sum = sum; Var maxSubArray = function(nums) {let sum = 0; let res = []; let max = nums[0]; for(let i = 0; i < nums.length; i++){ if(sum < 0){ sum = nums[i]; }else{ sum += nums[i]; } max = Math.max(max, sum); } return max; };Copy the code
Al shabaab

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.

Input:,2,3,1 [1]

Output: 4

Explanation: Steal House # 1 (amount = 1), then steal House # 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4.

This is a non-string dynamic programming problem. Since adjacent houses cannot be robbed at the same time, dp(I) can be robbed either in order to rob i-1 but not the i-th, or in order to rob i-2 and i-th, and take the maximum return of these two final states. Dp (I) = Max (DP (i-1), DP (i-2) + coins[I])

var rob = function(nums) { const len = nums.length; if(len === 0) return 0; const dp = new Array(len + 1); dp[0] = 0; dp[1] = nums[0]; for(let i = 2; i <= len; i++) { dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]); } return dp[len]; }; Var rob = function(nums) {if(nums.length === 1) return nums[0]; var rob = function(nums) {if(nums.length === 1) return nums[0]; let prev = Math.max(nums[0], nums[1]); let next = nums[0]; let i = 1; let length = nums.length; while(i++ < length - 1){ let temp = Math.max(prev, next + nums[i]); next = prev; prev = temp; } return prev; };Copy the code

The core of dynamic programming is to define what the states are, what dp(I) is, and then pull out the state transition equations from the complex relationships. Backpack problem as the most classic dynamic programming case, it is worth studying

Limited to the space is limited, first introduced the dynamic programming algorithm and the sliding window, next to talk back, recursion, how to solve the greedy algorithm, algorithm with special training practice, do not follow one’s inclinations, master the common thinking methods, meet specific problems, and then analyze disassembly to find a suitable solution, it is also a fun of the algorithm.

About brush problem (LeetCode)

When it comes to algorithms, the first thing that comes to mind is LeetCode, which most of you have practiced with at least a little bit. As for LeetCode’s positioning, many people have mixed opinions, some even compared it to the Sunflower Book, forcing everyone in the world to go to their palace.

A large number of algorithm cases provided by Leetcode are indeed very suitable for algorithm learning. Since you want to get the offer from the desired big factory, you can only prove yourself according to the requirements of others. As for whether this assessment method is reasonable, it is up to the industry to think, we just need to make ourselves stand out under any rules.