I solved hundreds of LeetCode problems (user: dhtmlkitchen). I would solve the daily problem, then create a write up on LeetCode (because if you can’t explain it, you don’t really understand it that well yourself). Next, I would take screenshots of my code, copy the problem description, and post the problem with my screenshots on LinkedIn.
After several months of doing this, I built up a following of about 155 followers.
LinkedIn Sucks
But LinkedIn groups were full of spam and many low-quality posts. Recruiters aren’t there looking to see who’s the best of the best because it’s all spam and low-quality posts. And for the spam, the only actions LinkedIn Trust & Safety take are against the user who reported, blocking and restricting the reporter and leaving the spam.
Johnson & Johnson & Getting Banned
LinkedIn kept feeding me Johnson and Johnson ads, which is a bit of a sore spot for me. So, I broke my rule of posting only professionally-related things on LinkedIn and posted a comment in the comment box of the J&J ads LinkedIn was targetting me with.
The comment was to the effect that my mother used Johnson and Johnson shower to shower talc products for the 20 years leading up to her diagnosis with leiomyosarcoma, caused by those products[1].
Johnson and Johnson recently settled a massive lawsuit for these products. However, because leiomyosarcoma is so rare, it was not listed on the lawsuit and I was excluded as a plaintiff.
I was very careful to remain within the guidelines of LinkedIn’s terms.
However, after that, LinkedIn deleted my account.
Interview Prep Matters…
I failed my 2009 Google interview after failing to solve Product of Array Except Self. It’s a challenging dynamic programming problem but once you know how to solve it, it’s not that hard.
…For the Interview
Only a small percentage of technical interview prep has direct practical relevance to the tasks I’ve performed as a Frontend engineer. Some algorithmic problems I’ve had to address as a front end engineer involve n-ary trees, graphs, strings and arrays, which appear on LeetCode. Other algorithms I’ve had to tackle do not. For example, I’ve never seen colorimetry problems on LeetCode.
Other front-end problems involve design patterns, data sanitization strategies, and using strategies to deal with a dynamic deployment environment (web browsers).
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.
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:—
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:—
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.
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.
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).
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.
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 ( targetFunction, boundThis, boundArgs )).
The forEach method can now be called generically, without call.
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)
We can reuse this top-level Array.prototype.forEach:
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:—
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 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.
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.
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.