A Few Algorithms and How to Solve Them

In order to prepare for a round of interviews, I started keeping track of the algorithms I solved. Most of these were from Code Signal and are in Javascript. I explain my thought process for each step.

Knapsack Light

Given two items with differing weights and values, write an algorithm to carry the maximum value without exceeding your knapsack's weight.

Initiate a max value variable

    let maxVal = 0; 

If the weights are equal, add both to max value.

    if(weight1 + weight2 <= maxW){
        maxVal = value1 + value2
    } 

If not, check for every other combination.

    else {
        if(weight1 <= maxW && value1 > value2){
            maxVal = value1
        } else if (weight2 <= maxW && value2 > value1) {
            maxVal = value2
        } else if (weight1 > maxW && weight2 <= maxW){
            maxVal = value2
        } else if (weight2 > maxW && weight1 <= maxW){
            maxVal = value1
        } else if (value1 === value2 ){
            maxVal = value1
        }
    }

Return max value.

    return maxVal

Circle of Numbers

Consider integer numbers from 0 to n - 1 written down along the circle in such a way that the distance between any two neighboring numbers is equal (note that 0 and n - 1 are neighboring, too).

Given n and firstNumber, find the number which is written in the radially opposite position to firstNumber.

Solution

Find the halfway point by dividing the distance by 2 (round up)

let halfway = Math.round(n/2)

Add the halfway point to the firstNumber

let total = firstNumber + halfway

If the number is less than the total, that's the answer. If not, subtract the distance from the total

  if(total >= n){
        return total - n
    } else {
        return total
    }

Alternating Sums

Sum alternating numbers in an array.

Solution

Define totals.

 let total1 = 0
 let total2 = 0    

Loop through to add alternating numbers using the index.

   for(let i = 0; i < a.length; i++){
        if(i % 2 == 0){
            total2 += a[i]
        } else {
            total1+= a[i]
        }

Push totals new array.

let newArray = []
    newArray.push(total2, total1)
   return newArray

All Longest String

Given an array of strings, return another array containing all of its longest strings.

Solution

Create an array to store all the longest strings.
Create a len value to hold the length of the longest string and set it to zero.

var len = 0; 
var longest = []; 

Loop through the array of strings. Find the longest string and set that to the len value.

for (var i = 0; i < inputArray.length; i++){
        if(inputArray[i].length > len){
            len = inputArray[i].length 
        }
    }

Loop through the array in a separate for loop. If a string's length is equal to the value of len, push into the longest array.

   for (var j = 0; j < inputArray.length; j++){
        if(inputArray[j].length === len){
            longest.push(inputArray[j])
        }
    }

Return the longest array.

 return longest

isLucky

Given an even integer, return true if the first half of numbers equals the second half.

Solution

Create an array of integers

    const arr = [] 
    while (n > 0){
        let lastDigit = n % 10 
        arr.push(lastDigit)
        n = Math.floor(n/10)
    }

Break the array into two halves

    const half = Math.ceil(arr.length / 2);
    const firstHalf = arr.splice(0, half)
    const secondHalf = arr.splice(-half)

Sum up the totals of each half; return true if the totals match

    let totalOne = 0; 
    let totalTwo = 0;
    for(let i = 0; i < firstHalf.length; i++){
        totalOne += firstHalf[i]
    }

    for(let i =0; i < secondHalf.length; i++){
        totalTwo += secondHalf[i]
    }

    if(totalOne === totalTwo){
        return true
    } else {
        return false
    }

Conclusion

Some of these I made some time ago and I can already see some optimizations and ways to create DRY-er code. I also noticed that I LOVE to use the for loop. Going forward, I'd like to incorporate more built in methods like every, some, and map.