Write a function to generate all valid nested parenetis for a given value N. So for example:
If N = 1: "()"
if N = 2: "()()", "(())"
if N = 3: "()()()","()(())","(())()","(()())","((()))"

Question

Write a function to generate all valid nested parenetis for a given value N. So for example:
If N = 1: "()"
if N = 2: "()()", "(())"
if N = 3: "()()()","()(())","(())()","(()())","((()))"

Sigiloso · Accepted Answer

There is a way to do this with backtracking and a more DP-like approach. I went with the later because I found it easier to reason. If you search for "Generate Parenthesis" in your search engine of choice you should be able to find solutions. Mine more or less looked like this:

    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0:
            return ['']

        results = []
        for x in range(n):
            for l in self.generateParenthesis(x):
                for r in self.generateParenthesis(n-1-x):
                    results.append('({}){}'.format(l, r))

        return results

Sigiloso · Answer

The key in generic questions like this, is to make sure to cover the fundamentals. There's usually a back-and-forth with the interviewer.
      

Might be worth doing a mock interview with one of the Spotify Senior Software Engineer experts on Prepfully? Really helps to get some real-world practice and guidance.
      

prepfully.com/practice-interviews

Spotify

Pergunta de entrevista da empresa Spotify

Respostas da entrevista

Empresas seguidas

Buscas de vagas