Since LUCifer is a small front-end, I am also preparing to write a front-end how to Handle algorithm interviews column, so I have been reading a lot of interview questions from various companies. Bytedance algorithm is said to be difficult, SO I will start with TA. This time we will take a set of front school admissions in 2018 (the fourth batch) to see the next byte algorithm pen test difficulty geometry. Address: www.nowcoder.com/test/853663…

There are four questions in this set, two essay questions and two programming questions.

One of the quiz questions is the original LeetCode 426 question, but the question type has changed to find fault (correct mistakes). Unfortunately, question 426 of LeetCode is a membership question, and it is hard to read without membership. However, the sword point Offer also has this question, and force buckle sword point Offer all questions are OJ. You can go to leetcode-cn.com/problems/er… Submit your answer. To briefly explain the idea of this topic, we can get an ordered sequence only by middle order traversal, and at the same time, we can connect the pre and cur nodes through Pointers in the middle order traversal process.

Another question and answer is the red envelope question, which is not covered here. Let’s focus on the two remaining algorithmic programming problems.

I didn’t do the two essay questions because I couldn’t judge them online, so I only did the remaining two programming questions.

team

The first programming problem is a team competition problem.

Topic describes

There are three teams, and each team is numbered team 1, team 2, and team 3, and they have to play a total of n games. Now k matches have been played, each match can not draw, win a match will get one point, lose will not be deducted points. Given that the score difference between team 1 and Team 2 is D1, and the score difference between team 2 and team 3 is D2, each game can be played by any two teams. If you play the last (n-k) game, is it possible that all three teams are tied?

Train of thought

So let’s say team 1, team 2, team 3 and the number of wins is a, B, C, team 1, team 2, team 3 and the total number of wins is n1, n2, n3.

My initial thought was just to make sure that n1, n2, and n3 are equal and less than or equal to n over 3. If the problem gives the values of n1, n2, and n3, the answer is:

print(n1 == n2 == n3 == n / 3)
Copy the code

But not just n1, n2, and N3, but also A, B, and C.

In fact, our message at this point is just:

① a + b + c = k ② a - b = d1 ③ b - c = d2 or c - b = d2Copy the code

Where k and d1 and d2 are known. A, B, and C are unknown. That is, we need to enumerate all the possibilities of a, b, and c, solve the equation to find legitimate a, b, and C, legitimate A, b, and c is less than or equal to n over 3.

The mathematical equations of A, B and C are difficult to solve in middle school mathematics. The three equations can be simplified, as shown in the code area below.

  • A only has to win n over 3 minus a times again
  • B only has to win n over 3 minus b times
  • C only has to win n over 3 minus c times again
n1 = a + n / 3 - a = n / 3
n2 = b + (n / 3 - b) = n / 3
n3 = c + (n / 3 - c) = n / 3
Copy the code

Code (Python)

It’s a bit annoying that you need print instead of return

t = int(input())
for i in range(t):
    n, k, d1, d2 = map(int.input().split(""))
    if n % 3! =0:
        print('no')
        continue
    abcs = []
    for r1 in [-1.1] :for r2 in [-1.1]:
            a = (k + 2 * r1 * d1 + r2 * d2) / 3
            b = (k + -1 * r1 * d1 + r2 * d2) / 3
            c = (k + -1 * r1 * d1 + -2 * r2 * d2) / 3
            a + r1
            if  0 <= a <= k and 0 <= b <= k and 0 <= c <= k and a.is_integer() and b.is_integer() and c.is_integer():
                abcs.append([a, b, c])
    flag = False
    for abc in abcs:
        if len(abc) > 0 and max(abc) <= n / 3:
            flag = True
            break
    if flag:
        print('yes')
    else:
        print('no')
Copy the code

Complexity analysis

  • O(t)O(t)O(t)
  • Space complexity: O(t)O(t)O(t)

summary

There are also some mathematical equation conversion questions, such as 494. Target-sum

Conversion string

Topic describes

There is a string S containing only ‘a’ and ‘b’ characters of length N that can convert one character per operation (either setting a ‘a’ to ‘b’ or a ‘b’ to ‘a’); However, there is an upper limit on the number of operations. What is the maximum contiguous length of the same character within a limited range of operands?

Train of thought

I had a feeling of deja vu after reading the questions.

Every time you say this to a girl, she feels so fake

But this time it’s real.” Oh, no! It’s true every time. This problem is actually a sliding window problem (1004. The maximum number of consecutive 1 III) I wrote before the sliding window (Python3) change problem. Special address: github.com/azl39798585…

So, if you don’t have any ideas on this one. Description:

  • Lack of abstraction.
  • The sliding window problem is not fully understood.

The second problem can be solved by looking at the address posted above, reading carefully and completing the exercises after class.

The first question is more difficult, but I can also slowly improve the solution. Such as:

  • Cut the Rope is actually 343. Integer split skin problems.

  • Force buckle 230 and force buckle 645 is to change the skin problem, details refer to the bit operation topic

  • And I took your clothes off. – Longest Common subsequence.

  • And get dressed and I don’t know who you are? Let’s talk about the longest ascending subsequence

  • As well as a move to eat force buckle four questions, my mother no longer need to worry about my routine ~

  • , etc.

So let’s go back to the problem. Actually, we just need to abstract it a little bit, it’s a pure algorithmic problem. Another advantage of abstraction is that it takes a lot of different topics back to their original simplicity, so that they can escape in a sea of questions. That’s one of the reasons I started I am Your Mother.

If we view a as 0 and b as 1. Or you could view b as 1 and a as 0. Don’t abstract into:

Given an array A of 0s and 1s, we can change up to m values from 0 to 1. Returns the length of the longest (continuous) subarray containing only 1.Copy the code

This is the force button 1004. The maximum number of consecutive 1 III original problem.

So we’re actually looking for the two cases above:

  1. A is 0, b is 1
  2. A is 1, b is 0

The greater value of.

Lucifer’s tip: You can also consider only one case, where a is 0 and B is 1. At this point, we’re doing two things, 0 becomes 1 or 1 becomes 0, and we’re solving for the longest continuous 0 or the longest continuous 1. Since this abstraction is more difficult to operate, we will not consider.

The problem is abstracted and solved. We just need to record whether 0 or 1 is added to the window:

  • If it’s 1, we don’t have to do anything, right
  • If it’s 0, we subtract 1 from m

Accordingly, we need to record whether the removed window is 0 or 1:

  • If it’s one, we don’t do anything, right
  • If it’s 0, that means it’s going to be 1 when we add it in, when we subtract 1 from m, we’re going to add another 1.

Lucifer tip: Actually, the problem is to find the length of consecutive a or b. If you see continuity, you should also have the sensitivity of sliding Windows, regardless of whether it works or not, you should always have it.

Let’s take A = [1, 1, 0, 1, 0, 1], m = 1. Take a look at the specific process of the algorithm:

Lucifer tip: The number on the left represents the size of the window, the yellow box represents the repaired wall, and the black box represents the window.

Here I visualize 0 as a hole and 1 as a wall, and our goal is to fill the hole so that the continuous wall is the longest.

Every time we hit a hole, we tinkered indiscriminately. And since m is equal to 1, that means we can fill at most one hole. Therefore, when repairing more than one hole, we need to adjust the window range so that at most one wall can be repaired in the window. Since the window represents a continuous wall (existing or patched), we will eventually return the maximum value of the window.

Since the diagram below has two holes in the window, which conflicts with “fill one hole at most”, we need to shrink the window to satisfy the “fill one hole at most” prerequisite.

So the largest window is Max (2, 3, 4…). = 4.

Lucifer tip: You can see that we patched all the holes indiscriminately and adjusted the window so that there were at most m patched holes in the window, so the maximum number of patched holes is the answer. In reality, however, we don’t really need to “fix” (0 to 1), but just change the value of m.

Let’s take a look at the code for one of the cases after abstraction:

class Solution:
    def longestOnes(self, A: List[int], m: int) - >int:
        i = 0
        for j in range(len(A)):
            m -= 1 - A[j]
            if m < 0:
                m += 1 - A[i]
                i += 1
        return j - i + 1

Copy the code

So the complete code is:

class Solution:
    def longestOnes(self, A: List[int], m: int) - >int:
        i = 0
        for j in range(len(A)):
            m -= 1 - A[j]
            if m < 0:
                m += 1 - A[i]
                i += 1
        return j - i + 1
    def longestAorB(self, A:List[int], m: int) - >int:
        return max(self.longestOnes(map(lambda x: 0 if x == 'a' else 1, A) ,m), self.longestOnes(map(lambda x: 1 if x == 'a' else 0, A),m))
Copy the code

The two maps here generate two different arrays. I just created the two arrays to make it easier for you to understand, but you don’t need them at all, see the code below.

Code (Python)

i = 0
n, m = map(int.input().split(""))
s = input()
ans = 0
k = m # save it, use the same initial value later
Repair # b
for j in range(n):
    m -= ord(s[j]) - ord('a')
    if m < 0:
        m += ord(s[i]) - ord('a')
        i += 1
ans = j - i + 1
i = 0
# to repair a
for j in range(n):
    k += ord(s[j]) - ord('b')
    if k < 0:
        k -= ord(s[i]) - ord('b')
        i += 1
print(max(ans, j - i + 1))

Copy the code

Complexity analysis

  • Time complexity: O(N)O(N)O(N)
  • Space complexity: O(1)O(1)O(1)

summary

This problem is a change of skin force buckle, medium difficulty. If you can abstract the problem and understand sliding Windows, it’s easy. I have read the reference answers in the solution area, but the content is confused and not clear enough. That’s one of the reasons I’m writing this article.

conclusion

There are four questions in this set of Bytedance, one design question and three algorithm questions.

Among them three algorithm questions from the difficulty, the basic is medium difficulty. From the point of view of content, it is force buckles basically change skin problem. But would you notice if I didn’t say they were skin changes? If you can, your abstraction skills are a bit low. If you don’t, follow me. Hand hand pickpocket skin to you see, pick more slowly will be. Remember, don’t do it blindly! If you’ve done a lot of questions and you still don’t see the pattern, it’s time to slow down and change the way you brush the questions.

For more solutions, visit my LeetCode solution repository: github.com/azl39798585… . Currently, it has 36K+ star.

Pay attention to the public number force buckle plus, and strive to use clear and straightforward language restore problem solving ideas, and there are a lot of diagrams, hand in hand to teach you to identify routines, efficient brush.