Spring recruitment has begun. Have you already started preparing? In order to help you get a better offer, Lucifer has a spring Tips rush program.

Today our prey is Dingding and Tencent. Take a look at the algorithm of these two difficulty geometry!

​

Video address: www.bilibili.com/video/BV1Qy…

nailing

  1. Comparison version Number (li Deduction No. 165. Comparison Version Number)

The only thing that needs to be paid attention to is completion and comparison (logical completion is ok, and physical completion is not necessary). The time complexity is O(m+n)O(m +n)O(m + N)O(m+ N), where M and n are the lengths of two version numbers respectively

  1. Random string generation (Randomly generate a string of 8 characters with lowercase letters and numbers. The letters and numbers can be repeated, but the generated random string cannot be repeated)

Generate a random character of length 8 and store it in the hash table. After the next generation, determine whether it is already in the hash table. If yes, it has been generated before. Continue to generate. Note that this algorithm can always be rejected, and the code will loop indefinitely.

  1. Log reporting (effect: if no data is reported, the data is reported in batches every 100ms)

Maintains a window that triggers batch upload requests only when there is data in the window, and a window with a length of 100m (possibly greater than) all requests in the window

tencent

  1. String inversion

Double pointer, keep swapping the characters of two Pointers.

  1. The KTH inverse of a linked list

Fast and slow double pointer typical questions.

  1. Design to find the NTH square root of a number

A typical dichotomous problem. No, look at my dichotomous notes. My brush title warehouse or public number search two on the line.

  1. LRU algorithm

A little bit difficult, this problem is very common, difficulty is not small, suggest brush. I wrote down the solution before, so I’ll just throw it at you 146. LRU cache mechanism

I’ve given JS, Go, PHP, Python3. Any dishes for you?

  1. Hand tear, is a car given coordinate position, and the current face direction (NSWE), and then input forward steering situation and forward steps, output car coordinate position and face direction.

It’s not that hard. It’s just a simulation.

  1. List together

Linked lists and arrays are essentially the same, just different operations. So master the basic operation of the linked list on the line. What are the basic operations of linked lists? What should I pay attention to? My linked list topics are summarized for everyone, recommended reading.

  1. Leetcode 1567 The length of the largest array whose product is positive.

Given an array of integers nums, find the length of the largest array whose product is positive. An array of subarrays is an array consisting of zero or more consecutive numbers from the original array. Return the maximum array length whose product is positive.

This problem is to find the maximum length of the array whose continuous product is positive. Here’s an elementary lesson: two numbers with the same sign are multiplied together to be positive, and two numbers with different signs are multiplied together to be negative (leaving 0 out of the equation). So use one-dimensional DP + one layer loop.

Negative [I] = nums[I] = nums[I] = Max (positive)

Nums [I], nums[I], nums[I]

  • nums[i] > 0

p o s i t i v e [ i ] = p o s i t i v e [ i – 1 ] + 1 Positive [I] = positive [I – 1) + 1

n e g a t i v e [ i ] = { n e g a t i v e [ i – 1 ] + 1 n e g a t i v e [ i – 1 ] > 0 0 n e g a t i v e [ i – 1 ] = 0 negative[i]=\left\{ \begin{aligned} negative[i-1] + 1 & & negative[i-1] > 0 \\ 0 & & negative[i-1] = 0 \\ \end{aligned} \right.
  • nums[i] < 0

n e g a t i v e [ i ] = p o s i t i v e [ i – 1 ] + 1 Negative [I] = positive [I – 1) + 1

p o s i t i v e [ i ] = { n e g a t i v e [ i – 1 ] + 1 n e g a t i v e [ i – 1 ] > 0 0 n e g a t i v e [ i – 1 ] = 0 positive[i]=\left\{ \begin{aligned} negative[i-1] + 1 & & negative[i-1] > 0 \\ 0 & & negative[i-1] = 0 \\ \end{aligned} \right.
  • nums[i] == 0

n e g a t i v e [ i ] = p o s i t i v e [ i ] = 0 negative[i]=positive[i] = 0

There are generally two sets of state definition:

  • Using a two-dimensional array, define dp[I][0] and define dp[I][1]
  • Using two one-dimensional arrays, define dp1[I] and dp2[I]

The two ways of thinking are the same, but the actual operation is different. Personally, I prefer the second option. For the stock problem, I like to define a buy and a Sell array. Or swing arrays, I like to define an up and a Down array.

In addition, if the problem does not define continuity, a two-layer loop and a one-dimensional DP (rolling array optimization) are required.

conclusion

I personally think the difficulty of the algorithm questions is medium, they are very routine, there is no difficult to understand the topic or unpopular knowledge.

In addition, I set up a spring recruit group, we can ask the interview questions. Want to enter the group can be in the public number force buckle plus background reply chunzhao get small secretary wechat, through again chunzhao into the group.

Finally, I wish you a lot of offers.