Prefix and Suffix Arrays

A Prefix Array, also known as a Prefix Sum Array or Cumulative Sum Array, is an Array with the calculation of cumulative sums of elements in a source array. It stores the cumulative sum of elements up to a certain index in the array. This can also be done in-place, so that the target rewrites values of the source.

Prefix and Suffix arrays are useful for range computations. For example, LeetCode 1608. Special Array With X Elements Greater Than or Equal X

Here’s how it works:

Given an array of numbers, the prefix array would be another array where each element prefix[i] stores the sum of elements from index 0 to index i in the array.

For example, given nums = [1, 2, 3, 4, 5], the prefix array would be [1, 3, 6, 10, 15], because:

prefix[0] = 1                      // sum from nums[0] to [0]
prefix[1] = 1 + 2 = 3              // sum from nums[0] to [1]
prefix[2] = 1 + 2 + 3 = 6          // sum from nums[0] to [2]
prefix[3] = 1 + 2 + 3 + 4 = 10     // sum from nums[0] to [3]
prefix[4] = 1 + 2 + 3 + 4 + 5 = 15 // sum from nums[0] to [4]
Code language: JavaScript (javascript)

Here is an example of creating a prefix array in-place, in JavaScript:—

const nums = [1, 2, 3, 4, 5];
nums.forEach((num, i) => nums[i] += nums[i-1] ?? 0);
// [1, 3, 6, 10, 15]
Code language: JavaScript (javascript)

Suffix Array:

A suffix array is similar to a prefix array, but it stores cumulative sums in reverse order. Instead of storing the sum of elements up to a certain index from left to right, a suffix array stores the sum of elements from right to left.

Given the array nums = [1, 2, 3, 4, 5], the suffix array would be:—

suffix[4] = 5
suffix[3] = 5 + 4 = 9
suffix[2] = 5 + 4 + 3 = 12
suffix[1] = 5 + 4 + 3 + 2 = 14
suffix[0] = 5 + 4 + 3 + 2 + 1 = 15

//  [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

Suffix Array Code

Creating a suffix array function is a little trickier than writing a prefix array. It can be done with a new array or in-place, replacing values of an existing array. Here are both.

function createSuffixArray(nums) {
    const suffixArray = new Uint32Array(nums);
    for (let i = suffixArray.length - 2; i >= 0; i--) {
        suffixArray[i] += suffixArray[i+1];
    }
    return suffixArray;
}

const nums = [1, 2, 3, 4, 5];
createSuffixArray(nums);
// [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

By pre-allocating a Uint32Array of the appropriate length and iterating over the input array from right to left, I efficiently compute the cumulative sums and store them directly in the suffix array without needing to reverse the array or create intermediate copies. This approach is concise and efficient.

This can also be done in-place.

function createSuffixArrayInPlace(nums) {
    for (let i = nums.length - 2; i >= 0; i--) {
        nums[i] += nums[i+1];
    }
    return nums; // Optional: Return the modified nums array
}

const nums = [1, 2, 3, 4, 5];
const suffixArray = createSuffixArrayInPlace(nums);
// [15, 14, 12, 9, 5]
Code language: JavaScript (javascript)

Applicant Tracking Systems and User Privacy

Applicant tracking systems (ATS) help companies streamline the hiring process.

Although these tools are important for larger companies, unwanted data sharing, blacklisting, and hiring bias can impact job seekers.

But first, some of the benefits of ATSs.

ATSs make it easier for hiring teams to manage and track candidates through the hiring process from start to finish, consolidate and maintain candidate data in one place, automate tasks such as resume screening, scheduling, saves time and reduces costs.

ATSs are scalable. They adapt to the hiring process as needed, handling large volumes of applications and candidates with ease.

They also provide a broader pool of candidates, including passive candidates who might not be actively looking for a job, but can be searched. And there’s the rub.

Privacy and Discrimination Concerns

Applicant data can be shared both within the company and globally, between partner organizations that use the same applicant tracking system.

Applicant data can include resumes, application materials, and notes on candidate interactions to alert companies about concerns regarding qualifications or behavior.

Various attributes within applicant tracking systems (ATS) can be deemed undesirable or potentially harmful to candidates. This information is internal and not publicly accessible.

Some of these negative attributes include “Do Not Hire” flags, negative comments by recruiters or hiring managers, and low compatibility scores determined by algorithms.

People can be unofficially blacklisted by being placed on “do not hire” lists or by having negative notes or attributes associated with their profiles in multiple applicant tracking systems.

Employers that use applicant tracking system generally require applicants use them. Companies may choose to make accommodations for employees who choose not use the ATS but few companies make such exceptions.

To work as an employee at a larger company, one will most likely be required to use the company’s ATS.

Participation in this system means allowing companies to share one’s data among a global network of companies. That can compromise privacy and ultimately impact future employability.

My experience with Applicant Tracking Systems includes being invited to an interview, then being forced to answer a laundry list of demographic questions through ADP, and then being promptly excluded from the interview process. (I’m currently trying to sort this out with ADP.)

LeetCode 1289. Minimum Falling Path Sum II

DP Solution Without Modifying Input — 24 Lines — O(n^2) / O(n)

Problem: https://leetcode.com/problems/minimum-falling-path-sum-ii/

Solution: https://leetcode.com/problems/minimum-falling-path-sum-ii/solutions/5081680/dp-solution-without-modifying-input-24-lines-o-n-2-o-n/

Algorithm

  1. Find smallest two cells of first row.
  2. Loop through remaining rows, rows i+1 to len-1.
  • For each cell, if it’s not the same col index as the prev smallest, add smallest prev cell, low, else, add the second smallest prev, hi.
  • Find next two lowest cells for each next row after adding lowest cells from prev row
  1. Return last lowest cell

Complexity

  • Time complexity: O(n2)
  • Space complexity: O(n)

The lowest values of the prev row are stored in three properties, low, i, hi.

rowValues = {
  low // lowest value (from prev row)
  hi // second lowest value (from prev row
  i // lowest value's index (from prev row)
}

The values of each row are also temporarily stored in an identically-structured object.

const minFallingPathSum = (() => {
    "use strict";
    const findLeastTwo = (row, prev) => {
        const rowValues = { low: Infinity, hi: Infinity };
       for (let i = 0; i < row.length; i++) {
            let cell = row[i] + (i === prev.i ? prev.hi : prev.low);
            if (cell < rowValues.low) { 
                 Object.assign(rowValues, {hi:rowValues.low, low:cell, i:i});
            } else if (cell < rowValues.hi) {
                rowValues.hi = cell;
            }
        }
        Object.assign(prev, rowValues);
    };

    return grid => {
        const prev = { low: 0, hi: 0, i: -1 }
        for (const row of grid) findLeastTwo(row, prev);
        return prev.low;
    };
})();Code language: JavaScript (javascript)

Top-Level Array filter with Function.prototype.call.bind

Top-level Array generics didn’t make it into EcmaScript. Here’s how to hand-roll them.

const myFilter = Function.prototype.call.bind(Array.prototype.filter);
Code language: JavaScript (javascript)

And that gives is a function that can be called as:—

const isNotUpper =  e=>e>"Z"; // lexicographic comparison
myFilter("asdAxE", isNotUpper).join(""); // "asdx"
Code language: JavaScript (javascript)

How does this filter “magic” work? Let’s look step-by-step with another example, Array.prototype.forEach. But first, let’s get some “basics” out of the way.

Function.prototype.call

Function.prototype.call calls the function it’s called on, passing its first argument as the this value to that function.

In the following example, window.prompt is called three times, passing the value of each character, followed by the index in which it occurs, followed by the this value (a String object).

[].forEach.call("asd", prompt);
Code language: JavaScript (javascript)

The interpreter will execute the above as the following:

thisArg = new String("asd");

prompt("a", 0, thisArg);
prompt("s", 1, thisArg);
prompt("d", 2, thisArg);
Code language: JavaScript (javascript)

(Function window.prompt ignores the last argument.)

We can do likewise with console.log, which prints any number of arguments.

[].forEach.call("asd", console.log);
Code language: JavaScript (javascript)

image
In each call, the arguments passed are (1) the value at each index, (2) the index, and (3) the String object (promoted from a string value), used as the thisArg.

Function.prototype.call.call

We can further abstract the forEach call with:—

Function.prototype.call.call (func, thisArg, ...args )
Code language: JavaScript (javascript)

— as:—

Function.prototype.call.
    call([].forEach, "asd", console.log)
Code language: JavaScript (javascript)

— resulting:—

image

In the above code, the this value to call is [].forEach, the this value to forEach is "asd", promoted to a String object, and the callback function, the first argument to forEach, is console.log.

Function.prototype.call.bind

If the second call method is replaced with call to Function.prototype.bind, forEach will be bound as the this value to a function from call as:—

let arrayForEach = Function.prototype.call.bind([].forEach);
Code language: PHP (php)

The steps by which this new function is created are a bit tricky, but it essentially creates a new function with a `[[BoundThis]] value assigned to the first argument (promoted to an object) (See: 10.4.1.3 BoundFunctionCreate ( targetFunctionboundThisboundArgs )).

The forEach method can now be called generically, without call.

arrayForEach("asd", console.log)
Code language: JavaScript (javascript)

The bound function arrayForEach is passed with "asd", which is promoted to a string object with length=3, and used as the this arg for [].forEach. Function [].forEach is called with, console.log three times, such as:

console.log(thisArg[i], i, thisArg)
Code language: JavaScript (javascript)
image

We can reuse this top-level Array.prototype.forEach:

const arrayForEach = 
Function.prototype.call.bind([].forEach);
arrayForEach("asd", console.log)
arrayForEach("qwe", console.log)
Code language: JavaScript (javascript)
image

Function.prototype.call Shortcut

Just as Array.prototype.forEach is found on every array instance such as [].forEach, so too is Function.prototype.call found on every function instance, such as (function(){}).call.

Base Object to Call and Arrow Functions

Arrow functions get their this value from the lexical environment and Bound functions have a bound thisArg (more on this later). This:—

(e=>e).call("foo")
Code language: JavaScript (javascript)

— results undefined

For our intent, this doesn’t matter. We can still use call a layer of abstraction out, as call.call. We don’t access the Base object that far back. We can also use other functions or the built-in function constructor function, Function.

(function(){return this}).call({})
Code language: JavaScript (javascript)

— which returns the object argument, {}.

Calling of forEach is stored by binding forEach to the call method:

let boundForEach = Function.prototype.call.bind([].forEach);
Code language: JavaScript (javascript)

This can be later called with any thisArg and any callback.

boundForEach("asd", prompt);
Code language: JavaScript (javascript)

Bound Method for Array.prototype.filter

Back to the problem at hand, we want to invoke Array.prototype.filter when it’s called and with the arguments passed in:

const myFilter = Function.prototype.call.bind(Array.prototype.filter);
Code language: JavaScript (javascript)

And that gives is a function that can be called as:—

const isNotUpper =  e=>e>"Z"; // lexicographic comparison
myFilter("asXd", isNotUpper);
Code language: JavaScript (javascript)

— results:—

['a', 's', 'd']
Code language: JavaScript (javascript)

Function myFilter is called with array-like object to act as the this value for the actual function call to Array.prototype.filter.Array.prototype.filter promotes its thisArg to a String object and calls the second parameter, isNotUpper (with that String as the thisArg).

Just as we get Array.prototype.forEach with [].forEach, so too can we get Function.prototype.call from any function (except arrow or bound functions).

Function.call is the same Function.prototype.call, but gets it this arg a Function, the base object, if called as Function.call(). As mentioned, we’re not calling it like that, rather, we’re using the value of that function as the Base object for bind.

From: https://leetcode.com/problems/filter-elements-from-array/discuss/5024144/Function.prototype.call.bind

Checking NaN Values

NaN is a global property that represents an IEEE 754 “not a number”. (There is also a static NaN property of the built-in Number object, Number.NaN for pointless duplication (mdn)).

In older versions of ECMAScript NaN and other global properties like undefined were writable. You shouldn’t be doing that and Brendan, et al made it illegal; even throwin errors in strict mode..

The value type of NaN is “number”, as can be seen by the literal NaN property or by NaN values.

typeof NaN; // "number"
typeof (1 / "foo"); // "number"

Any value compared to NaN using the comparison operators == or === results false.

NaN == NaN; // false
undefined == NaN; // false

Method isNaN almost seems to work:—

isNaN(NaN); // true

— until it does type conversion, even attempting to run the algorithm when no argument is supplied.

isNaN(); // true
isNaN(undefined); // true
isNaN("-."); // true
isNaN(""); // false
isNaN("-2."); // false

The answer to that is to use Number.isNaN, which only returns true for actual NaN values and does not do type conversion.

Number.isNaN(); // false
Number.isNaN("1"); // false
Number.isNaN(""); // false
Number.isNaN("-."); // false
Number.isNaN("0xf"); // false
Number.isNaN("-2."); // false

Object.is can also reliably check NaN values:

 Object.is(NaN, NaN); // true
 Object.is(NaN, undefined); // false

Methods isFinite and the newer non-type-converting version Number.isFinite can work in certain situations:—

 Number.isFinite(NaN); // false

— but do not check exclusively for NaN, as they also return true for Infinity and -Infinity:—

 Number.isFinite(-Infinity); // false

But these methods are useful for numeric validation. Especially Number.isFinite, which, unlike global isFinite, does not do type conversion:

Number.isFinite("2"); // false
Number.isFinite(new Date); // false
isFinite("2"); // true
isFinite(new Date); // true

Teach Yourself to Speak

Have you considered learning English?

Your communication skills might not be as good as you think they are.

The greater burden of communication lies upon the one communicating the message. If you want to be understood, it is your duty to clearly and effectively communicate your intended meaning to your audience.

You don’t need school. All you need is your brain, a camera, and the will to speak well. Learn to speak by making videos of yourself speaking and watching them back.

LeetCode 15. 3Sum, in JavaScript

Problem

LeetCode 15. 3Sum — JavaScript.

Solution

https://leetcode.com/problems/3sum/solutions/2895033/javascript-sorted-typed-array-sliding-window/?orderBy=most_votes

const threeSum = numsArray => {
    "use strict";
    const nums = Int32Array.from(numsArray).sort();
    const results = [];
    const LAST  = nums.length - 1;

    let i = 0;
    do {
        const n = nums[i];
        if (n === nums[i-1]) continue;
        let l = i + 1;
        let r = LAST;
        const isPossible = (n + nums[l] + nums[l+1] <= 0);
        if (!isPossible) break;
        do {
            const ln = nums[l];
            const rn = nums[r];
            const testSum = n + ln + rn;

            if (testSum === 0) {
                results.push([n, ln, rn]);
                // Increment l; decrement r.
                // To avoid duplicate triplets,
                // repeat until unique values appear.
                //  E.g. [-10, 2, 3, 3, 7, 8]
                // [[-10, 2, 8] [-10, 3, 7]] NOT 2nd [-10, 3, 7]
                while (ln === nums[++l]);
                while (rn === nums[--r]);
            } else if (testSum < 0) {
                l++;
            } else {
                r--;
            }
        } while (l < r);
    } while (++i < LAST)
    return results;
};Code language: JavaScript (javascript)

Interactive Web Demo in JavaScript

https://mybanned.com//wp-content/uploads/2023/01/3sum.html

Video

LeetCode 54. Spiral Matrix in JavaScript

Problem

Given an m x n matrix, return all elements of the matrix in spiral order.

https://leetcode.com/problems/spiral-matrix/description/

Solution

https://leetcode.com/problems/spiral-matrix/solutions/2989475/four-pointer-javascript-video-demo/

Interactive Demo

https://mybanned.com//demo/spiral-matrix.html

Video

LeetCode 3. Longest Substring Without Repeating Characters — Interactive JavaScript

Problem

Given a string s, find the length of the longest substring without repeating characters.

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

Solution

Dynamic Programming Sliding Window with Set

Interactive Example using Promises

Explanation

Use a Sliding window. Go stepwise through characters of s to expand the longest unique string one character each step. Each time a new maximum size of characters in the Set is reached, it is stored in our variable, ans. The Set is used only to track the next possible longest unique set of characters.

If the next character in s is not in the Set, wordEnd is incremented, widening the window. Save ans = Max(new result, previous max).

If the next character is already in our Set, try a new window. We don’t know where in our word the next character exists, but we can try removing one char from the front of the set. This decreases the current running set of unique characters, but gives us a chance to possibly find a longer unique set.

MAX_LENGTH - wordStart > ans

If the length number of characters remaining are greater than our longest answer, continue the loop for a chance to get a longer answer.

Loop Terminal Condition

MAX_LENGTH - wordStart > ans
If the length number of characters remaining are greater than our longest answer, continue the loop (there is a chance to get a longer answer).

Time complexity

O(n)

Space complexity

O(2n)

JavaScript

function lengthOfLongestSubstring(s) {
    const MAX_LENGTH = s.length;
    const set = new Set();
    let ans = 0, wordStart = 0, wordEnd = 0;
    while (MAX_LENGTH - wordStart > ans) { // Loop terminal condition.
        if(!set.has(s[wordEnd])) {
            set.add(s[wordEnd++]);
            ans = Math.max(ans, wordEnd - wordStart);
        } else {
            set.delete(s[wordStart++]);
        }
    }
    return ans;
}

Changing while to do / while can improve performance. If the readability is good, why not use it?

Only one small tweak is needed to avoid an error. Can you spot the error?

function lengthOfLongestSubstring(s) {
    "use strict";
    const MAX_LENGTH = s.length;
    const testChars = new Set();

    let ans = 0, wordStart = 0, wordEnd = 0;
    if (MAX_LENGTH === 0) return 0;
    do { 
        if(!testChars.has(s[wordEnd])) {
            testChars.add(s[wordEnd++]);
            ans = Math.max(ans, wordEnd - wordStart);
        } else {
            testChars.delete(s[wordStart++]);
        }
    } while (ans < MAX_LENGTH - wordStart)
    return ans;
}

If s === "", its 0 property (wordEnd) is undefined.

We can avoid adding undefined to our map by doing a check for this special case before the loop.

if (MAX_LENGTH === 0) return 0;

Finally, adding "use strict" allows the script engine to make some of its own optimizations, more for sanity than performance. (This should mostly be done on the file level or by using modules or classes.) The result is readable and has phenomenal performance, beating 91.55 % of all javascript submissions.

Non-strict functions use a separate Environment Record for top-level lexical declarations. This is done so direct eval can determine whether any var-scoped declarations introduced by the eval code conflict with pre-existing top-level lexically scoped declarations. This is not needed for strict functions because strict direct eval places all declarations into a new Environment Record.

Performance: Beats 91.55%!

Criminal Artistworks, Lying Barry Shrum, OAG, Chinelo Bivens, Jennifer Urban, CCPA/CPRA 1798

In response to “offensive song lyrics”, Artistworks decided to remove me from their website.

In response, I requested my content back from them, including all videos and posts, per CA CC §1798.100.

Artistworks ignored all of my CCPA data portability requests to them.

I then filed a CCPA data portability request violation to the CA Office of the Attorney General (OAG) through the OAG’s website.

The OAG then reached out to Artistworks regarding the allegations I had made in my CCPA data portability request violation claim.

Artistworks responded to the OAG’s inquiry by deleting my data. Under legal representation by Barry Shrum, LLC, they then lied to the OAG, falsely stating that I had requested them to delete my data. I never requested this and it is not what I wanted.

Artistworks went on to further lie to the OAG, making libelous claims about me, a former student, in an attempt to justify their criminal actions.

Artistworks, of course, had no evidence to support their false claim that I had made the alleged request for them to delete my data. Their false claims simply didn’t happen. I had requested clearly, to Artisworks, in writing, they provide to me my data. Here is just one of the emails I sent to Artistworks. This email was addressed to Dawn Mendoza of Artistworks, clearly and lawfully requesting my data, per CCPA.

To: Dawn Mendoza <dawn@artistworks.com>,
Date: Jan 12, 2020.
Subject: CCPA Data Portability Request

Message:
YOU ARE HEREBY NOTIFIED OF LEGAL ACTION.

California Consumer Privacy Act (CCPA) Right of Access

You are to provide all of my data, including all media, posts, messages, and contacts in a human accessible and machine readable format, free of charge to me as specified by and provisioned for in CCPA SECTION 1. Section 1798.100 of the Civil Code. The data shall be in a readily-useable format that allows the me to transmit this information to another entity without hindrance.

In response, the OAG was supposed to fine them for their criminal activity, however, the OAG did nothing, accepting Artistworks’ defamatory comments as justification for their own inaction.





In follow-up with the OAG board, I asked the board “who holds the board accountable?” and “how does the board decide which cases to enforce and which to ignore?”. The board members, Jennifer Urban, et al, ignored that question.

In a follow-up to being ignored, I issues a FOIA request to the OAG for the video recording of that phone call. That FOIA request went ignored, as unfortunately happens with too many FOIA requests.

CCPA 1798.100.

OAG Public Inquiry Unit (916) 210-6276
Chinelo Bivens
PIU@doj.ca.gov

Jennifer Urban
jurban@berkeley.edu
Tel: 510-642-7338

Artistworks lawyer Barry Shrum, Esq (615) 338-5130