Coding Journal

Jordan Vidrine

Daily Coding Journal

A Self-taught coder from the Cajun Prairie in rural Louisiana, currently working as a designer for Discourse.

I am always trying to better myself, and do so through learning new skills, trying out new routines, traveling, and pouring energy into hobbies. Since 2014, I have been recording, editing, and producing my own music under the name Skies Speak.

October 27th

We are continuing on with the Aglorithms course. Next up…

Divide and Conquer

This pattern involvers dividing a data set into smaller chunks and then repeating a process with a subset of data. This pattern can tremendously decrease time complexity.

An example Given a sorted array of integers, write a function called search, that accepts a vlue and returns the index where the value passed to the function is located. If the value is not found, return -1.

search([1,2,3,4,5,6],4) // 3
search([1,2,3,4,5,6],6) // 5
search([1,2,3,4,5,6],11) // -1

A naive solution to this problem could look something like this:

function search(arr,value){
  for(let i = 0; i < arr.length; i++){
    if (arr[i] === val) {
      return i;
    }
  }
  return -1;
}

This solution time complexity is O(n).(linear)

The following refactor is a Binary Search. It looks a little different, and its time complexity comes out to be Log(n).

function search(arr, val) {
  let min = 0;
  let max = array.length -1;

  while ( min <= max) {
    // sets the current index to be the middle
    let middle = Math.floor((min+max) / 2);
    // if the value at the middle of the array is LESS than the value
    // it sets the new beginning of the array to look for as the IDX right before middle
    // IE arr = [1,2,3,4,5,6,7,8,9,10] val = 9
    // middle will equal 6 and the new array to check will be the middle of [6,7,8,9,10]
    if (array[middle] < val) {
      min = middle -1;
    }
    else {
      return middle;
    }
  }

  return -1;
}

This will save a lot of time, instead of going through every single element, it uses calculations to get the number at the middle index, and continues to divide and conquer until it gets to the correct value.

It is a little complicated, but it works well. We will work with this algorithm more often later in the course.

Optional Exercises

Write a function called sameFrequency. Given two positive integers, find out if the two numbers have the same frequency of digits. Solution MUST have O(N) complexity.

// sameFrequency(182,281) // true
// sameFrequency(34,14) // false
// sameFrequency(3589578, 5879385) // true
// sameFrequency(22,222) // false
function sameFrequency(int1,int2) {

    let int1Obj = {};
    let int2Obj = {};

    for (let val of int1.toString()) {
        int1Obj[val] ? int1Obj[val]++ : int1Obj[val] = 1;
    }

    for (let val of int2.toString()) {
        int2Obj[val] ? int2Obj[val]++ : int2Obj[val] = 1;
    }

    for (let key in int1Obj) {
        if (int1Obj[key] !== int2Obj[key]) return false;
    }

    return true;
}

Implement a function called areThereDuplicates which accepts a variable number of arguments, and checks whether there are any duplicates among the arguments passed in. You can solve this using the frequency counter pattern OR the multiple pointers pattern. Both time & Space complexity must be O(n).

// areThereDuplicates(1,2,3) // false
// areThereDuplicates(1,2,2) // true

function areThereDuplicates(...args) {

    if (args === 0) return false;

    let set = new Set();

    for (let arg of args) {
        if (!set.has(arg)) {
            set.add(arg)
        } else if (set.has(arg)) {
            return true;
        }
    }

    return false;
}

// Refactor based on solution from instructor
function areThereDuplicates(...args) {
  return new Set(args).size !== args.length;
}

Write a function called averagePair. Given a SORTED array of integers and a target average, determine if there is a pair of values in the array where the average of the pair equals the target value. There may be more than one pair that matches the average target.

// averagePair([1,2,3], 2.5) // true
// averagePair([1,3,3,5,6,7,10,12,19], 8) // true
// averagePair([-1,0,3,4,5,6], 4.1) // false
// averagePair([], 4) // false

// solution based on Multiple Points pattern
function averagePair(arr,targetAvg) {
    let left = 0;
    let right = arr.length -1;

    while (left < right) {
        let avg = arr[left] + arr[right] / 2
        if (avg === targetAvg) return true;
        else if (avg < targetAvg) left++;
        else right--;
    }

    return false;
}

Write a function called isSubsequence which takes in two strings and checks whether the characters in the first string form a subsequence of the characters in the second string. The function should check whether the characters in the first string appear somewhere in the second string, without their order changing.

// isSubsequence('hello','hello world') // true
// isSubsequence('sing', 'sting') // true
// isSubsequence('abc', 'abracadabra') // true
// isSubsequence('abc', 'acb') // false (order matters)

Back to blog...