Forem: aohibbard

Lemonade Change

aohibbard — Sun, 29 Nov 2020 21:32:25 +0000

It has been a food-filled few days so let's massage the brain with an easy post: how to solve Leetcode #860 "Lemonade Change." In the problem, we are told that a lemonade costs $5, you the vendor have no change to start with, and buyers will pay with either a $5 bill, a $10 bill, or a $20 bill. Given an array of called bills containing only 5, 10, or 20, determine if you can provide the appropriate change at every transaction. If so, return true, if not, return false.

This problem is a Leetcode easy, and under the spell of too many carbs, seemed difficult at first, but honestly it's not much harder than fizzbuzz.

To start, let's deal with our edge cases. If we receive an empty array or the first value of the array is NOT equal to 5, we have to return false. In the latter case, we know that the seller does not have any change to start with, so any array that does not begin with 5 assumes change will be provided. That's impossible. So let's write that.

var lemonadeChange = function(bills) {
  if (!bills.length || bills[0] !== 5) return false
}

The next step is to figure out how to approach the problem. The approach requires us to iterate over the whole array and to compare values based on existing change. Effectively, we need to create a change drawer. I opted to do this as an object, where the keys correspond to the dollar amount of a bill and the values to the quantity of those bills: let change = {'5': 0, '10': 0, '20': 0} (remember that integers cannot be used as keys in JavaScript).

The next step is to consider all of the different scenarios and operate on our object accordingly. The function will iterate over the array, testing the input value against a series of if/else statements, each based on the value of the input.

The first one is easy. If the array value is 5, there is no need to produce change, so we simply increment the '5' key in our change object. (NB: I did not do this, but because any array that does not begin with 5 will return false, we could theoretically initiate the change object with '5' have a value of one, and begin iterating at array index 1 to save a smidgeon of time).

The second case requires us to address what happens if the array value is 10. In this case, we once again increment the appropriate value in the change object. But this time, we have to produce change. Given that there are only $5, $10, or $20 bills, we can only pay change with a $5 bill. If there is a $5 bill in the change object (that is, key 5 has a value greater than or equal to 1), we can produce change. So we have to decrement the value of the 5 key by one. If not, no change can be produced, so we should break the loop and return false.

The most complicated logic comes with a $20 bill. We start the same one, by increment the value of key '20' by one and then seeing if change can be produced. Change can be produced with a $10 and a $5 or three $5 bills. Because $5 bills are more necessary, we should check if there is a $10 and a $5 first. If so, decrement the corresponding keys by one. If not, see if there are three $5 bills. If so, decrement key 5 by three. If neither condition is true, once again break the loop and return false, because a situation has been produced where no change is available.

By inserting these return false statements throughout the loop, we have addressed any situation where it is impossible to produce correct change. That means, if the loop successfully completes by iterating over all values in bills, the return value must be true.

Check out the full function below. It's a lot of logic but all in all, pretty simple.

var lemonadeChange = function(bills) {
  if (!bills.length || bills[0] !== 5) return false
  let change = {'5': 0, '10': 0, '20': 0}
  for(let i = 0; i < bills.length; i++){
      if(bills[i] === 5){
          change['5']++
      } else if (bills[i] === 10){
          change['10']++
          if (change['5'] === 0){
              return false
          } else {
              change['5']--
          }
      } else {
          change['20']++
          if (change['10'] >= 1 && change['5'] >= 1){
              change['10']--
              change['5']--
          } else if (change['5'] >= 3){
              change['5'] -= 3
          } else {
              return false
          }
      }
  }
  return true
};

Manual Implementation of JSONPath

aohibbard — Mon, 16 Nov 2020 11:55:18 +0000

A few weeks ago, I was given a live coding challenge to write a function that would parse a pathway of a JSON object. The question was effectively a manual implementation of JSONPath. For the purposes of this post, we will work with this object:

json_obj = {
    “hello”: [
        “world”,
        {“hello”: true},
        [3, 4, 5]
    ],
    “world”: {
        “from”: “Your Friend”
    }
}

The idea is that if fed the json_obj and a path, one would return the following results:

get_json_value_by_path("$.hello[1].hello", json_obj) // true
get_json_value_by_path("$.world.from", json_obj) // “Your Friend”
get_json_value_by_path("$.hello[2][0]", json_obj) // 3
get_json_value_by_path("$.does.not[3].exist", json_obj) // “Key does not exist”

I stumbled performing this in JavaScript, coming up with a very clumsy answer that relied on a lot of Googled Regex. But as it turns out, it is very easy to do in Python.

In working with the object in Python, we need to ensure that we are treating the object as a JSON object. This means calling on Python’s native json capabilities by writing import JSON at the top of the file. We then call on json.dumps to serialize the object into JSON format and then json.loads to support reading the JSON object in Python (this is similar to JSON.stringify and JSON.parse in JavaScript).

For me, the challenge here is working with the index values in bracket. For the second example, which should return “Your Friend,” the function is just a matter of splitting and parsing the file path string and interpolating them in a for loop. To do this, we would call on our JSON function as above, and then split the path name string and the period, pulling out the terms we need. Because all of the path names begin with a dollar sign, we can ignore the value at index zero and then interpolate the path keys as needed. This would look like:

def get_json_value_by_path(path, obj):
  json_dump = json.dumps(json_obj)
  data = json.loads(json_dump)
  paths = path.split('.')
  for i in range(1, len(paths)):
    data = data[str(paths[i])]
  print(data)

Unfortunately, the index values are there. I’m fairly certain this is not the best solution, but my approach was to inspect every path value in the loop to see if contains numbers. To do this, we use the findall function in python and check each string to see if it includes any numbers. If it does, these numbers are placed in a list called res, and the existence of values in res determines how we proceed. If it has a length of zero, we proceed as above, if not, we iterate over each of the indices in res. I have also called upon a regex function to check if a value is a digit, which requires importing another library: re. Note that I have also introduced a value called key in this loop. We have to work with the root string in the path first before we attend to index values.

import re

def get_json_value_by_path(path, obj):
  json_dump = json.dumps(json_obj)
  data = json.loads(json_dump)
  paths = path.split('.')
  for i in range(1, len(paths)):
    res = re.findall(r'\d+', paths[i])
    #if there are index values in the string
    if len(res) > 0:
      key = paths[i].split('[')[0]
      data = data[str(key)]
      for i in range(len(res)):
        idx = int(res[i])
        data = data[idx]
    else: 
      data = data[str(paths[i])]
  print(data)

The scalability of this solution is not great as the regex function assumes that all index values will be standalone, single value integers. We could easily modify this if needed by finding all numbers between brackets say, but it works for our test cases.

Finally, we need to account for a situation where we are fed a path where something does not exist. This requires a simple if statement. Because the JSON data is treated as a dictionary, we can use the get function to see if the key exists. It it does not, we simply break the loop and return the statement “Key does not exist.”

In total, our function looks like this. Not the prettiest, but functional:

import re
import json 

def get_json_value_by_path(path, obj):
  json_dump = json.dumps(json_obj)
  data = json.loads(json_dump)
  paths = path.split('.')
  for i in range(1, len(paths)):
    res = re.findall(r'\d+', paths[i])
    if len(res) > 0:
      key = paths[i].split('[')[0]
      if not data.get(str(key)):
        return "Key does not exist"
      data = data[str(key)]
      for i in range(len(res)):
        idx = int(res[i])
        data = data[idx]
    else: 
      if not data.get(str(paths[i])):
        return "Key does not exist"
      data = data[str(paths[i])]
  print(data)

Changing Your AWS Default Profile

aohibbard — Mon, 09 Nov 2020 14:20:04 +0000

As I've been working with AWS recently, I find myself struggling to do really simple things. Newbie errors. I recently documented my struggles with configuring an Amplify backend and wanted to return to the subject to reveal another issue that I had: changing the default profile.

Before beginning, I wanted to say a bit about what Amplify is. According to AWS's description:

AWS Amplify is a set of products and tools that enables mobile and front-end web developers to build and deploy secure, scalable full stack applications, powered by AWS. With Amplify, you can configure app backends in minutes, connect them to your app in just a few lines of code, and deploy static web apps in three steps.
In short, Amplify is a quick way to set up a backend. I'm using it in a shared project to run the backend of a React application.

Now my struggle: I was running a shell script in the application to create an account in the backend of the web application, and the script required that I call on my AWS profile alias. When you configure an AWS account the first time, the profile name will default to "default." For some reason, the script did not like the name 'default', even when assigned to an environment variable.

AWS does not have the clearest documentation for how to change the name of a profile, but it turns out to be pretty easy. If you have configured your settings correctly, you should have two local files that contain your account settings such as API key: ~/.aws/config and ~/.aws/credentials. If you're in an editor like VS Code, these might not be visible so just run open before the path and you'll get something like a .rtf with your AWS configuration. You'll notice that in both files, account settings are listed and they having a header set in brackets, which contains the profile name. For the profile named default, simply delete the word default and assign the name you want. It must match in the two files. Save the two files. And that's it.

If you want to preserve this account as the default one, just remember the alias you have given the profile run the command export AWS_PROFILE=<my_profile> (with acting as the name of your profile). You can perform this step whenever you want to change the default AWS profile. And that it. Three simple steps to change the name of your AWS default profile.

Setting Up a Basic Unit Test with RSpec

aohibbard — Tue, 03 Nov 2020 16:27:54 +0000

I have not spent a lot of time writing code in Ruby recently, but this weekend had the opportunity to develop a very simple trivia application in vanilla Ruby: two classes, a few dependencies, not much else. While this was easy enough, I wanted to add some tests to one of my classes, and I need a refresher. This post details my reintroduction to RSpec.

As background, the application took a JSON file that contained many questions, each an object with three keys: a question (value: a string), an answer (value: a string), and incorrect (value: an array of strings). I wrote a Clue class (not the most descriptive name given it includes answers, but so it goes sometimes) with one function to parse the JSON file. This looked like:

class Clue

    attr_accessor :question, :answer, :wrong_answers, :all_answers
    @@all = [] #an array of all the clues

    def initialize()
        @@all << self
    end

    def self.all 
        @@all
    end 

    def self.get_trivia
        json = JSON.parse(File.read("file_name.json"))
        json.each do |res| 
            clue = Clue.new 
            clue.question = res['question']
            clue.answer = res['correct']
            clue.wrong_answers = res['incorrect']
            clue.all_answers = [res['correct']].concat(res['incorrect'])
        end
    end 

end

Having once upon a not-so-distant time spent a lot of time interacting with RSpect unit tests, I decided to use RSpec rather than Ruby'y standard library test-unit.

To get started with RSpec, you need to ensure that you have included the gem 'rspec' in your Gemfile and have that installed correctly, then in your command line from the root direct run rspec --init. This will create a directory 'spec' with the file 'spec-helper.br' as well as a root file '.rspec'.

I next created a file under spec called 'clue_test.rb' which is where all of the work happens. It's easy to forget, but you need to remember to import the class you are working with in the test file, in this case: require 'clue'. The next step was to test the different attributes of the Clue class. With testing, it is best to make the tests small and simple (an easy thing to do in a simple application).

To start, I wanted to create a test Clue object that would be the basis for the tests. RSpec relies on the verb describe for a lot of its tests, and as my tests were describing the clue class, that's what we began with: describe Clue do. Before any tests run, a new clue was created, fed with data from a Hash. There could be other ways of doing this, but I liked simulating the logic of the JSON parsing function.

require 'clue'

describe Clue do 
    before do 
        new_clue = Hash["question" => "How many folds does a chef's hat have?", "answer" => 100, "wrong_answers" => [90, 115, 50]]
        @first_clue = Clue.new
        @first_clue.question = new_clue['question']
        @first_clue.answer = new_clue['answer'] 
        @first_clue.wrong_answers = new_clue['wrong_answers']
        @first_clue.all_answers = [new_clue['answer']].concat(new_clue['wrong_answers'])
    end 

end

The next step was to write a test. Go one by one. I wanted to start with some very simple. RSpec works by outlining a condition and then describing how the condition should behave. Tests generally look like something like:

describe "thing" do 
   it "behaves like this" do 
       expect(variable).to eq(other thing)
    end
end

For the first test, I wanted to simply check if the wrong_answers attribute of the newly instantiated Clue was an array. This looked:

    describe "wrong answers" do 
        it "includes an array of wrong answers" do 
            expect(@first_clue.wrong_answers.class).to eq(Array)
        end 
    end

In the initial writing of my tests, I had actually passed the wrong_answers to the Clue as a hash. It's a small but significant error, and one that really helps you to get to know your code much better, regardless of how simple you think it.

There are a whole host of things you can beyond checking equivalence in RSpec. One simple test I wrote checked if the .all_answers attribute include something from the .wrong_answers array:

    describe "all answers" do 
        it "includes wrong answers" do 
            expect(@first_clue.all_answers).to include(@first_clue.wrong_answers[0])
        end 
    end

In the end, I wrote a very simple test suite, but one that got me much closer to my code. I encourage you to check out the documentation and always test your code.

Anagram Checker

aohibbard — Fri, 30 Oct 2020 21:10:39 +0000

I was recently tasked in a technical interview to implement a function that iterated through an array of strings and checked if each string was an anagram of a string before it, returning an alphabetically sorted array of the results. The caveat was that certain features such as reverse() were not allowed.

So given the array [‘drag’, ‘grad’, ‘’dad’, ‘banana’, ‘flimsy’, ‘add’] the function would output ['banana', 'dad', ‘drag’, ‘flimsy’]. I.e. Because 'grad' is an anagram of 'drag', it is removed from the array.

My first approach was to determine how to detect an anagram. Typically I would do the sort of word1.split('').sort() === word2.split('').sort, but that was not allowed. Instead, I implemented a function that first checked that the lengths of the two strings. Assuming they were of equal length, the function iterated through one of the strings, comparing it to the other, breaking if there is a letter that does not match up.

function isAnagram(word1, word2){
    if (word1.length !== word2.length) return false;
    word1 = word1.toLowerCase().split('')
    word2 = word2.toLowerCase().split('')
    for(let lttr of word1){
        // if letter in word1 is in word2, remove it from word2
        // if we never encounter a letter not in word2, 
        if (!word2.includes(lttr)){
            return false;
            break;
        } else {
            word2.splice(word2.indexOf(lttr), 1)
        }
    }
    return true
}

By splicing the word2 array, we ensure that the amount of letters is equal as well.

This function is a great start, but it is not going to work with the sample array we've been fed. Instead, I will call on this function inside of another one.

To begin, I wrote an if statement that examines the length of the array. We know that the the first string in the array will always be returned, because there is no string prior to it for it to be an anagram of. So if the array is empty or only includes only 1 string, the function will not continue and just return the array.

I chose to not modify the array in place and use the extra memory to create a solution array. By the logic explained above, we know that the first string will always be included in the solution, so the array is initialized with the first string in the array: let solution = [text[0]]. I then iterate over the subsequent array, calling on the isAnagram function to check if the subsequent strings are anagrams of any of the strings in the solution array. Note that the for loop starts with i = 1, not 0, because we have already checked text[0]. To do this, I filtered the solutions array against the current word in the for loop. If the word at text[i] is not an anagram, it is pushed into the solution array. (An alternate way of doing this would be to modify the array in place, checking isAnagram() only for words that have an index less than i.)

function arrayAnagramChecker(text) {
    if (text.length <= 1) return text;
    let solution = [text[0]]
    for(let i = 1; i < text.length; i++){
        if (!solution.filter(word => isAnagram(word, text[i])).length){
            solution.push(text[i])
        }
    }
}

This covers most of the work, but remember that the the results have to be returned in a sorted array, not in their original order. Again, normally I would just do a .sort or the slightly more laborious .sort((a, b) => a - b). This was not enabled so I to implemented a slightly more elaborate sort:

    solution.sort(function(a, b){
            if(a < b) { return -1; }
            if(a > b) { return 1; }
            return 0;
    })

Finally, our function:

function funWithAnagrams(text) {
    if (text.length <= 1) return text;
    let solution = [text[0]]
    for(let i = 1; i < text.length; i++){
        if (solution.filter(word => isAnagram(word, text[i])).length === 0){
            solution.push(text[i])
        }
    }
    solution.sort(function(a, b){
            if(a < b) { return -1; }
            if(a > b) { return 1; }
            return 0;
    })
    return solution
}

function isAnagram(word1, word2){
    if (word1.length !== word2.length) return false;
    word1 = word1.toLowerCase().split('')
    word2 = word2.toLowerCase().split('')
    for(let lttr of word1){
        // if letter in word1 is in word2, remove it from word2
        // if we never encounter a letter not in word2, 
        if (!word2.includes(lttr)){
            return false;
            break;
        } else {
            word2.splice(word2.indexOf(lttr), 1)
        }
    }
    return true
}

And, just for kicks, I rewrote the function in Python, although I utilized .sort there and also the .sorted() function in a lambda to avoid create a separate function.

def funWithAnagrams(text):
    if len(text) <= 1:
        return text
    solution = [text[0]]
    i = 1
    for i in range(len(text)):
        # if current word is not an anagram of list of solutions, add to solutions list
        anagrams = list(filter(lambda x : sorted(x) == sorted(text[i]), solution))
        if not anagrams:
            solution.append(text[i])
    solution.sort()
    return solution

Connecting to AWS Amplify

aohibbard — Sat, 24 Oct 2020 13:26:39 +0000

This week, I spent a lot of time trying to connect to databases. Or rather, I wasted a lot of time trying to connect to databases. An AWS Amplify application caused me quite a headache, so I wanted to provide a simple walkthrough to help troubleshoot some of the issues I was facing.

Prerequisites

To start, there are three packages that you will need get get things going: 1. @aws-amplify-cli; 2. @aws-amplify; 3. the most recent version of AWS CLI. You will also need an AWS account.

Getting Going

I was working with an existing Github repo, so I cloned that repo to my local machine and accessed a working branch. To configure access to the AWS resources, you will need to run amplify configure. This command requires you to log into your AWS account and configure the access permissions through an IAM account. When going through these steps, you will be prompted to set a region. It is essential that the AWS region you choose matches the region configured in the application. You can find this information in the repo's team-provider-info.json

You will also have to enter credentials for the IAM account that are produced in the AWS management console. These include an access key and a secret key. Take note of these in a secure location, though you can always produce a new one in the event that you lose it.

In theory, everything should be working from here and you can just run amplify init to connect things. When I ran amplify init, I hit the following error.

Initializing your environment: dev(node:22264) UnhandledPromiseRejectionWarning: InvalidAccessKeyId: The AWS Access Key Id you provided does not exist in our records.

This is one of those programming things where you want to beat your head against a wall. I just told you the access key, why do you have to lose it? I tried going through the amplify configure steps again, to no avail.

(An aside on amplify configure. The amplify configure command menu creates the impression you are always adding a new user, when in fact it is a way of updating a user (see this pull request for a more thorough discussion.)

In the prerequisites, I mentioned installing the AWS CLI tools. This allowed me to diagnosis and fix the problem. If you run aws configure, it will show you the last 4 characters of both the saved access key ID and secret access key, as well as the selected region. If any of this looks different from what you input aws configure, this is the place to change it. I updated the values here, and voila. I ran amplify init, and things were working.

TL;DR

In summary, ensure you have the prerequisites. Run amplify configure, then amplify init and then run your app. Run aws configure if things are not going right and then check your credentials.

Getting Into TypeScript: What is a Dynamically Typed Language?

aohibbard — Fri, 16 Oct 2020 14:06:56 +0000

Take a look at job postings out there, and you'll see a lot of mentions of TypeScript. It doesn't take long to glean that TypeScript exists in relation to JavaScript, but what exactly is that relation?

TypeScript was developed at Microsoft and first released in 2012. TypeScript is sort of a superset of JavaScript, adding a type system on top of JavaScript. This description from the TypeScript Github repository is not a bad starting point:

TypeScript is a language for application-scale JavaScript. TypeScript adds optional types to JavaScript that support tools for large-scale JavaScript applications for any browser, for any host, on any OS. TypeScript compiles to readable, standards-based JavaScript.

To get at the core difference, it is important to understand what a dynamically typed language is, and what a statically typed language is. Dynamically typed languages include Perl, Ruby, Python, PHP, JavaScript—big languages in full-stack web development and the core languages we see being taught in bootcamps. Statically typed languages include C, C++, Java, Rust, Go, Scala.

Statically typed languages either work through type inference or force you to declare the type of a variable (e.g. string, integer) in writing the code so it is known at compilation. Dynamically typed languages do not require this. Oracle identifies two key differences

First, dynamically-typed languages perform type checking at runtime, while statically typed languages perform type checking at compile time. This means that scripts written in dynamically-typed languages...can compile even if they contain errors that will prevent the script from running properly (if at all). If a script written in a statically-typed language (such as Java) contains errors, it will fail to compile until the errors have been fixed.

Second, statically-typed languages require you to declare the data types of your variables before you use them, while dynamically-typed languages do not.

Dynamically typed languages offer a bit more speed for the coder, sparing you the step of type declaration. As mentioned above, your code will compile without errors in a dynamically typed language. It's the sort of logic that allows us to do get something like "1" + 1 = "11" or "alert" + [1,2] = "alert1,2"in JavaScript. Although we can sometimes use this to our advantage, it can also result in errors.

TypeScript then sits on top of JavaScript and allows a bit more control over things. Consider this example from the TypeScript documentation.

function greeter(person: string) {
  return "Hello, " + person;
}

let user = [0, 1, 2];

document.body.textContent = greeter(user);
Argument of type 'number[]' is not assignable to parameter of type 'string'.

What we see is by declaring the type of the person argument, anything passed in that is not a string will yield an error. It's a small addition but a huge amount of control added to your programming.

I'm a big fan of knowing the history of things, and this video of Jonathan Turner talking about TypeScript in 2013 is a great resource and starting place.

Counting Array of Arrays

aohibbard — Fri, 09 Oct 2020 15:55:51 +0000

A few weeks ago in a technical interview, I was given a challenge that involved iterating through an arrays. I do not have the exact wording, but it was something akin, to given a family tree in the format of an array of arrays, return all the nodes with only one parent or no parents. To visualize the data, I was shown this:

1   2    4 
 \ /   / | \
  3   5  8  9
   \ / \     \
    6   7     11

From this data display, we can deduce the nodes with only one parent are [5, 7, 8, 9, 11] and the nodes with no parent are [1, 2, 4]. While looking at the data in this format cause me to think "TREE!", this was not the case as this information was given as an array of arrays, with each sub-array including two values, the index at 0 referring to the parent and at index 1 referring to the child. Practically, this looked like:

const parentChildPairs = [
    [1, 3], [2, 3], [3, 6], [5, 6],
    [5, 7], [4, 5], [4, 8], [4, 9], [9, 11]
  ];

I came up with, what I think is, a rather solid linear run-time solution. This involved creating two objects, one to count the number of times parents appear and the other to count the number of times that children appear: let parentsObj = {} and let childObj = {}.

The next step was to iterate over the entire collection and count where numbers appear. If a number appears in a sub-array at index 0, it should be counted as a parent; if it appears in a sub-array at index 1, it should be counted in the child object. Practically, this looks like:

  function findNodesWithZeroAndOneParents(arr){
    let parentsObj = {}
    let childObj = {}
    for (const subArr of arr){
      //count parents
      if (!parentsObj[subArr[0]]){
        parentsObj[subArr[0]] = 1
      } else {
        parentsObj[subArr[0]] += 1
      }
      //count children
      if (!childObj[subArr[1]]){
        childObj[subArr[1]] = 1
      } else {
        childObj[subArr[1]] += 1
      }
    }

The next step is to go through each collection and take out the data that we need: children who have no parents, and children who have only one parent. In both cases, it is extremely helpful to use JavaScript's [Object.keys() method](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/keys), yielding an array of the object keys that can be filtered to get the results that we need.

To find the individuals with no parent, we need to compare the individuals in our parentsObj with those in the childObj. Any key that appears in the parentsObj but no the childObj would be included in the array of individuals with no parent. I chose to do this by finding the keys of the parentObj and then filtering those in relation to the keys of the childObj:

Object.keys(parentsObj).filter(key => !Object.keys(childObj).includes(key))

To find children with only parent requires another Object.keys method but a slightly easier: take all of the keys from the childObj and filter them, finding any key whose value is equal to one (that is, any child who only appears one time at sub-array index one).

Object.keys(childObj).filter(key => childObj[key] === 1)

Once we account for an edge case in which the array fed into the function is empty, we have an answer.

  function findNodesWithZeroAndOneParents(arr){
    if (arr.length === 0) return 0;
    let parentsObj = {}
    let childObj = {}
    for (const subArr of arr){
      if (!parentsObj[subArr[0]]){
        parentsObj[subArr[0]] = 1
      } else {
        parentsObj[subArr[0]] += 1
      }
      if (!childObj[subArr[1]]){
        childObj[subArr[1]] = 1
      } else {
        childObj[subArr[1]] += 1
      }
    }
    let noParents = Object.keys(parentsObj).filter(key => !Object.keys(childObj).includes(key))
    let oneParent = Object.keys(childObj).filter(key => childObj[key] === 1)
    return {"No Parents": noParents, "One Parent": oneParent}
  }

NB: Because JavaScript does not allow return on multiple variables, I returned the answer as an object, with the keys referring to the different information needed and their values referring to the appropriate arrays.

What exactly is JSON?

aohibbard — Fri, 02 Oct 2020 14:15:48 +0000

During a recent interview, I was tasked with working with a JSON object in the language of my choice. While I'll skip over the the particularities of the situation, I realized that I had some uncertainty over what exactly JSON is. I've worked with JSON extensively in JavaScript concepts, and I've utilized methods like JSON.parse() and JSON.stringify(), knowing that these are valuable in managing the data and sending it between the front and back end. But there was a conceptual foundation missing from my practical usage. Let's start with a an official definition from Mozilla:

JavaScript Object Notation (JSON) is a standard text-based format for representing structured data based on JavaScript object syntax. It is commonly used for transmitting data in web applications (e.g., sending some data from the server to the client, so it can be displayed on a web page, or vice versa).

If we start with just the name, it is the second half that really stands out. JSON is an object notation, or as Mozilla says, a "text-based format" for representing data. This of course makes sense. If we are utilizing a back-end such as Rails or Django, it does not make much sense that our data would be circulating as a JavaScript object.

So JSON is in fact a text-based notation (think XML, YAML) that format data into a readable object format for JavaScript. This is why it is import to run JSON.parse() when data enters the a JavaScript front end: because it is coming through as a string, albeit one that is formatted as a JavaScript object. If we were just sending a really long string this would be, well, a pain. But of course.

Conventional wisdom suggests that, with the rise of JavaScript, JSON took the throne from XML as a preferred way to send data in APIs given its easier readability and accessibility as a JavaScript object. Indeed, working with JSON is just as easy as working with JavaScript objects because (if parsed), JSON is an JavaScript object. Most histories date JSON back to 1999 or 2000 and it began to pick up usage in the aughts, but really grew in the last decade particularly when it became an ECMA international standard in 2013. (For some context on JSON vs. XML, this post has a nice graph, with some highlights being that JSON is easier to read and parse, though has some more security vulnerability.)

What about generating JSON outside of JavaScript? The standardization of JSON has made it very easy to work with and many languages have native support for working with JSON. In Python, you simply need to import json and there are plenty of functions available to parse JSON data and to format data into JSON. There are also libraries like Jackson and GSON in Java. And frameworks have plenty of support too: Rails, for example, has the Active Model Serializer, although I'm a big fan of Fast_JSON API as it offers a faster performance.

JSON is not a difficult concept to understand. But it is always a good reminder to think through the basic concepts of what you are working with.

JavaScript: Map & Set

aohibbard — Fri, 25 Sep 2020 15:18:05 +0000

While hunting for my first job as a software engineer, I have spent a LOT of time on LeetCode and HackerRank. Everyone has a different strategy for how they approach this studying. At some point after I’ve solved a problem, I like to look at how other individuals have approached the same situation. And from doing this, I’ve picked up two very valuable assets in JavaScript: map and set.

SET

I find myself using Set all the time. It is an exceptional tool for removing duplicates in an array. Imagine you have let arr = [1, 2, 3, 4, 1]. Run [...new Set(arr)], and you will get [1, 2, 3, 4]. Great! But I know this is a limited use of Set so I wanted to dig a bit deeper.

What is Set? If we take a set like the one above and run typeof() on it, we see that a set is a type of object in JavaScript. It is worth remembering there are two structural types in JavaScript: objects and functions. Within the object family tree, we find arrays, maps, sets as well as WeakSets and WeakMaps.

So Set is a type of object. As Mozilla describes: “Set objects are collections of values. You can iterate through the elements of a set in insertion order. A value in the Set may only occur once; it is unique in the Set's collection.” They key to set is the condition of uniqueness.

It is also worth noting that Set allows us to iterate over it. So we can call forEach on a Set. Several other methods also allow iteration: Set.prototype.keys() and Set.prototype.values() create iterator objects that return the keys or values of the set. If we had something like let mySet = new Set([1, 2, 3, 4, 4, 4]), mySet would be of size 4 and would equal {1, 2, 3, 4}. What is important to note about this is that if we wanted to to find the values or keys of this set, the result would look the same, because in this case, the values and keys are effectively the same. Set store objects and arrays inside of it as well, creating nesting. If we wanted to add let arr = [1, 2, 3, 4, 4] to mySet by performing mySet.add(arr), mySet would take on size five and look like {1, 2, 3, 4, arr: [1, 2, 3, 4, 4]}. It is noteworthy here that set allows non-unique values inside the this array because it is not looking inside the value stored.

MAP

Map turns out to be quite similar, but does not uphold the uniqueness factor. Like set, a Map does not use or contain keys by default, but if keys are added, the can be any value (e.g. primitive data types, functions, objects). Similarly, Map allows out to iterate over, and values are placed in the sequence in which they are added (or set). There’s a StackOverflow post containing an older explanation of the differences between objects and Maps that is helpful.

Objects are similar to Maps in that both let you set keys to values, retrieve those values, delete keys, and detect whether something is stored at a key. Because of this, Objects have been used as Maps historically; however, there are important differences between Objects and Maps that make using a Map better.
An Object has a prototype, so there are default keys in the map. However, this can be bypassed using map = Object.create(null). The keys of an Object are Strings, where they can be any value for a Map. You can get the size of a Map easily while you have to manually keep track of size for an Object.
Use maps over objects when keys are unknown until run time, and when all keys are the same type and all values are the same type.
Use objects when there is logic that operates on individual elements.

With both Map and Set, there are a lot of properties and methods
Tania Rascia has a great post outlining some of these, but essential ones are set, delete, get, has, clear, and size for Map. All considered, Set and Map are essential tools in modern JavaScript.

JS String Encryption Algorithm

aohibbard — Tue, 15 Sep 2020 11:12:44 +0000

This week, I was given a technical challenge that involved creating an encryption for a string. I’m pulling from memory, but the the task was roughly as follows: given a string, an r value, and a c value, encrypt the string so that it is split into a grid measuring r characters across and c characters down. Then, transform the string so that it reads top to bottom. The string will always be a length measuring r * c, and spaces count toward the string.

I was given a few test cases for this algorithm, which I’ve lost, but I’ve created my own for the purposes of this demo. Let’s work with the very convenient (and broken) string I gave myself: "This message is 25 charac" and r and c values both equal to 5.

According to the instructions, we would want to transform this string to look something like:

“This
messa
ge is
25 c
harac”

This should then give us the following string:

"Tmg hhee2ais 5rssi a ascc"

My approach to this was sound, but the final code was clumsy. So I want to walk you through how I approached it and then refactored it.

Following the instructions, I thought the best approach was to manipulate the string into a matrix measuring r rows and c columns, and the transform that matrix into a string, moving down column by column.

My first steps were to make a function with three arguments (duh) function encrypString(message, r, c) declare a matrix let matrix = [] and then to split the string into an array let msgArr = message.split(‘’). Easy enough

The next step was to populate the array. To do this, I opted for the creation of a for loop inside a while loop. With each iteration of the for loop, a new character was added to an empty array, which would stop when the array achieves a length of c - 1 — that is, the end column of the matrix given by the function (in this case 5). When the for loops completes, this new subarray is pushed into the matrix. This loop operates destructively on the msgArr variable, running until the array is empty.

  while(msgArr.length > 0){
    let newArr = [];
    for(let i = 0; i < c; i++){
      let newChar = msgArr.splice(0, 1)
      newArr.push(newChar)
    }
    matrix.push(newArr.flat())
  }

Admittedly, this is not the most beautiful solution. We’ll come back to a better alternative later that is less clunky. But for the time being, this produces the matrix that we need.

In my handling, the next step was to create an empty string which will be used to produced a return value (our answer) (let str = ‘’)and then manipulate the array by columns so that we can have our encrypted string. I chose the very clunky way of running a for loop inside of a for loop, once again manipulating the string one character at a time.

  for (let i = 0; i < c; i++){
    for (let j = 0; j < r; j++){
      str += matrix[j][i]
    }
  }

I’ll note the importance thing here is how the i and j values are set. The outer for loop runs according to the c value — that is the column — and the inner loop runs according to the row size (r). Every time the inner loop completes, this means we have emptied the nth column of every row, and then can move onto the next one. This does the work that we need it to and helps us arrive, but it’s not the most beautiful.

Having completed this text, I knew I could do better. These loops take too much time. Let’s look first at our initial loop to create the matrix using a while loop inside a for loop.

I realized two things going into this. First, I did not need to take up additional memory space by saving my original string under a new variable. I could simply declare message = message.split(‘’). Goodbye msgArr variable. Second, I did not abandon a loop entirely, but I did find a way to form the matrix one row at a time rather than one character at time by employing splice (still destructively manipulating the array).

  for(let i = 0; i < c; i++){
      matrix.push(message.splice(0, c))
  }

What is happening here is the message array is spliced each time from its beginning to c characters, destructively manipulating the message array and producing a new array of length c, which is then pushed to our matrix. Additionally, because splice produces an array, there is no need to declare an empty array with each loop. This allows the loop to run only c times, rather than once per character plus once per row (in our example 25 times for the string in the for loop, plus 5 times for the while loop. That would get long fast!).

This is good progress. But we can do better still. Once again, we have a double for loop to manipulate our string. This is not necessary. A single loop can accomplish the same goal. Rather than manipulate the array one character at a time, we can go one column at a time using destructing and the map function.

let encoded = []
while (matrix.length > 0){
    encoded.push(...matrix.map(subArr => subArr.shift()))
}

The restructuring allows us to pass in the matrix, and then map new arrays from each of its subarrays. By calling shift, we destructively manipulate the array, pulling the first value from each subarray. In total, this gives us an entire column of the matrix with each loop. What we achieved with two for loops that run character by character now run column by column. Not bad!

I’ll note that instead of creating an empty string, I’ve chosen to push these subarrays to an empty array, which requires calling .join(‘’) in our return value. I think join could be called on the mapped arrays as well and we could just push to the string as we did originally, str += ...

Let's compare, starting with our old version:

function encryptString(message, r, c){
  let matrix = []
  let msgArr = message.split('')
  while(msgArr.length > 0){
    let newArr = [];
    for(let i = 0; i < c; i++){
      let newChar = msgArr.splice(0, 1)
      newArr.push(newChar)
    }
    matrix.push(newArr.flat())
  }
  message = message.split('')
  for(let i = 0; i < c; i++){
      let newArr = []
      newArr.push(message.splice(0, c))
      matrix.push(newArr)
  }
  let str = ''
  for (let i = 0; i < c; i++){
    for (let j = 0; j < r; j++){
      str += matrix[j][i]
    }
  }
  console.log(str)
  return str
}

The new version:

function encryptString(message, r, c){
  let matrix = []
  message = message.split('')
  for(let i = 0; i < c; i++){
      matrix.push(message.splice(0, c))
  }
  let word = []
  while(matrix[0].length > 0){
    word.push(...matrix.map(subArr => subArr.shift()))
  }
  return word.join('')
}

This drastically cuts down the length of the function and the run time, and I think ends up being a lot more readable too. Not bad! If only I could have done this in the live coding exercise.

UPDATE 21 SEPTEMBER

Always trying to improve, I've stayed looking at this algorithm and realized that, with a little pattern recognition, there would probably be a better way to perform the string encryption. And I realized that we can effectively disregard the c variable and simply collect the values row by row. Imagine r = 5. We know the string will be a multiple of 5, so we can just collect every fifth value to form the first part of the string. These would be the values of column[0]. We need to append the second part of the string (this would have been column[1]), which would be every string at index of r - 1. With the addition of a counter and a while loop, this logic becomes a lot easier to track.

This logic could be kept inside a for loop, checking every index value or we can just implement this by filtering the string and checking if the index of the specific character divided by r has a remainder equal to the column it would be in. With x corresponding to the column number, this looks like: message.indexOf(char) % r === x. You can see this all at work in a much more efficient function below:

function encryptString(message, r, c){
  message = message.split('')
  let newStr = ''
  let x = 0
  while(x < r){
    // for every turn of the loop on x, add the character at the value r - x (x corresponding to the rows)
    newStr += message.filter(char => message.indexOf(char) % r === x).join('')
    x++
  }
  return newStr
}

Transactions in MongoDB

aohibbard — Fri, 11 Sep 2020 16:39:59 +0000

I’ve recently been building a web app with Node and Express and decided to go full MERN stack and integrate MongoDB—or more accurately, I’m working with mongoose, the object modeling tool for MongoDB. I’ve spent most of my time working with SQL databases (PostgreSQL especially) and there are a lot of great posts out in the world that chart the difference between SQL and NoSQL databases.

One of the processes I had taken for granted in a SQL context is transactions. In the most basic context, a transaction involves the propagation of one or more changes to a database. Order matters in transactions. Consider an event where you have a value A, value B, and value C. Value A needs to deduct something from value B so that value C can deduct something from value A. Assume value A is 10, value B is 20, and value C is 100, and the value deducted is 15. If C deducts from A before A can deduct from B, that means A will have a negative value at some point. In this benign hypothetical, this is fine. But imagine we are dealing with a bank: A could incur overdraft penalties. In the real world, this could get sticky. If we were dealing with inventories in eCommerce, people could be buying things they thing are available but actually are not. Order matters!

TutorialsPoint has a helpful breakdown of the properties of transactions, which can be remembered through the acronym ACID.

• Atomicity − ensures that all operations within the work unit are > completed successfully. Otherwise, the transaction is aborted at
the point of failure and all the previous operations are rolled > back to their former state. 
• Consistency − ensures that the database properly changes states
upon a successfully committed transaction. 
• Isolation − enables transactions to operate independently of and transparent to each other. 
• Durability − ensures that the result or effect of a committed
transaction persists in case of a system failure. 

Historically, ACID transactions were not a part of MongoDB. This had to do with the the way NoSQL databases were used, but their growing popularity changed that. See Laura Schaefer’s blog post from January 2019 on the subject:

They explained how, for non-relational databases like MongoDB,
multi-document ACID transactions have historically been a bit of
an odd case. With a document data model, you naturally prefer to
keep changes localized to the document you are working on, so the
single operation ACID compliance was often enough.

With MongoDB 4.0, it became possible to execute ACID transactions, but that did not mean it was impossible before. The package Fawn made it possible to execute ACID transactions in MongoDb.

The development of ACID transactions in MongoDB was motivated, in part, by the long shadow relational databases with table models have cast over the history of databases. As Mat Keet and Alyson Cabral wrote in June of this year:

With subdocuments and arrays, documents allow related data to be
modeled in a single, rich and natural data structure, rather than > spread across separate, related tables composed of flat rows and > columns. As a result, MongoDB’s existing single document atomicity > guarantees can meet the data integrity needs of most applications. > In fact, when leveraging the richness and power of the document > > model, we estimate 80%-90% of applications don’t need multi- document transactions at all.
However, some developers and DBAs have been conditioned by 40
years of relational data modeling to assume multi-document
transactions are a requirement for any database, irrespective of
the data model they are built upon. Some are concerned that while
multi-document transactions aren’t needed by their apps today, they > might be in the future. And for some workloads, support for ACID > transactions across multiple documents is required.
As a result, the addition of multi-document transactions makes it > easier than ever for developers to address a complete range of use > cases on MongoDB. For some, simply knowing that they are available > will assure them that they can evolve their application as needed, > and the database will support them.

In Node, ACID transactions require the creation of helper functions that rely on async/await patterns in JavaScript to ensure that not only are transactions completely successfully but are completed in the correct order. For more on the topic, I recommend this post on MongoDB's blog.