preface

Algorithms are becoming more and more important in the industry. First-tier Internet companies also attach great importance to algorithms, so they are basically involved in the interview. Bytedance is notoriously algorithmic, with algorithms being asked on almost every side of the question. In fact, now many companies will ask the algorithm, especially for fresh graduates, higher requirements, so want to enter the big factory, it is very important to deal with the algorithm.

Some time ago, I went to a bytedance interview, finally entered the fourth side, saw the offer was about to get, unfortunately, was an “algorithm” to intercept the offer, and byte missed. Share this algorithm today and let’s talk about how to nail a bytedance interview!

 

Blocking my offer is the algorithm

Given a string containing only ‘(‘, ‘)’, determine whether the string is valid. Note: Empty strings are valid strings

Example 1: input: "(())" output: true example 2: input: "()) (" output: falseCopy the code

At first glance, this question is so simple and stable. (Leetcdoe)

So I also used the stack to solve it directly without thinking, I believe that 99% will use the stack to solve it, right? Here I will talk a little about the process. The steps are as follows:

(“)” (“)” (“)” (“)” (“)” (“)”

(1), if there is, the "(" pop, equivalent to ")" at the top of the stack matches, and then continue through the string (2), if there is no, the match fails. ")" at the beginning of the string, which is obviously not reasonable.Copy the code

2. When the string traversal is complete, check whether the stack is empty. If it is empty, the string is valid; otherwise, it is invalid.

In order to give attention to both sides small white, I should draw a diagram to demonstrate to you ，，，， I too conscience.

 

The code looks like this:

public static boolean isValid(String s){ if(s == null || s.length() < 1) return true; int n = s.length(); Stack<Character> Stack = new Stack<>(); For (int I = 0; i < n; Char c = s.charat (I); char c = s.charat (I); if(c == '('){ stack.push(c); }else{ if(stack.isEmpty()) return false; else stack.pop(); If (stack.isempty ()) return true; return false; }Copy the code

Then the interviewer told me that the spatial complexity of my problem was O(n), and asked me if I could optimize it.

To be honest, if you’ve done leetcode number 20, maybe your brain is going to be directed or not, because that’s the optimal solution to handle on a stack. But this is a simplified version of the problem, and you can actually optimize the space to order 1, so you can think about it.

Since we all have the same type of character “(” in the stack, we can actually replace the stack with a variable, which records the number of “(“, increment “(” variable “, decrease “)” variable, empty stack equivalent to the value of the variable is 0.

At that time, I didn’t know why, so I immediately thought of this method, so a minute to modify the code, as follows:

public static boolean isValid(String s){ if(s == null || s.length() < 1) return true; int n = s.length(); Int sum = 0; int sum = 0; For (int I = 0; i < n; Char c = s.charat (I); char c = s.charat (I); if(c == '('){ sum++; }else{ if(sum == 0) return false; else sum--; } } return sum == 0 ? true : false; }Copy the code

In this case, the time complexity is O(n), the space complexity is O(1).

The interviewer then went on to make the question harder and changed it to the following

Given a string containing only ‘(‘ and ‘)’, find the length of the longest substring containing valid parentheses.

Example 1: input: "(() output: 2 explained:" the longest substring bracket is effectively "()" example 2: input: ") () ()) "output: 4: longest substring bracket is effectively" () ()"Copy the code

32. This is the original Leetcode.

Since I had done this problem before, I smiled, pretended to think about it with a serious expression, and then immediately gave the idea, at first I used violence.

1. Violence

The brute force method is as simple as iterating the string as the first character of the longest valid parenthesis, then iterating the string as the second character of the longest valid parenthesis, and then iterating the string as the third character……

For example, for s = “()) (())”.

Take the first character as the first character, Max = 2 (the third character ‘)’ will not match) take the second character as the first character, Max = 0 (the first character is ‘)’, obviously will not match anything) Take the third character as the first character, Max = 0 take the fourth character as the first character, Max = 4….. This is O(n^2) in time, O(1) in space.

Basically, we did the same thing, but we did n iterations.

The interviewer then asks, can it be optimized?

I already knew that I would ask for optimization. I had done this problem myself before, so I pretended to think about it and immediately gave optimization.

2, to optimize

In the optimized version of this problem, we’re still going to do it on a stack, but instead of pushing “(“, we’re going to push the index of “(“. The steps are as follows:

1. Put -1 on the stack. (As for why? For each ‘(‘ encountered, we put its subscript on the stack. 3. For each ‘) ‘encountered, we pop the top element on the stack and subtract the current element’s subscript from the pop element’s subscript to get the length of the current valid parenthesis string.

In this way, we proceed to calculate the length of the valid substring and eventually return the length of the longest valid substring.

Look not to understand? Ok, I’ll make an example to draw some graphs, such as s = “()) (())”, and use the variable Max to hold the degree of the longest valid string, I is the index of the current string

0, initialization: Max = 0; I = 0. Minus one goes on the stack

 

1, I = 0, s[I] = ‘(‘, subscript I = 0

 

2, I = 1, s[I] = ‘)’; I – top element = 1 – (-1) = 2, Max = 2

 

3, I = 2, s[I] = ‘)’; Note at this point: since there are no more elements at the top of the stack after -1, we must put the subscript ‘)’ on the stack, which is equivalent to the initial initialization.

 

4、i = 3，s[i] = ‘(‘，入栈;

 

5、i = 4，s[i] = ‘(‘，入栈;

 

6, I = 5, s[I] = ‘)’; I – top = 5-3 = 2; Max = 2;

 

7, I = 6, s[I] = ‘)’; I – top = 6-2 = 4; Max = 4;

 

The traversal is complete. The longest valid parenthesis is 4.

Don’t get it? Ok, look at the code to deepen the understanding, the code is as follows:

public int longestValidParentheses(String s) { int max = 0; Stack<Integer> stack = new Stack<>(); stack.push(-1); for (int i = 0; i < s.length(); I++) {if (s.c harAt (I) = = '(') {/ / subscript stack stack. Push (I); } else {// stack.pop(); If (stack.empty()) {stack.push(I); } else {Max = math.max (Max, i-stack.peek ());} else {Max = math.max (Max, i-stack.peek ()); } } } return maxans; }Copy the code

This is O(n) in time, O(n) in space, and it’s nice to think of stacks.

The final blow

I thought I gave this solution is ok, the interviewer should change a question, and then, the interviewer came to a: can you optimize again? . This time I fell into a meditation…….

Everyone who read the article can think about whether it can be optimized in space, because it is impossible to optimize in time.

After thinking for a while, I was surprised to find that the stack could not be used. The optimal solution must be similar to the above problem, which is to replace the stack with the variable of the number of records. Then I came up with the following details:

In fact, this problem could still be optimized by using variables instead of stacks as above, but in this case we need two variables, and we assume that the variables are left and right.

We use left to record the number of ‘(‘ and right to record the number of ‘)’ as we traverse the string from left to right. And in the process of traversal:

1, if left == right, it is clear that right ‘)’ will be matched. So the current valid parenthesis length is 2 * right. Then update Max.

If left < right, the partial ‘)’ will not match, and we set both left and right to 0.

When we’re done iterating through the string, do we have the maximum length of valid parentheses? You can think about it

No, we’re going to have to iterate from right to left.

Why is that?

Since ‘(‘ and ‘)’ are actually equivalent, why can’t we iterate backwards? So don’t forget about it.

The final code looks like this:

public int longestValidParentheses(String s) { int left = 0, right = 0, max = 0; For (int I = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, 2 * right); } else if(right > left){ left = right = 0; } } left = right = 0; // from right to left for (int I = s.length() -1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { max = Math.max(max, 2 * left); } else if (left > right) { left = right = 0; } } return max; }Copy the code

This approach is O(n) in time and O(1) in space.

Note: The topic of this article is “algorithm”, and you need to pay attention to the official account at the end of the article for free.

Review the algorithm and fight bytedance again

Bytedance always has an obsession in my mind, so I plan to fight Bytedance in the second world War. However, I still need to pay attention to the algorithm, so the review of the algorithm is particularly important. For algorithm learning, I mainly read some books and documents as follows:

(1) LeetCode Chinese version

 

 

 

(2) The fun of algorithms

 

 

 

(3) Algorithm

 

 

More algorithm information:

 

Above these algorithm information, can share for free, there is a need for private message I get password [algorithm] free download.

conclusion

Algorithms need a lot of practice. First of all, we need to choose good basic textbooks to strengthen our theoretical knowledge, and then we need to practice on the computer based on the theory here.

If you are also interested in learning algorithms, and want to get the relevant information about the above algorithms, forward + comment on my article, follow the public account below can get free download method ~