DEV Community: Amy Shackles

SingleNumber

Amy Shackles — Fri, 08 Jan 2021 01:24:17 +0000

Problem Statement

Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without extra memory?

Thought Process

My initial conclusion was that no, you couldn’t. Since there’s not a range for the possible numbers in the array and the array isn’t already sorted, you can solve in linear time if you used an object to store counts, but you need that extra storage or sorting is O(n log n).

But see, I forgot about XOR (^). For those of you who don’t play with bits, exclusive or takes two binary numbers and for pair where one number has the bit flipped and the other doesn’t, the resulting number has the bit flipped.

  01101
^ 10110
= 11011

So if you have a number and XOR it by 0, you get the number. If you have a number and XOR it by itself, you get 0.

Now, that’s helpful, but why would you care about XOR for this problem?

Let’s run through an example:

const input = [4,1,1,2,2,4,5,1,2,1,2]
let num = input[0];

for (let i = 1; i < input.length; i++) {
    num ^= input[i];
    console.log(num);
}

/*
5
4
6
4
0
5
4
6
7
5
*/

Explanation/Solution

Because all of the values that appear twice will eventually cancel themselves out, you’re left with that one solitary element that has no partner. No extra storage necessary. Linear time.

  100 // 4
^ 001 // 1
= 101 // 5
^ 001 // 1
= 100 // 4
^ 010 // 2
= 110 // 6
^ 010 // 2
= 100 // 4
^ 100 // 4
= 000 // 0
^ 101 // 5
= 101 // 5
^ 001 // 1
= 100 // 4
^ 010 // 2
= 110 // 6
^ 001 // 1
= 111 // 7
^ 010 // 2
= 101 // 5

Since we're working with an array of numbers, we can make use of an array method to accomplish the task in lieu of a for loop.

function singleNumber(nums) {
    return nums.reduce((a, b) => a ^ b)
}

Problem taken from LeetCode

Why Is {} > [] ?

Amy Shackles — Tue, 24 Nov 2020 21:34:40 +0000

TLDR version

Relational Comparisons

In JavaScript, the result of a relational comparison is determined by the Abstract Relational Comparison algorithm. The algorithm converts both sides of a comparison to primitive values and then returns the result of the comparison between those two primitive values.

ToPrimitive¹

The Abstract Relational Comparison algorithm calls ToPrimitive twice, once for each operand, passing 'number' as the second argument. This tells the ToPrimitive function that if there are multiple primitive types the operand could convert to, and number is one of them, it should convert the value to a number instead of a different type.

OrdinaryToPrimitive²

If the value being passed to ToPrimitive is an object, it then calls OrdinaryToPrimitive with the same two arguments, value and type hint. OrdinaryToPrimitive generates a list of methods to call to convert the value to a primitive.

If "string" is passed in as the type hint, the method order becomes toString followed by valueOf. In this case, since "number" was passed, the method order is valueOf followed by toString. It's important to note that while all values that get to this point are objects, not every value will use the valueOf and toString methods on the Object prototype.

If the first method results in a value of type "object", the result of calling the second method returned. If the first method does not return a value of type "object", the result of the first method is returned.

OrdinaryToPrimitive( {} )

In the case of {}, the only prototype being looked at is Object, so it first tries calling valueOf on the object using Object.prototype.value()³, but that returns {}. Since typeof {} === "object", it moves to the next method. It then calls Object.prototype.toString()⁴
; If Object.prototype.toString() is called on a value that is an object, the builtinTag is set to "Object". The return value of Object.prototype.toString() is the concatenation of "[object ", tag, "]". The return value for passing in an empty object, then, is "[object Object]"

OrdinaryToPrimitive( [] )

In the case of [], there are two prototypes to take into consideration -- Array and Object. If a method exists on the Array prototype, that is the method called. If, however, it does not exist on the Array prototype, it looks for the method on the Object prototype. The Array prototype does not contain a method for valueOf, so it first tries calling Object.prototype.valueOf(). That returns [], and since typeof [] === "object", it moves on to the next method.

The Array prototype does have a toString() method, so It then calls Array.prototype.toString()⁵.

Array.prototype.toString() returns the value of the join method on the array. As there are no elements in the array, the return value of Array.prototype.toString() on an empty array is an empty string.

Comparison

Now that both sides are converted to their primitive values, it's time to compare them in relation to each other.

"[object Object]" > ""

A string of any length is going to be greater in value than the value of an empty string.

Follow-up

The way that JavaScript evaluates abstract equality when one operand is of type String/Number/Symbol/BigInt and the other operand is an object is to call the same ToPrimitive on the object and then check equality⁶.

Therefore, we can also sanity check that {} is actually converted to "[object Object]" and [] is converted to an empty string by performing abstract equality checks.

console.log({} == "[object Object]") // true
console.log([] == "") // true

Why does {} > [] error in browser?

Shout out to Martijn Imhoff for asking this question.

The way that the specification for JavaScript is written, block statements are evaluated before expressions, so when the interpreter sees curly braces when not in an expression context, it interprets them as a block rather than an object literal. That's why you get an error when you attempt to run those expressions in the browser. The way to force the interpreter to see {} as an object literal instead of as a block is to wrap it in parentheses.

If you were to open a Node console rather than a browser console, you would see:

This is because Node made a change to evaluate input as expressions before evaluating them as statements. That change can be seen here.

TLDR Version

{} is converted to "[object Object]"

[] is converted to ""

"[object Object]" > ""

References:

¹ ToPrimitive specification

² OrdinaryToPrimitive specification

³ Object.prototype.valueOf() specification

⁴ Object.prototype.toString() specification

⁵ Array.prototype.toString() specification

⁶ Abstract Equality Comparison algorithm

Learning to Love Regex

Amy Shackles — Thu, 12 Nov 2020 03:45:21 +0000

You create a table of information somewhere and decide to transfer it somewhere else in markdown format.

Only, when you go to copy the values into your code editor, you realize that the formatting is all wrong! Verdammt! You spent all day compiling this information and you really don't want to spend the rest of the day fiddling around with the formatting to turn it into a markdown table.

Never fear, friend. Regex to the rescue.

Step 1: Know how to write a markdown table

The basic format is this:

The heading for the table needs a pipe (|) on either side of each column.
Between the heading of the table and the table body, there needs to be a line where each column has a pipe on either side and the content of the column has three or more hyphens

Example:

| Heading1 | Heading2 |
| --- | --- |
| The most | Basic table ever |

Ends up looking like:

Heading1	Heading2
The most	Basic table ever

Step 2: Remove newlines

To make subsequent regular expressions easier, remove all the newlines in the pasted text and replace them with a single space.

Step 3: Create your table header

This step requires figuring out a regular expression that will match your headers and capture each header individually so that you can manipulate what surrounds it (namely, to add the pipes). This can be accomplished by making use of capture groups. For capture groups, each capture is given a number internally which can then be used in the replace operation. In this example, our table header should include Alias, Canonical property name, and Matches letters and written signs belonging to ____ script as headers, so we need to come up with a way to match those. Note that with regular expressions, there are a ton of ways to approach a regular expression to match text, so this is by no means the only way to go about it.

Find:
(\w+) ([\w\s]+(?= Matches)) ([\w\s]+)

Replace:
| $1 | $2 | $3 |\n| --- | --- | --- |\n

The find regex:

Creates a capture group of one or more alphanumeric characters (including underscore)
Matches a space
Creates a second capture group of one or more of either alphanumeric characters (including underscore) or whitespace characters only if it is followed by a space and the word 'Matches' (Since the third heading begins with 'Matches', this is a way to ensure that the second capture group ends at the right spot)
Matches a space
Creates a third capture group of one or more either alphanumeric characters (including underscore) or whitespace characters

Alias becomes capture group 1
Canonical property name becomes capture group 2
Matches letters and written signs belonging to ____ script becomes capture group 3

The replacement regex:

Adds a pipe (|) and a space before capture group 1
Adds a space and a pipe and a space before capture group 2
Adds a space and a pipe and a space before capture group 3
Adds a space and a pipe after the third capture group
Adds a new line
Adds a pipe
Adds a space
Adds three hyphens
Adds a space
Adds a pipe
Adds a space
Adds three hyphens
Adds a space
Adds a pipe
Adds a space
Adds three hyphens
Adds a space
Adds a pipe
Adds a new line

Step 4: Create the table body

This is much like the routine we went through to create the header for the table -- we need to come up with a regular expression that will match what we want to match and ensure that our replacement regular expression converts it into the format we're looking for.

I know from having input all of this data that the pattern for the table is:

The first column starts with \p{Script=, is followed by variable number of letters, followed by }
The second column starts with \p{Script=, is followed by a variable number of letters (and/or underscores), followed by }
The third column is a variable number of letters and can include multiple words (so can include whitespace)

Find:
(\\p{Script=\w+}) (\\p{Script=\w+}) ([\w\s]+)

Replace:
| $1 | $2 | $3 |\n

The find regex:

Creates a capture group of the value \p{Script= followed by one ore more alphanumeric characters followed by a }
Matches a space
Creates a capture group of the value \p{Script= followed by one or more alphanumeric values followed by a }
Matches a space
Creates a capture group of one or more alphanumeric values or whitespaces

For the first row of the table:
\p{Script=Adlm} becomes capture group 1
\p{Script=Adlam} becomes capture group 2
Adlam becomes capture group 3

The replacement regex:

Adds a pipe and a space before capture group 1
Adds a pipe and a space before capture group 2
Adds a pipe and a space before capture group 3
Adds a space and a pipe after capture group 3
Adds a new line

Copying that newly formatted text here results in (moment of truth....)

Alias	Canonical property name	Matches letters and written signs belonging to _____ script
\p{Script=Adlm}	\p{Script=Adlam}	Adlam
\p{Script=Ahom}	\p{Script=Ahom}	Ahom
\p{Script=Hluw}	\p{Script=Anatolian_Hieroglyphs}	Anatolian Hieroglyphs
\p{Script=Arab}	\p{Script=Arabic}	Arabic
\p{Script=Armn}	\p{Script=Armenian}	Armenian
\p{Script=Avst}	\p{Script=Avestan}	Avestan
\p{Script=Bali}	\p{Script=Balinese}	Balinese
\p{Script=Bamu}	\p{Script=Bamum}	Bamum
\p{Script=Bass}	\p{Script=Bassa_Vah}	Bassa Vah
\p{Script=Batk}	\p{Script=Batak}	Batak
\p{Script=Beng}	\p{Script=Bengali}	Bengali
\p{Script=Bhks}	\p{Script=Bhaiksuki}	Bhaiksuki
\p{Script=Bopo}	\p{Script=Bopomofo}	Bopomofo
\p{Script=Brah}	\p{Script=Brahmi}	Brahmi
\p{Script=Brai}	\p{Script=Braille}	Braille
\p{Script=Bugi}	\p{Script=Buginese}	Buginese
\p{Script=Buhd}	\p{Script=Buhid}	Buhid
\p{Script=Cans}	\p{Script=Canadian_Aboriginal}	Canadian Aboriginal
\p{Script=Cari}	\p{Script=Carian}	Carian
\p{Script=Aghb}	\p{Script=Caucasian_Albanian}	Caucasian Albanian
\p{Script=Cakm}	\p{Script=Chakma}	Chakma
\p{Script=Cher}	\p{Script=Cherokee}	Cherokee
\p{Script=Zyyy}	\p{Script=Common}	Common
\p{Script=Copt}	\p{Script=Coptic}	Coptic
\p{Script=Qaac}	\p{Script=Coptic}	Coptic
\p{Script=Xsux}	\p{Script=Cuneiform}	Cuneiform
\p{Script=Cprt}	\p{Script=Cypriot}	Cypriot
\p{Script=Cyrl}	\p{Script=Cyrillic}	Cyrillic
\p{Script=Dsrt}	\p{Script=Deseret}	Deseret
\p{Script=Deva}	\p{Script=Devanagari}	Devanagari
\p{Script=Dupl}	\p{Script=Duployan}	Duployan
\p{Script=Egyp}	\p{Script=Egyptian_Hieroglyphs}	Egyptian Hieroglyphs
\p{Script=Elba}	\p{Script=Elbasan}	Elbasan
\p{Script=Ethi}	\p{Script=Ethiopic}	Ethiopic
\p{Script=Geor}	\p{Script=Georgian}	Georgian
\p{Script=Glag}	\p{Script=Glagolitic}	Glagolitic
\p{Script=Goth}	\p{Script=Gothic}	Gothic
\p{Script=Gran}	\p{Script=Grantha}	Grantha
\p{Script=Grek}	\p{Script=Greek}	Greek
\p{Script=Gujr}	\p{Script=Gujarati}	Gujarati
\p{Script=Guru}	\p{Script=Gurmukhi}	Gurmukhi
\p{Script=Hani}	\p{Script=Han}	Han
\p{Script=Hang}	\p{Script=Hangul}	Hangul
\p{Script=Hano}	\p{Script=Hanunoo}	Hanunoo
\p{Script=Hatr}	\p{Script=Hatran}	Hatran
\p{Script=Hebr}	\p{Script=Hebrew}	Hebrew
\p{Script=Hira}	\p{Script=Hiragana}	Hiragana
\p{Script=Armi}	\p{Script=Imperial_Aramaic}	Imperial Aramaic
\p{Script=Zinh}	\p{Script=Inherited}	Inherited
\p{Script=Qaai}	\p{Script=Inherited}	Inherited
\p{Script=Phli}	\p{Script=Inscriptional_Pahlavi}	Inscriptional Pahlavi
\p{Script=Prti}	\p{Script=Inscriptional_Parthian}	Inscriptional Parthian
\p{Script=Java}	\p{Script=Javanese}	Javanese
\p{Script=Kthi}	\p{Script=Kaithi}	Kaithi
\p{Script=Knda}	\p{Script=Kannada}	Kannada
\p{Script=Kana}	\p{Script=Katakana}	Katakana
\p{Script=Kali}	\p{Script=Kayah_Li}	Kayah Li
\p{Script=Khar}	\p{Script=Kharoshthi}	Kharoshthi
\p{Script=Khmr}	\p{Script=Khmer}	Khmer
\p{Script=Khoj}	\p{Script=Khojki}	Khojki
\p{Script=Sind}	\p{Script=Khudawadi}	Khudawadi
\p{Script=Laoo}	\p{Script=Lao}	Lao
\p{Script=Latn}	\p{Script=Latin}	Latin
\p{Script=Lepc}	\p{Script=Lepcha}	Lepcha
\p{Script=Limb}	\p{Script=Limbu}	Limbu
\p{Script=Lina}	\p{Script=Linear_A}	Linear A
\p{Script=Linb}	\p{Script=Linear_B}	Linear B
\p{Script=Lisu}	\p{Script=Lisu}	Lisu
\p{Script=Lyci}	\p{Script=Lycian}	Lycian
\p{Script=Lydi}	\p{Script=Lydian}	Lydian
\p{Script=Mahj}	\p{Script=Mahajani}	Mahajani
\p{Script=Mlym}	\p{Script=Malayalam}	Malayalam
\p{Script=Mand}	\p{Script=Mandaic}	Mandaic
\p{Script=Mani}	\p{Script=Manichaean}	Manichaean
\p{Script=Marc}	\p{Script=Marchen}	Marchen
\p{Script=Gonm}	\p{Script=Masaram_Gondi}	Masaram Gondi
\p{Script=Mtei}	\p{Script=Meetei_Mayek}	Meetei Mayek
\p{Script=Mend}	\p{Script=Mende_Kikakui}	Mende Kikakui
\p{Script=Merc}	\p{Script=Meroitic_Cursive}	Meroitic Cursive
\p{Script=Mero}	\p{Script=Meroitic_Hieroglyphs}	Meroitic Hieroglyphs
\p{Script=Plrd}	\p{Script=Miao}	Miao
\p{Script=Modi}	\p{Script=Modi}	Modi
\p{Script=Mong}	\p{Script=Mongolian}	Mongolian
\p{Script=Mroo}	\p{Script=Mro}	Mro
\p{Script=Mult}	\p{Script=Multani}	Multani
\p{Script=Mymr}	\p{Script=Myanmar}	Myanmar
\p{Script=Nbat}	\p{Script=Nabataean}	Nabataean
\p{Script=Talu}	\p{Script=New_Tai_Lue}	New Tai Lue
\p{Script=Newa}	\p{Script=Newa}	Newa
\p{Script=Nkoo}	\p{Script=Nko}	Nko
\p{Script=Nshu}	\p{Script=Nushu}	Nushu
\p{Script=Ogam}	\p{Script=Ogham}	Ogham
\p{Script=Olck}	\p{Script=Ol_Chiki}	Ol Chiki
\p{Script=Hung}	\p{Script=Old_Hungarian}	Old Hungarian
\p{Script=Ital}	\p{Script=Old_Italic}	Old Italic
\p{Script=Norb}	\p{Script=Old_North_Arabian}	Old North Arabian
\p{Script=Perm}	\p{Script=Old_Permic}	Old Permic
\p{Script=Xpeo}	\p{Script=Old_Persian}	Old Persian
\p{Script=Sarb}	\p{Script=Old_South_Arabian}	Old South Arabian
\p{Script=Orkh}	\p{Script=Old_Turkic}	Old Turkic
\p{Script=Orya}	\p{Script=Oriya}	Oriya
\p{Script=Osge}	\p{Script=Osage}	Osage
\p{Script=Osma}	\p{Script=Osmanya}	Osmanya
\p{Script=Hmng}	\p{Script=Pahawh_Hmong}	Pahawh Hmong
\p{Script=Palm}	\p{Script=Palmyrene}	Palmyrene
\p{Script=Pauc}	\p{Script=Pau_Cin_Hau}	Pau Cin Hau
\p{Script=Phag}	\p{Script=Phags_Pa}	Phags Pa
\p{Script=Phnx}	\p{Script=Phoenician}	Phoenician
\p{Script=Phlp}	\p{Script=Psalter_Pahlavi}	Psalter Pahlavi
\p{Script=Rjng}	\p{Script=Rejang}	Rejang
\p{Script=Runr}	\p{Script=Runic}	Runic
\p{Script=Samr}	\p{Script=Samaritan}	Samaritan
\p{Script=Saur}	\p{Script=Saurashtra}	Saurashtra
\p{Script=Shrd}	\p{Script=Sharada}	Sharada
\p{Script=Shaw}	\p{Script=Shavian}	Shavian
\p{Script=Sidd}	\p{Script=Siddham}	Siddham
\p{Script=Sgnw}	\p{Script=SignWriting}	SignWriting
\p{Script=Sinh}	\p{Script=Sinhala}	Sinhala
\p{Script=Sora}	\p{Script=Sora_Sompeng}	Sora Sompeng
\p{Script=Soyo}	\p{Script=Soyombo}	Soyombo
\p{Script=Sund}	\p{Script=Sundanese}	Sundanese
\p{Script=Sylo}	\p{Script=Syloti_Nagri}	Syloti Nagri
\p{Script=Syrc}	\p{Script=Syriac}	Syriac
\p{Script=Tglg}	\p{Script=Tagalog}	Tagalog
\p{Script=Tagb}	\p{Script=Tagbanwa}	Tagbanwa
\p{Script=Tale}	\p{Script=Tai_Le}	Tai Le
\p{Script=Lana}	\p{Script=Tai_Tham}	Thai Tham
\p{Script=Tavt}	\p{Script=Tai_Viet}	Tia Viet
\p{Script=Takr}	\p{Script=Takri}	Takri
\p{Script=Taml}	\p{Script=Tamil}	Tamil
\p{Script=Tang}	\p{Script=Tangut}	Tangut
\p{Script=Telu}	\p{Script=Telugu}	Telugu
\p{Script=Thaa}	\p{Script=Thaana}	Thaana
\p{Script=Thai}	\p{Script=Thai}	Thai
\p{Script=Tibt}	\p{Script=Tibetan}	Tibetan
\p{Script=Tfng}	\p{Script=Tifinagh}	Tifinagh
\p{Script=Tirh}	\p{Script=Tirhuta}	Tirhuta
\p{Script=Ugar}	\p{Script=Ugaritic}	Ugaritic
\p{Script=Vaii}	\p{Script=Vai}	Vai
\p{Script=Wara}	\p{Script=Warang_Citi}	Warang Citi
\p{Script=Yiii}	\p{Script=Yi}	Yi
\p{Script=Zanb}	\p{Script=Zanzabar_Square}	Zanzabar Square

So if you find yourself in a situation where you need to format data and you really don't want to manually go through the repetitive work involved.... look for patterns, embrace the regex, and save yourself some time.

SingleNumber Solution in O(n) Time Without Extra Storage

Amy Shackles — Thu, 24 Sep 2020 19:21:09 +0000

Problem Statement

Thought Process

My initial conclusion was that no, you couldn't. Since there's not a range for the possible numbers in the array and the array isn't already sorted, you can solve in linear time if you used an object to store counts, but you need that extra storage or sorting is O(n log n).

But see, I forgot about XOR (^). For those of you who don't play with bits, exclusive or takes two binary numbers and for pair where one number has the bit flipped and the other doesn't, the resulting number has the bit flipped.

  01101
^ 10110
= 11011

So if you have a number and XOR it by 0, you get the number. If you have a number and XOR it by itself, you get 0.

Now, that's helpful, but why would you care about XOR for this problem?

Let's run through an example:

input:  [4,1,1,2,2,4,5,1,2,1,2]
4^1=5
5^1=4
4^2=6
6^2=4
4^4=0
0^5=5
5^1=4
4^2=6
6^1=7
7^2=5

Explanation/Solution

Because all of the values that appear twice will eventually cancel themselves out, you're left with that one solitary element that has no partner. No extra storage necessary. Linear time.

function singleNumber(nums) {
    return nums.reduce((a, b) => a ^ b)
}

Array Manipulation JavaScript Solution

Amy Shackles — Mon, 21 Sep 2020 01:06:28 +0000

Problem Statement

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array elements between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array.

Setup

The function you are writing takes two arguments. The first argument, n, represents the number of elements in the array you are performing operations on. The second argument, queries is an array of operations to perform on the array. Each element in queries is an array consisting of a starting index, ending index, and the value to be added to the elements in your array between those starting and ending indices.

Example

n = 12;
queries = [
// Start, end, value to add
    [2,   7,   4],
    [5,   9,   2],
    [6,   12,  8]
]
/*
 1   2   3   4   5   6   7   8   9   10  11  12 // Indices
*/
[0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0] // Starting array
[0,  4,  4,  4,  4,  4,  4,  0,  0,  0,  0,  0] // After queries[0]
[0,  4,  4,  4,  6,  6,  6,  2,  2,  0,  0,  0] // After queries[1]
[0,  4,  4,  4,  6,  14, 14, 10, 10, 8,  8,  8] // After queries[2]

largest = 10

Naive Approach (Brute Force)

Create an array with length of n + 1
Initialize each element in the array with 0
Create a variable to store the maximum value encountered, initialized to 0
Iterate through queries array, separating out a, b, k
Loop through the array from index a through b, incrementing each element at that index by k
If the updated value of the array at the current index is greater than the max, update max

function arrayManipulation(n, queries) {
    let arr = new Array(n + 1).fill(0);
    let max = 0;
    queries.forEach(([a, b, k]) => {
        for (let i = a; i <= b; i++) {
            arr[i] += k;
            if (arr[i] > max) {
                max = arr[i];
            }
        }
    })
    return max
}

Now, this works for some input. But think about what happens when n is a large number. Think about what happens if queries is a large array. In each operation in queries, you're updating 1-n elements in the array. That's a lot of operations to be performing. So some of the tests on HackerRank for this particular problem time out if you have a function like this as a solution. Their input is just too large to get away with using this algorithm. Womp womp. Sad trombone.

But you know what? There's no shame in not knowing how to solve this problem. It's marked as hard and it is hard. I had to look up solutions in the Discussion section to grok how one would even approach solving this problem at scale. And then I needed to take out a piece of paper and a pen to work through a few problems to understand how the provided solution worked. This is one of those solutions that once you understand it, it seems obvious. And it's beautiful. Naturally, the solutions I found were all in either C++ or Java and that's not my language of choice for code challenges, so I adapted it into JavaScript to both ensure that I understood it and to make it easier for anyone looking to solve it in JavaScript.

Solution

SPOILERS!

function arrayManipulation(n, queries) {
    let arr = new Array(n + 1).fill(0);
    queries.forEach(([a, b, k]) => {
        arr[a - 1] += k;
        arr[b] -= k;
    })
    let sum = 0;
    let max = 0;
    arr.forEach(val => {
        sum += val;
        max = Math.max(sum, max)
    })
    return max;
}

Let's go through how this works using the earlier example. Note that the reason we're changing the value at arr[a - 1] is because the problem statement indicated that the arrays are 1-indexed, so the array indices given are going to be off by 1 since arrays in JavaScript are 0-indexed. The reason we change arr[b] and not arr[b-1] is that the operations are meant to be from a to b inclusive and so we want to add the end point as being after the last index operated on.


n = 12;
queries = [
// Start, end, value to add
    [2,   7,   4],
    [5,   9,   2],
    [6,   12,  8]
]
/*
 1   2   3   4   5   6   7   8  9  10 11  12  13 // Indices
*/
 [0, 0,  0,  0,  0,  0,  0,  0, 0,  0, 0,  0,  0] // Starting array
 [0, 4,  0,  0,  0,  0,  0, -4, 0,  0, 0,  0,  0] // After [2,7,4]
 [0, 4,  0,  0,  2,  0,  0, -4, 0, -2, 0,  0,  0] // After [5,9,2]
 [0, 4,  0,  0,  2,  8,  0, -4, 0, -2, 0,  0, -8] // After [6,12,8]

sum = 0, max = 0, arr = [0,4,0,0,2,8,0,-4,0,-2,0,0,-8]
sum += 0; // sum stays 0, max stays 0
sum += 4; // sum is now 4, sum > max, so max becomes 4
sum += 0; // sum stays same, max stays same
sum += 0; // sum stays same, max stays same
sum += 2; // sum is now 6; sum > max, so max becomes 6;
sum += 8; // sum is now 14; sum > max, so max becomes 14;
sum += 0; // sum stays same, max stays same
sum += -4; // sum is 10; max > sum, so max stays 14;
sum += 0; // sum stays same, max stays same
sum += -2; // sum is 8; max > sum, so max stays 14;
sum += 0; // sum stays same, max stays same
sum += 0; // sum stays same, max stays same
sum += -8; // sum is 0; max > sum, so stays 14;

max = 14;

How does this work? Well, because we're subtracting the value of k at the index following the end index, we're only adding the value of a given k for the indices we should have added that k to. And because we're only changing the values in the array to mark the beginning and end of operations, we're only performing 2 updates for each query. We've changed a variable operation with a worst case complexity of n to be constant! Not too shabby.

Problem taken from HackerRank

Homebrew Basics

Amy Shackles — Mon, 14 Sep 2020 19:22:01 +0000

Homebrew Terminology

Formula: A package definition written in Ruby
Keg: Installation prefix of a formula (e.g., /usr/local/Cellar/pipenv)
Keg-only dependency: Dependency that isn't symlinked to places like /usr/local
Cask: An extension of Homebrew to install MacOS native apps (e.g., Atom and Google Chrome)
Cellar: Where kegs are installed (/usr/local/Cellar)
Bottle: A pre-built keg (rather than one built from source)
Tap: A git repository. To tap a repository is to make a shallow clone of it.
Brew bundle: An extension of Homebrew to describe dependencies

Essential commands

brew install <formula name> # Installs a package

brew uninstall <formula name> # Uninstalls a package

brew list # Lists all installed packages

brew search # Lists all locally available packages

brew search <text> # Searches online in homebrew/core and
# homebrew/cask

brew search /<text>/ # Search term is interpreted as a 
# regular expression if bookended by slashes.  Searches 
# online in homebrew/core and homebrew/cask

Useful commands

brew commands # Lists all built-in and external commands known
# to homebrew.  Returns with subheadings for:
# "Built-in commands", "Built-in developer commands",
# "External commands", "Cask commands", and
# "external cask commands".

brew cleanup # Removes old lock files and outdated downloads
# for formulae and casks, removing old versions

brew doctor # Checks system for potential problems

brew log # Shows git log for the Homebrew repository

brew log <formula name> # Shows git log for formula

brew update # Fetches newest version of Homebrew and all
# formula from Github and performs necessary migrations

brew upgrade # Upgrade outdated casks and formula using the
# same options they were installed with

brew upgrade <formula name|cask name> # Upgrade formula|cask

Managing Background Services

Brew services manage background services using the macOS launchctl daemon manager

brew services run <formula name> # Run the service without
# registering to launch it at login (or boot)

brew services run --all # Run all services without registering
# to launch them at login/boot

brew services start <formula name> # Immediately start the
# service and register it to launch at login (or boot)

brew services start --all # Immediately start all services
# and register them to launch at login/boot

brew services stop <formula name> # Immediately stop the
# service and unregister it from launching at login (or boot)

brew services stop --all # Immediately stop all services
# and register unregister them from launching at login/boot

brew services restart <formula name> # Stop (if necessary) and
# start the service immediately, registering to launch at
# login (or boot)

brew services restart --all # Stop (if necessary) all services
# and start them immediately, registering to launch them at 
# login/boot

brew services cleanup # Remove all unused services

brew services # Lists all managed services and whether they 
# are stopped or started

References:

Trust, But Verify (Downloads)

Amy Shackles — Mon, 13 Jul 2020 20:43:53 +0000

Have you ever downloaded something from the internet and noticed that the site you're downloading from has a message about verifying the integrity of the downloaded package? Have you ever been curious how to go about doing that, so clicked the link, only to see a jumble of text displayed? Believe me, I know the feeling.

While the task of acquiring the SHA256 value of a downloaded file is easy to figure out (there are plenty of resources online on how to do that), most of the examples out there seem to only go that far, relying on your ability to spot the difference visually between the two outputs.

My friends, there is a better way.

Option 1: Echo!

1) After downloading the package you want to verify, make a note of where that file is. If it makes it easier, cd into the containing folder so that you don't need to specify the path to it.
2) Copy the SHA256 value from the download site that corresponds with the package you downloaded (that's going to be all the letters/numbers before the spaces and the file name)
3) In your terminal shell, type the command:

echo "${Copied 256 Value}  /path/to/downloaded/file" | shasum -a 256 -c

Let's break that down.

The echo command will write the copied value to standard out. The quotation marks ensures that the whitespace is maintained... the two spaces between the SHA256 and the filepath is important. From the man page for shasum, the second space character is for specifying that the type should be text. It should be noted that in lieu of a space character, you could also set the mode to binary and provide the mode character '*'
The | (pipe character) passes the output (stdout) of the previous command to the input (stdin) of the next, so now the shasum command has the values we just passed to stdout
The -a flag is shorthand for -algorithm and tells shasum which type of SHA to calculate. In this example, we're working with SHA256, so we pass 256 to the -a flag.
The -c flag is shorthand for --check

Example:

 echo "ef0ca4924922514b6ad71469998821f2cf7c596b4b8b59736c3699759e0f1df8  Downloads/VirtualBox-6.1.10-138449-OSX.dmg" | shasum -a 256 -c

Option 2: Why Echo When You Can Redirect?

shasum -a 256 -c <<< "${Copied SHA256 value}  /path/toDownload"

Example:

shasum -a 256 -c <<< "ef0ca4924922514b6ad71469998821f2cf7c596b4b8b59736c3699759e0f1df8 *Downloads/VirtualBox-6.1.10-138449-OSX.dmg"

Result

Whichever option you choose, if your SHA256 values match, you should get a response like:

Downloads/VirtualBox-6.1.10-138449-OSX.dmg: OK

Breaking Down Project Euler #1: Multiples of 3 and 5

Amy Shackles — Fri, 08 May 2020 00:11:02 +0000

Greetings, friends.

If you want to get to the meat of this post, click here

As you may (or may not) know, I'm a currently unemployed software developer. A currently unemployed workaholic of a software developer. A currently unemployed workaholic of a software developer who did not spec into the mathematics skill tree.

For a long time, I lived with this mistaken belief that people were either good at math or they were not good at math, and I was clearly a member of the latter group. Until I was talking to one of my best friends, the smartest man I've ever met¹, about my terrible-at-math affliction.

Paraphrased version of the conversation:

"No one's good at math to start with."
"But you're good at math!"
".... because I went to a library every day and read everything I could about it. And practiced. A lot. And asked a lot of questions. I was rubbish at math."
"But you're an electrical engineer!"
"Exactly. If I can learn it, so can you. You just have to want to."

Damn it, I thought to myself. So this was exactly like that whole "no one's an amazing artist without practice" things. I have no one to blame but myself.²

Why am I telling you this story? Well, dear, patient reader, I'm a workaholic out of work. I know that if I want to stop being a workaholic out of work, I should spec more into the whiteboarding skill tree. While everyone's approach for leveling up on this skill tree is different, my general approach tends to be to try to solve a lot of problems on HackerRank/LeetCode/whatever other platform I happen to have open at the time. Emphasis on try. It would be lying to say that I struggle with every algorithmic question, because I have familiarity with quite a few now. I've slain those dragons, they hold no power over me, I am victorious. But for others, I just ... can't. For some problems, I can't even come up with a terrible solution to a problem.³ For still others, I can come up with the naive approach for solving it, but inevitably some of the tests on whatever the platform is are smart enough to test for poorly performing code and will error out.

So what do I, a workaholic with a stubborn streak and a deep hatred of not understanding a problem, do?

I look at solutions. Sometimes, the solutions are straightforward and I feel like an idiot for not having thought of approaching it that way, before reminding myself that everything always seems easier with hindsight. Other times, the solutions work, but I am confused either a) how or b) why. And then I spend an embarrassing amount of time trying to figure out the how and why.

Which brings us to this post!

Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

The naive approach to this problem is fairly straightforward if you are familiar with the modulo operator, which gives you the remainder when one number is divided by another. One approach might be:

initialize a variable sum with the value of 0
iterate from 3 to 999 (3 because you know 1 and 2 don't divide cleanly)
if the number is divisible by 3 or 5, add that number to the sum
return the sum



function sumOf3or5(num) {
    let sum = 0;
    for (let i = 3; i < num; i++) {
        if (i % 3 === 0 || i % 5 === 0) {
            sum += i;
        }
    }
    return sum;
}

But the tests were tricky. They used values greater than Number.MAX_SAFE_INTEGER, which meant that when it came to mathematical operations on those numbers ... well, it didn't do well. But more than that, because the numbers were so high, it also meant that this naive solution was not going to work⁴.

This was one of the times where I had to look at other people's solutions to come to an answer. The solution I ended up with was:



function sumOf3or5(num) {
/* 
    The test cases use numbers greater than Math.MAX_INTEGER, so we 
    need to use a data type that can handle larger numbers.  You could 
    pull in a library like bignumbers.js for this, but there's a new data 
    type in JavaScript for big numbers -- BigInt.   
*/
    num = BigInt(num);
/*
    We not only have to add the sum of multiples of 3 and 5 together, but 
    because 3 * 5 = 15, we need to make sure to subtract all the sums of 
    multiples of 15 in order to remove duplicates
*/
    return (
        BigInt(sumOfSequence(num - 1n, 3) 
        + sumOfSequence(num - 1n, 5)
        - sumOfSequence(num - 1n, 15)).toString()
        )
}

function sumOfSequence(num, multiple) {
    // find the number of times multiple can go into num
    let terms = num / BigInt(multiple);
    // Use Gauss's summation trick
    let sum = terms * (terms + 1n) / 2n;
    return BigInt(multiple) * sum;
}

First off, if you're not familiar with BigInt in JavaScript, that 'n' at the end of numbers is just to indicate that it's a BigInt type.

Second, I'm sure you're looking at that n * (n + 1) / 2 bit and going "...?"

"I get that that's the way to sum numbers, but why are we using the number of times a multiple can go into the number for the formula? And why are we multiplying by the multiple afterward?"

Good question.

Say that we're looking for the sum of multiples of 3s and 5s for numbers less than 10.

To calculate the multiples of 3, we would be passing 9 and 3 to our sumOfSequence function. That would mean that the 'n' we would be using for the summation would be 3 (9 / 3 = 3). So what we're using Gauss's trick for is the summation of 1 to 3 (1 + 2 + 3) and then multiplying it by the multiple so that we get the actual sum of the multiple.



(1 + 2 + 3) * 3 = 18
3 + 6 + 9 = 18

If you made it all the way down here, thanks for reading. I hope it helps you in some small way. Let me know if you'd be interested in reading more content like this. Honestly, feel free to reach out in general. Be safe, be kind, take care!

Every time I found myself leaning on my natural writing tendency of including an aside, I cut and pasted it down here into the footnotes.

Footnotes

[1] Literally a genius, and not in the pretentious "I'm a member of MENSA and all should bow before me" way, more in the "you asked a good question, but you would have to understand three different levels above what you currently know to understand my answer to your question, so let me patiently explain to you how all of that stuff works so you know what I'm talking about" way.
[2] Well, maybe my high school guidance counselor who convinced me to stop taking math because I would "never need it as a health and human sciences major". >insert an eyebrow narrow right here<
[3] Sometimes I can come up with a terrible solution, but it is so terrible that I wouldn't even admit to having come up with it. I'm serious, it's bad.
[4] It has to iterate through all of the numbers from 3 to the number passed in, so if the number is large, this is going to take a lot of time to execute.