It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
Apparently, many engineers take measures on the site called LetCode.
It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.
I wrote it in a big way, but I have no plans to have such an interview at the moment.
However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.
I'm solving it with Python3.
Leet Code Table of Contents Starting from Zero
Last time Leet Code Day54 starting from zero "1290. Convert Binary Number in a Linked List to Integer"
Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.
Twitter I'm doing it.
The difficulty level is Medium. Excerpt from Top 100 Liked Questions.
The problem is given the positive integer n. Let's design an algorithm that writes out all the combinations of that number of parentheses.
I recently learned that natural numbers include 0 in university mathematics ...
For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]
It's easier to understand if you look at the example.
# solution
It's a question about the combination, so I couldn't solve it at first glance, so I glanced at the discuss and studied the way of thinking.
It is easier to understand if you divide the parentheses into right, `right` and left, and` left`.
I think that it can be solved relatively easily if you apply the `n` as each argument and continue adding until they become 0, which is the so-called backtrack method.
As a specific conditioning
--The first and last placement of parentheses must be absolute
--Add to the array when both are 0
--Otherwise, the function is called back recursively.
The code below summarizes `dfs` separately to make them easier to read.
```python
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
self.dfs(n,n,"",ans)
return ans
def dfs(self,left,right,path,ans):
if left > right or left < 0 or right < 0:
return
if left == 0 and right == 0:
ans.append(path)
return
self.dfs(left-1,right,path+'(',ans)
self.dfs(left,right-1,path+')',ans)
# Runtime: 32 ms, faster than 78.59% of Python3 online submissions for Generate Parentheses.
# Memory Usage: 13.9 MB, less than 93.80% of Python3 online submissions for Generate Parentheses.
I recently noticed that when LeetCode changes from Easy to Medium, it handles more variables, and I get the impression that it is easier to solve if you have mathematical probabilities, number of cases, and integer knowledge rather than being familiar with programming languages. I did.
Most of the people who receive these interviews are in the information and science fields, and I feel that such knowledge does not seem to be a pain, but when I saw a problem with a few people like me? In many cases, it seems necessary to acquire such knowledge in order to challenge higher difficulty levels.
So that's it for this time. Thank you for your hard work.
Recommended Posts