Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Permutations (medium)

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

You are inserting elements into vector which means that you have to reallocate whole vector and you repeat it several times. I know that it isn't about language but ... I found that c++ level in this course is really bad. Sorry but I have to say it ...

A

Anonymous

· 2 years ago

from collections import deque

class Solution:
  def findPermutations(self, nums):
  
    def backtrack(index, result, path, seen):
      if len(path) == len(nums):
        result.append(path[:])
        return 

      for i, num in enumerate(nums):
        if i not in seen:
          seen.add(i)
          path.append(num)
          backtrack(i, result, path, seen)
          seen.remove(i)
          path.pop()
    
    result = []
    backtrack(0, result, [], set())

    return result
A

Anonymous

· 3 years ago

Description says:

Given a set of distinct numbers, find all of its permutations.

However, one of the test cases contains duplicate numbers: [1, 3, 5]

[1, 2]

[2, 2]

Show 1 reply
A

Anonymous

· 3 years ago

"If a set has ‘n’ distinct elements it will have n!n! permutations.". It should be n! only.

A

Anonymous

· 4 years ago

Contradictory between the code and the description, the description says "we are iterating through all of these permutations with the help of the two ‘for’ loops". Apparently, from the code, we make 3 loops.

Should the time complexity be O(N^2*N!) instead?

Show 1 reply
A

Anonymous

· 4 years ago

How do you solve this if the numbers are not distinct?

Show 4 replies
A

Anonymous

· 4 years ago

what is the advantage of deque here in js solution? I did the same general thing but kept my result as an array of arrays that was replaced each time i finished adding an element to each. function test(distinct) { let output = [[]]; distinct.forEach(el => { const newOutput = [] output.forEach(ar => { const possiblePlaces = ar.length + 1 for (let i = 0; i < possiblePlaces; i++) { const newArr = [] for (let j = 0; j < i; j++) { newArr.push(ar[j]) } newArr.push(el) for (let j = i; j < ar.length; j++) { newArr.push(ar[j]) } newOutput.push(newArr) } }) output = newOutput }) return output }

Show 2 replies

Reading Progress

0%

Vote for new content