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 21st

Continuing from last week, we were looking at the Frequency Counter problem solving pattern. Lets being by looking at my refactored solution to a problem.

Frequency Counter Continued

function same(arr1,arr2){
  for (let i = 0; i < arr1.length; i++) {
      let idx = arr2.indexOf(arr1[i]*arr1[i])
      if (idx !== -1) {
          arr2.splice(idx,1)
      } else {
          return false;
      }
  }
  return true;
}

Inside of the for loop, I used the Array.prototype.indexOf to check if the squar of an array value existed inside of another array. Using index of essentially acts as another loop inside of my for loop. My solution operates in O(n2) time. There is a way we can solve this without using a nested loop, which will be O(n) time.

In the refactored solution, we still will be looping, but we will have two separate loops, and they will not be nested into one another. This is vastly more performant.

Here is how that looks:

function same(arr1, arr2) {
  if (arr1.length !== arr2.length){
    return false;
  }
  let freqCounter1 = {};
  let freqCounter2 = {};
  // adds keys to the freq object with the value being the num of times
  // that key appears
  for (let val of arr1) {
    freqCounter1[val] = (freqCounter1[val] || 0) + 1
  }
  for (let val of arr2) {
    freqCounter2[val] = (freqCounter2[val] || 0) + 1
  }
  for (let key in freqCounter1) {
    // checks to see if there is a squared version of the current key
    // inside of the second object
    if (!(key ** 2 in freqCounter2)) {
      return false;
    }
    // checks to see if the squared value occurs the same number of times
    // as the regular value
    if (freqCounter1[key] !== freCounter2[key ** 2]) {
      return false;
    }
  }
  return true;
}

At first this was a little complicated but I now understand how this is a better solution in terms of time and performance. It is easier/faster on the computer to read and compare values in an object instead of an array. I also can clearly understand what is happening here even though it turns out to be more lines of code, it makes sense to me why its better.

Anagram Challenge

Given two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

Reading this prompt directly leads me to think I can solve this using pretty much the same code as the previous issue. Although it is the same, here is my solution.

function validAnagram(str1,str2) {
    // if the strings are a different length, it cant be an anagram, return false
    if(str1.length !== str2.length) {
        return false;
    }
    let freq1 = {}
    let freq2 = {}
    // build up the freq counting objects
    for (let char of str1) {
        freq1[char] = (freq1[char] || 0) + 1
    }

    for (let char of str2) {
        freq2[char] = (freq2[char] || 0) + 1
    }

    // check to see if the characters appear the same amount of times in each obj
    for (let key in freq1) {
        if (!(key in freq2)) {
            return false
        }
        if (freq1[key] !== freq2[key]) {
            return false;
        }
    }
    return true;
}

I liked my implementation of the solution, but I would like to show the course instructors solution as well as I think it is pretty smart.

Instructor Solution

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) {
    return false;
  }

  const lookup = {};

  // store all char frequencies in lookup obj
  for (let char of str1) {
    lookup[char] ? lookup[char] += 1 : lookup[char] = 1;
  }
  // loop through second str, if char is in the lookup object, subtract 1 from
  // that key, object should eventually be filled with keys of the value of 0
  // if it gets to that point BEFORE the looping over the STR is finished,
  // (lookup[char]) will return false
  for (let char of str2) {
    if (lookup[char]) {
      lookup[char] -= 1;
    } else {
      return false;
    }
  }

  return true;
}

I like this solution because it only uses two loops. Instead of making a second object to compare the first too, it uses the string, which is already there for us to use. I like the cleverness of the subtracting from the lookup object as a way to compare the characters in each string.

Multiple Pointers Problem Solving Pattern

Creating pointers or values that correspond to an index or position and move towards the beginning, end, or middle based on a certain condition. Very efficient for solving problems with minimal space complexity as well.

Example

Write a function called sumZero which accepts a sorted array of integers. The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist.

// Naive solution
function sumZero(arr){
  for (let i = 0; i < arr.length; i++) {
    let num = arr[i];
    for (let j = arr.length-1; j >= 0; j--) {
      // as long as the numbers are not pointing to the same index
      if (i < j) {
        if (num + arr[j] == 0) {
          return [num,arr[j]];
        }
      }
    }
  }
  return false;
}

This solution does work, but it also uses a nested loop, which creates an O(n2) time complexity.

Here is a solution with an O(n) complexity using the Multiple Pointers pattern.

function sumZero(arr) {
  let left = 0;
  let right = arr.length - 1;
  // as long as the pointer isnt referring to the same index
  // of the sum isnt 0, do this loop
  while (left < right) {
    let sum = arr[left] + arr[right]
    if (sum === 0) {
      return [arr[left],arr[right]];
    // if the sum is greater than 0, the integer on the right side was too large
    // decrease right by one and go with the next smaller number
    } else if (sum > 0) {
      right--;
    // if the sum is less than 0, the integer on the left side was too small
    // increase left by one and go with the next larger number
    } else {
      left++;
    }
  }
}

countUniqueValues Challenge

Implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.

My solution to this was to implement the above solution and fit it to the problem. Again, not the best way, but it did the job. I only used the multiple points because that is the section we are on, I felt like this could have been solved in the same way we solved the unique characters solution earlier.

function countUniqueValues(arr){
    // count only unique values in the array using 2 pointers
    let left = 0;
    let right = arr.length - 1;

    const uniqueValues = {};

    while (left < right) {
        if (!uniqueValues[arr[left]]) {
            uniqueValues[arr[left]] = 1;
        }
        if (!uniqueValues[arr[right]]) {
            uniqueValues[arr[right]] = 1;
        }
        left++;
        right--;
    }
    return Object.keys(uniqueValues).length
}

Instructor Solution This solution uses two pointers starting from the left. Moving forward from there. He updates the first pointer to be the same value as the second when they do not match, and moves forward from there. Once the second pointer reaches the end, the index of the first pointer will be equal to the unique number of values in the array.

function countUniqueValues(arr) {
  if (arr.length < 1) {return 0;}
  let i = 0;
  for (let j = 1; j < arr.length ; j++) {
    if (arr[i] !== arr[j]) {
      i++;
      arr[i] = arr[j]
    }
  }
  return i + 1;
}

This is such an interesting solution to me. To walk through it looks something like this.

// this is how the loop starts off, since these numbers are equal, j will increase and i will stay in place.
 i
[1,1,1,1,2,3,4,5,5,5,6,7]
   j

 i
[1,1,1,1,2,3,4,5,5,5,6,7]
     j

 i
[1,1,1,1,2,3,4,5,5,5,6,7]
       j

// now that j is different than i, we will move i one forward, and change the item
// at that index to match j
   i
[1,2,1,1,2,3,4,5,5,5,6,7]
         j

     i
[1,2,3,1,2,3,4,5,5,5,6,7]
           j

// as you can see, eventually j will reach the end, and where i+1 is at that point will be equal to the amount of unique values.
       i
[1,2,3,4,2,3,4,5,5,5,6,7]
             j

CLEVER! I really enjoy learning this stuff, going back to pure JS and solving these types of problems is what attracted me to the language in the first place. Time to move onto my Mongo Course.

Continuing with MongoDB

We will move onto MongoDB and learn about modeling and storing data in the DB as well as relationships the data should have. We will learn about Document Schemas and Data Types, Modeling Relations, and Schema Validation.

MongoDB does not enforce schemas. Documents do not have to use the same schema inside of one collection. This doesn’t mean that we cant use them however. They are important because they give our data a nice structure to work with.

The image below showcases the data types that we can use in Mongo.

Relations

How do we store related data in our database? Should we uses Nested/Embedded documents or References?

Using $lookup to Join

$lookup allows you to fetch two related documents and merge them together in one step. It would look like something similar to this.


// customers
{
  userName: 'jordan',
  favBooks: ['id1','id2']
}

// books
{
  _id: 'id1',
  name: 'Lord of the Rings'
}

{
  _id: 'id2',
  name: 'Version Control'
}

customers.aggregate([
  {
    $lookup: {
      from: 'books',
      localField: 'favBooks',
      foreignField: '_id',
      as: 'favBookData'
    }
  }
])

// it would return this

{
  userName: 'jordan',
  favBooks: ['id1','id2'],
  favBookData: [
    {
      _id: 'id1',
      name: 'Lord of the Rings'
    },
    {
      _id: 'id2',
      name: 'Version Control'
    }
  ]
}

Whew ok, not gonna lie. Since I feel like I have a fairly solid grasp of mongo, at least when using it within node with mongoose, this course is a little boring, BUT I am still going to go through it to have some more solid foundation.

Up next, my favorite, REACT.

React

To start off, I will be working on a challenge in the course. The challenge is laid out below:

Build an app that displays a deck of cards, one card at a time. When the page loads, send a request to https://deckofcardsapi.com/api/deck/new/shuffle to create a new deck. Store the Deck ID it gives you, so you can make further requests to retreive each card image. Add a button to your app that allows a user to draw a new card.

When a user clicks the button, send another request to the API, this time to https://deckofcardsapi.com/api/deck/${deck_id}/draw/. (make sure to use your actual deck ID). Use the data included in the response to display a new card image, and make sure to include an informative alt attribute.

Every time the user clicks, the app should display a new card until the deck is empty. Make sure to tell the user there are no cards left!

Here is my no styling solution to the app prompt. This was super easy.

import React, {Component} from 'react';
import axios from 'axios'

class DeckOfCards extends Component {
  constructor(props) {
    super(props)
    this.state = {
      deck_id: null,
      remaining: null,
      drawnCards:[]
    }
    this.drawCard = this.drawCard.bind(this)
  }

  async componentDidMount() {
    let {data} = await axios.get(`https://deckofcardsapi.com/api/deck/new/shuffle/`)
      console.log(data)
    this.setState({
      deck_id: data.deck_id,
      remaining: data.remaining
    })
  }

  async drawCard() {
    let {data} = await axios.get(`https://deckofcardsapi.com/api/deck/${this.state.deck_id}/draw/`)
    this.setState({
      ...this.state,
      drawnCards: [...this.state.drawnCards, data.cards[0]],
      remaining: data.remaining
    })
  }

  render() {

    let cards = this.state.drawnCards.map((card,idx) => {
      let style = {
        position: 'absolute',
        zIndex: idx,
        listStyle: 'none'
      }
      return <li style={style}><img src={card.image}></img></li>
    })

    return (
      <div className="DeckOfCards">
        <h1>Deck of Cards!</h1>
        <ul>
          {cards}
        </ul>
        {this.state.remaining !== 0
        ? <button onClick={this.drawCard}>Draw</button>
        : <p>No Card Remaining!</p>
        }
      </div>
    )
  }
}

export default DeckOfCards

The next exercise will be to design the following app, this should take a bit, but also seems pretty fun to build on.

Back to blog...