I created the most inefficient working solution

I was doing a challenge from the Interview Prep section https://www.freecodecamp.org/learn/coding-interview-prep/algorithms/no-repeats-please. I wrote a function that does the job but does it so horribly that it still fails two of the conditions of the test, even though it still does return the correct results…after 46 seconds. But that’s for 7 letters, for a smaller number of letters it works ok. Some code editors will crash if you use 7 letters though, so use a sturdy one like Programiz if you want to run this code. My question is, can this code be modified to pass the test, while still preserving the logic?

function permAlone(arg) {

    let length = arg.length
    let arr = []

    function uniqueIndices() { // generate a set of non-repeating integers to represent indices 
        let indices = new Array(length)
        for (let i = 0; i < indices.length; i++) {
            let r = Math.floor(Math.random() * length)
            if (indices.indexOf(r) === -1) {
                indices[i] = r
            } else {
                i--
            }
        }
        return indices
    }

    function factorial(n) {
        let product = 1;
        for (let i = 2; i <= n; i++) {
            product *= i;
        }
        return product;
    }
    let length2 = factorial(arg.length) // factorialize the length of arg to set the length of next loop which will be filled with sets of non-repeating integers
    for (let i = 0; i < length2; i++) {
        let val = uniqueIndices(arg)
        if (arr.map(a => a.join('')).indexOf(val.join('')) === -1) { // make sure the sets of integers are all unique
            arr[i] = val
        } else {
            i--
        }
    }
    for (let indices of arr) { // now that we have the unique sets of non-repeating indices, convert each integer in the set to a letter in arg with the corresponding index 
        for (let i = 0; i < indices.length; i++) {
            indices[i] = arg[indices[i]]
        }
    }

    function final(a) { // final function to record the number of sets that have repeated consecutive letters 
        let ct = 0;
        for (let x of a) {
            for (let i = 0; i < x.length; i++) {
                if (x[i] === x[i + 1]) {
                    ct++
                    break;
                }
            }
        }
        return ct
    }
    // to find the number of sets without repeated consecutive letters, substract their number from arr.length
    return arr.length - final(arr)
}

console.log(permAlone(['a', 'b', 'c', 'd', 'e']))```

Yes and no. Some of the specific logic is causing such run time, so that would need to be changed. At the same time, the general structure - the more overall way function arrives at the result is good enough to pass, when some specifics are improved.

Can you give me a hint? What specifics?

There are two places using similar pattern, which are using some randomness to generate unique permutations. One thing to consider might be figuring out some way not relying on randomness and keeping track of previous combinations.

If you’d like to keep that way, consider how checking for duplicates is done. Searching through array is relatively slow, as it in worst case scenario (i.e. confirming element isn’t already in array) requires iterating through all array. The bigger the array, the more time that takes.

I think I’ll keep the randomness aspect, since it’s at the core of the logic, but how should I go about checking for duplicates? Plus the problem seems to lie in the loop that creates an array equal to the factorial of arg.length, or at least that’s what the test says when I run it. Can you point me further to the solution?

Relying on randomness can be an amusing challenge, but even though it can be an interesting approach it is worth noting that you wouldn’t take such an approach in most professional code. You only incorporate randomness when a deterministic algorithm won’t get results in a reasonable time frame.

I understand, and I will look into more optimal solutions once I tweak my function so that it passes the test, but I just want to make it passable first.

By that definition everything in code can be considered as core of the logic.

It won’t pass without making changes. But if you want to explore only selected set of changes that you have in your mind, which are not touching parts that are heavily impacting efficiency, nobody can force you otherwise.

1 Like

I fixed it.

function permAlone(arg) {

    let length = arg.length
    let arr = []

    function uniqueIndices() { // generate a set of non-repeating integers to represent indices 
        let indices = new Array(length)
        for (let i = 0; i < indices.length; i++) {
            let r = Math.floor(Math.random() * length)
            if (indices.indexOf(r) === -1) {
                indices[i] = r
            } else {
                i--
            }
        }
        return indices.join('')
    }

    function factorial(n) {
        let product = 1;
        for (let i = 2; i <= n; i++) {
            product *= i;
        }
        return product;
    }
    let length2 = factorial(arg.length) // factorialize the length of arg to set the length of next loop which will be filled with sets of non-repeating integers
    for (let i = 0; i < length2; i++) {
        let val = uniqueIndices(arg)
         if (arr.indexOf(val) === -1) { // make sure the sets of integers are all unique
            arr.push(val)
         } else {
             i--
         }
    }
    arr = arr.map(a => a.split(''))
    arr = arr.map(a => a.map(a => Number(a)))
    arr = arr.map(a => a.map(a => arg[a])) // now that we have the unique sets of non-repeating indices, convert each integer in the set to a letter in arg with the corresponding index 
        

    function final(a) { // final function to record the number of sets that have repeated consecutive letters 
        let ct = 0;
        for (let x of a) {
            for (let i = 0; i < x.length; i++) {
                if (x[i] === x[i + 1]) {
                    ct++
                    break;
                }
            }
        }
        return ct
    }
    // to find the number of sets without repeated consecutive letters, substract the number of sets with repeated consecutive letters from arr.length
    return arr.length - final(arr)
}

console.log(permAlone(['a', 'b', 'c', 'd', 'e', 'f', 'a']))

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.