DEV Community: Ezra Schwepker

Getting Closure(s)

Ezra Schwepker — Tue, 18 Jun 2019 00:34:12 +0000

What is a Closure?

A function that references bindings from local scopes around it is called a closure. Eloquent JavaScript

A simple definition, but not one that provides understanding without greater context.

A closure is a persistent scope which holds on to local variables even after the code execution has moved out of that block. Languages which support closure (such as JavaScript, Swift, and Ruby) will allow you to keep a reference to a scope (including its parent scopes), even after the block in which those variables were declared has finished executing, provided you keep a reference to that block or function somewhere. - StackOverflow

A longer definition, but still not that informative.

The first time I encountered a closure in use, I sat there, wondering what the hell just happened. It was like magic. I didn't know how it worked, just that it did.

And it seems that that is a common sentiment.

Luckily, they're actually quite simple. They're a solution to a problem. Once you see the problem, then you'll recognize the solution, closures, for what they are.

But first we need to discuss the three pieces to the puzzle that make closures necessary.

Lexical Scope

In a programming language, scope is a set of rules which govern where a variable binding may be accessed. There are two forms, lexical and dynamic.

With dynamic scope, variable bindings are available in relation to where a function is invoked, while with lexical scope, where the binding is written is key.

const x = 5;
const printX = ( ) => console.log('The value of X is: ', x);

const dynamicScope = ( ) => {
  const x = 100;
  printX( ); // uses the x where it was called from
}
dynamicScope( );  //-> The value of X is 100

const lexicalScope = ( ) => {
  const x = 100;
  printX( ); // uses the x where it was written
} 
lexicalScope( );  //-> The value of X is 5

Lexical scope rules are the most common scoping system as they are easy to read and debug. The code that you write will behave consistently based upon how you defined it, not upon where it is used.

Lexical scoping produces a nested series of blocks which prevent a variable defined within a block from being accessed from outside of it.

// global scope

const a = 'outer';
const b = 'outer';
const c = 'outer';

{  // block scope
  const b = 'inner';
  const c = 'inner';

  {  // nested block scope
    const c = 'innermost';
    console.log('InnerMost Scope: ', 'a: ', a, 'b: ', b, 'c: ', c);
    //-> InnerMost Scope: a: outer, b: inner, c: innermost
  }
  console.log('Inner Scope: ', 'a: ', a, 'b: ', b, 'c: ', c);
  //-> Inner Scope: a: outer, b: inner, c: inner
}
console.log('Outer Scope', 'a: ', a, 'b: ', b, 'c: ', c);
//-> Outer Scope: a: outer, b: outer, c: outer

When the innermost console.log asks for the values of a, b, and c, it first looks within the block in which it is defined. If it doesn't find the variable binding, it then looks in the block surrounding the block that it was defined within, and so on until it reaches the global scope and can go no further.

That means that each console.log accesses the value of the variable in the scope where it was defined, or higher. The inner and outer scopes cannot see the value of the innermost scope.

When we define a function, it has it's own block scope, and the variables defined within it cannot be accessed from outside of the function.

function hasItsOwnScope() {
  const innerScope = 'cannot access outside of function';
}

console.log(innerScope); 
//-> Uncaught ReferenceError: innerScope is not defined

Execution Context

The next piece of the puzzle is Execution Context. Every time a function is called (aka executed, or invoked), the function is added to the call stack. If that function calls another function, then that function is added to the call stack, on top of the previous function. When a function is finished, it is removed from the call stack.

function first ( ) {
  function second ( ) {
    function third ( ) {
    }
    third( );
  }
  second( );
}
first( );

// Call stack: [ ]
// Call stack: [first]
// Call stack: [first, second]
// Call stack: [first, second, third]
// Call stack: [first, second]
// Call stack: [first]
// Call stack: [ ]

In order to conserve memory, the variables defined inside of a function are discarded when the function is removed from the call stack. Each time you call a function, it is a clean slate. Every variable defined within it, including parameters, is defined again.

These bindings, as well as special bindings available only inside of functions like arguments, name and caller are stored in the Execution Context which contains all of the information the function needs to access the values of variables defined within it, as well as variables further up the lexical scope chain.

First Class & Higher Order Functions

Many languages these days allow for first-class functions, which means that you can treat a function like any other value. It can be bound to a variable definition:

const firstClass = function myFirstClassFn( ) { /* ... */ }

And it can be passed to functions as arguments, as well are returned by other functions. When a function accepts a function as an argument, or returns it, that function is called a Higher Order function:

function higherOrderFn(firstClassFnParameter) {
  firstClassFnParameter( );

  return function anotherFirstClassFn( ) { /* ... */ }
}

higherOrderFn(firstClass); //-> function anotherFirstClassFn...

The Problem

We cannot access the values inside of a function from outside of a function
The variables inside of a function only exist when the function is called
But, we can define a function inside another function and return it.

So what happens when the returned first-class function tries to access a value defined inside of the returning higher-order function?

function higherOrder( ) {
  const insideScope = "cannot be accessed outside";
  return function firstClass( ) {
   console.log(insideScope);
  }
}

const returnedFn = higherOrder( );
returnedFn( );  //-> ???????

And THAT is a closure! Closures preserve the execution context of a function when another function is returned. The language knows that you might need the execution context later, so instead of discarding it, it attaches it to the returned function.

Later on when you're ready to use the returned function, it is able to access all of the values it needs, just like it would have been able to if you called it while it was still inside of the function you returned it from.

This is an incredibly powerful idea! You're now able to define private variables:

function higherOrder( ) {
  let privateVariable = 'private';

  return {
    get: () => privateVariable,
    set: (val) => privateVariable = val
  }
}
console.log(privateVariable);
//-> Uncaught ReferenceError: privateVariable is not defined

const getterSetter = higherOrder( );
getterSetter.get( );  //-> 'private';
getterSetter.set('new value');
getterSetter.get( );  //-> 'new value'

You can also compose functions!

const log = function (message) {
  return function (val) {
    console.log(message, val);
  }
}

const logWarning = log('Warning! We encountered an issue at: ');
const logError = log('Error: ');

logWarning('ChatBot message delivery');
logWarning('PostIt note stickyness');

logError('Connection lost');

While that is a simple example, the power to extend it is incredible. Functions are now stateful. A function returned by another function retains a memory of its higher order function and you can use that to combine functions like legos.

Should I use a design pattern?

Ezra Schwepker — Mon, 10 Jun 2019 23:46:28 +0000

Yes. And no. Maybe?

Design patterns like Flyweight or Facade each serve purpose and a reason for being. Each pattern is named, formalized, and put forth as a best practice. But if we treat them as formal structures which we cannot stray from, we limit ourselves and lose sight of how design patterns are created.

The key word isn't design, it's pattern. Design patterns are recognized. They are the convergent evolution of solutions to issues arising within Object Oriented programming. As you develop as a programmer, you will likely run into the same issues that generated a particular pattern and find yourself arriving at similar solutions.

A design pattern isn't invented in a crystalized, perfect form, it is consolidated from a multitude of similar approaches. It serves a purpose, and offers a recognized solution to a particular set of problems, but it can also be expressed in a number of different ways beyond a rigid example in a hefty book.

Design patterns are important, not just because they offer a recognized best practice approach to a specific issue, but also because they provide us a shared vocabulary which we can use to discuss abstractions of our code, free of any implementation details.

However just because a design pattern has been recognized and agreed upon and recorded, does not mean that that particular pattern is still worth implementing. Programming trends and language capabilities do change over time, and as a consequence, the problem set addressed by a particular pattern may have shifted or been addressed.

Delay Using Them

Patterns, like all forms of complexity, should be avoided until they are absolutely necessary. That’s the first thing beginners need to learn. Not the last thing.

While I can't find the source of that quote, aside from a comment here, there's a ring of truth to it. Many of the reductions of complexity made possible by a design pattern are only made necessary if we have arrived at that level of complexity to begin with.

Novice programmers often make the mistake of reaching for a pattern, or two, or all of them, and end up with a bloated, tangled mess. Using a pattern does not make your code better, unless you are using it appropriately. Even then, you may have arrived at a situation prompting using one because of the consequences of an earlier choice.

"Always implement things when you actually need them, never when you just foresee that you need them." - Ron Jeffries

Don't reach for a solution until you've encountered and defined the scope of a problem. Designing towards a pattern rather than arriving at one in response to the needs of your system will simply add cruft. Instead, refactor towards an appropriate pattern, if any while keeping your code SOLID and DRY.

Weigh the Cost

Something I appreciate greatly about the standardized format of design patterns is that each one must detail not only when it is useful and how to implement it, but also the tradeoffs.

For example, the Flyweight Pattern, which is designed to avoid unnecessary initialization, reducing resource cost:

moving the state outside the object breaks encapsulation, and may be less efficient than keeping the state intrinsic. In these cases it may be necessary to decide whether performance or memory is more important.
Flyweights are based on pointers or references. Working with Flyweights is easy in a language like Java where all object variables are references and a garbage collector is responsible for removing old objects. Flyweights are just a little trickier in a language like C++ where objects can be allocated as local variables on the stack and destroyed as a result of programmer action.

Singletons have been widely criticized and, depending upon the language, may not even be necessary, and require convoluted implementation.

Implement Concepts not Snippets

Using snippets or copy-pasted code that someone else wrote is a great way to save time. It's also a great way to end up with code that you don't personally understand or relate to to the degree that you would if you implemented it yourself.

Grok the what and the why, rather than pasting the how. Pasting in a finished pattern skips over the stages of evolution that bring you both the understanding of why it exists and how it works. A pattern has been refactored many times before it reaches a formalized state. Arriving at it will ensure that you have some of the same experiences that motivated your peers, rather than depending upon their wisdom.

Conclusion

Should you use Design Patterns? Absolutely! Should you memorize them? Maybe. Should you be familiar with them? Certainly. Should you implement them without a clearly defined need? No.

Refactoring Guru: Design Patterns
JavaScript Design Patterns
Refactoring Patterns

Do me a S.O.L.I.D.

Ezra Schwepker — Mon, 03 Jun 2019 23:47:09 +0000

When we first learn Object Oriented Programming, we're taught with simple concepts like a Dog is a Canine is an Animal. But those are just cutesy examples that obscure the real difficulties of designing an Object Oriented system.

When OOP was first introduced, it was championed as a way to write re-usable, modular code. If we cleanly separate everything into tidy groups of data and the methods that operate upon them, then we can treat everything like legos and build and build. However there's an issue lurking: no matter how perfect the initial design, requirements evolve, and what was once perfect is now inadequate and must be changed.

The question then becomes, how much has to change? Can we add a few lines of code and call it done? Do we have to rework a class, or watch as a quick fix cascades outwards, touching the entire code base?

Semantic Versioning

Before we go further, let's briefly discuss semantic versioning, a simple system for indicating the impact changes within a code base can be:

Patch version: the changes are minor bugfixes, are backwards compatible, and the new version can be substituted for prior versions with the same API with no discernible impact.
Minor version: the changes add functionality, but remain backwards compatible as the previous API was extended but not altered.
Major version: changes were made that break compatibility with prior APIs. Any code interacting with the API must also be updated to function properly.

While semantic versioning is typically reserved for applications and modules, we can apply this concept at a more granular level within our code.

SOLID

The 5 principles of SOLID design form a strategy for reducing the impact of changes within an Object Oriented System to primarily Path and Minor version updates.

Single Responsibility Principle: sensibly divide your code, so that each module is focused upon one task.
Open-Closed Principle: extend functionality without modifying the existing interface of a module.
Liskov's Substitution Principle: subclasses implement their parent's interface and functionality such that they can be substituted without altering the result.
Interface Segregation: define a focused and stable interface and limit changes to functionality improvements behind the interface.
Dependency Inversion: to prevent a tightly coupled system, implement abstracted interfaces between dependencies and consuming modules.

Single Responsibility Principle

A class or module should be focused upon a single purpose, so that only if that purpose changes should the module itself have to change.

Rather than lumping functionality into a messy utility drawer, subdivide your classes so that each has a specific purpose and reason for being. Careful subdivision results in isolated code which remains stable and re-usable, and reduces the impact of changes elsewhere in the system.

If for example we were to put all of the methods and information needed to access our backend into a single class, we would swiftly end up with a mess that would be constantly refactored as requirements change.

class AccessBackend {
  userInfo
  jwt
  baseURI
  registerUser: () =>
  authenticate: () =>
  getData: () =>
  postData: () =>
}

If instead we split the class according to purpose, we can now alter the implementation details of any class without effecting the others.

class User {
  userInfo
  registerUser: () =>
  loginUser: () =>
}

class Authenticate {
  jwt
  authenticate: () =>
  storeJWT: () =>
}

class HttpHandler {
  baseURI
  get: () =>
  post: () =>
  put: () =>
}

Alright, vocab time:

Connascence: the measure of the complexity caused by an interdependent system. A system is more connascent the wider the impact changing a single component has.

Core to the idea of connascence is the tension between two other concepts: coupling and cohesion.

Think of cohesion like a tidy workbench. A place for everything and everything in its place. Things that go together are together. The hammer is stored with the nails, while the drill bits are with the drill. The components needed to perform a single task are located in a single space.

On the other end, the more coupled your workbench is, the more components that are needed to perform a task aren't stored together, so when you want to do something, you have to open up every drawer and rummage through.

But a drill doesn't only use drill bits, and drill bits can be used by multiple kinds of drills. And the more you try and fit in a particular drawer, the harder it is to keep tidy and clean. So what might have seemed simple: put like things together, quickly becomes a task requiring careful thought.

Cohesion and coupling are two sides of the same coin. We can't just put everything in its own container, and we can't just dump it all in a single pile. Nor can we perfectly divide a system so that each drawer has everything needed for a specific task without duplicating the contents.

There will be coupling across containers and imperfect cohesion within. When we make changes to one container, at some point those changes will impact the contents of another container. However with careful planning, we can reduce the frequency with which that occurs.

Open/Closed Principle

Once you have defined a set of functionality which is accessible outside of a class, module or function, and that functionality is in use, any changes made to it will introduce potentially breaking changes to code dependent upon it.

When writing code that is designed to be re-used, responsible maintenance requires respecting the impact any change you make has upon others. Particularly in popular modules, another developer's interaction with your code may be tightly coupled and finely grained, including accommodations for errors and poor design choices.

One of the worst examples of this tight coupling is JavaScript itself. Despite the many flaws in the language, because JavaScript is so deeply embedded in the modern Internet, addressing those flaws is effectively impossible. Fixing something as fundamental as typeof null === "object" would break millions of websites. As a consequence, the development of the JavaScript language focuses upon extending the language while respecting the existing API.

Similarly, as you continue to build upon your own code, be mindful of any breaking changes. Avoid them, and if you cannot prevent them, time their release strategically, so that downstream developers are not constantly forced to refactor in order to maintain compatibility.

Liskov's Substitution Principle

Liskov's Substitution Principle gets a little strange, so stay with me. First we need to talk about Types and Type signatures.

A Type is effectively a set of expectations for how a particular set of properties can be interacted with. At a low level, we have data types like strings or arrays, which can be manipulated with operators like + or methods like .concat(). But at a higher level, we can define our own complex types.

type User {
  name: string;
  address: string;
  greet: (person: User) => User;
}

The declaration above tells us that if we encounter a data structure of the type User, it should have the defined properties. Similarly, the Type signature of the method greet indicates that it expects an input of the User type, and will return a User class.

If we define a class with a set of data and methods as a type, and if we define a class which inherits from that class as a subtype, then, because the subtype implements the functionality of the supertype, we can replace the supertype with the subtype and our program will continue to function without issue.

type User {
  greet: (person: User) => string;
}

type Moderator extends User {
  greet: (person: User) => string;
  promote: (person: User) => Moderator;
}

type Administrator extends Moderator {
  greet: (person: User) => string;
  promote: (person: User) => Administrator;
  ban: (person: User) => User;
}

Because a subtype may be substituted for its supertype, it is important that we retain compatibility with the Types that its methods may receive as arguments. For example the Administrator's promote method only requires that the given person be compatible with the User type, which means that the Administrator class can be substituted for the Moderator class without error.

Because the subtype is compatible with the supertype, we are not similarly constrained to return a supertype. Instead, as we have extended functionality within the subtype, we can return the subtype.

Vocab:

contravariance: supertypes ok, types ok, subtypes not ok

covariance: supertypes not ok, types ok, subtypes ok

In order to preserve compatibility among subtypes, we need to observe some rules:

contravariance of method arguments on the subtype: a method inherited from the suptype should accept the same type as the supertype's method.
covariance of return type: the return type of a subtype's method cannot be the supertype, but should be the subtype.
any thrown exceptions should be subtypes of exceptions thrown by the supertype. The error handling system should remain compatible with a substituted subtype.

A method of a subtype should be able to accept the same type of input as the supertype, but should return a subtype of the supertype's return type. Yikes. Let's rephrase that again.

class SuperType {
  method: (input: InputType) => ReturnType;
}

// ok
class SubType {
  method: (input: InputType) => SubReturnType;
}

// not ok
class SubType {
  method: (input: subInputType) => SubReturnType;
}

// not ok
class SubType {
  method: (input: subInputType) => ReturnType;
}

Liskov's Substitution Principle has a final consequence: because a type must be replaceable by its subtype, the subtype must implement the supertype fully. If a subtype does not implement the full supertype, then we need to rethink whether or not all the properties of the supertype actually belong at that level in the hierarchy.

We may need to alter the hierarchy so that the supertype only implements all shared properties across all subtypes, and a collection of subtypes which further share their own set of properties inherit from their own common ancestor.

class Bird {
  fly: () =>
}

class Seagull extends Bird {
  fly: () =>
}

class Penguin extends Bird {
  // fly: () =>
}

While we commonly think of flight as a core property of birds, it isn't shared by all, and unlike biology, Liskov's principle doesn't care about lineage, it cares about compatibility.

Instead we can insert a subtype of Bird which introduces the fly method and is shared by all flying birds:

class Bird {}

class FlightfullBird extends Bird {
  fly: () =>
}

class Seagull extends FlightfullBird {
  fly: () =>
}

class Penguin extends Bird {}

Interface Segregation

Interfaces govern how we interact with the internals of a module. They may provide a degree of abstraction, as well as protection by governing how a module is accessed.

A module is not limited to a single interface, and you may in fact choose to define multiple interfaces, each oriented towards a single, segregated purpose, altering what aspects of the module are accessible through each particular interface.

Dependency Inversion

Object Oriented programming promised easy code reuse, however the issue with reusable code is all the code being reused.

Unless a module is written to be explicitly dependency free, it will have dependencies, which may in turn have their own dependencies and so on. Each of these dependencies is tied to a specific version, and upgrading a version may introduce subtle bugs or break the functionality of downstream consumers entirely. We can easily arrive at a situation where our dependency tree contains multiple references to different versions of the same module.

While it is not practical to eliminate all dependencies, we can reduce the degree of coupling between our consuming modules and the dependencies that we require by inverting the typical approach.

Instead of directly referencing and utilizing a dependency within our modules, we define an abstract interface without regard to the actual details of implementation in both our module and the dependency. This interface acts as translator between the two, and localizes the external details of implementation to a single, internally controllable interface defined according to the abstract needs of the project.

SOLID, rephrased:

Decouple dependencies. Well defined modules should not be interacting directly with their dependencies. Instead define interfaces between them which abstract the details of interaction.
Keep APIs consistent and stable. Refactor behind the API.
Divide along the lines of refactoring. Expect to extend and refactor, and group the contents of a module accordingly. Each module should have a singular purpose and only a modification of that purpose should require alteration.
Extension over Modification. build upon existing functionality without modifying it, leaving consumers of the existing functionality unaffected.

Algorithm Problem Solving Strategies

Ezra Schwepker — Wed, 10 Apr 2019 18:05:33 +0000

Algorithm puzzles are an unfortunately common way to weed out candidates in the application process. However, when you aren't stressing over the job search, they're actually a lot of fun, like crossword puzzles for coders.

Solving them presents unique challenges that you won't encounter when spinning up Yet Another Crud App and exposes you to concepts that you might not already be familiar with. Practicing algorithm challenges will improve your broader problem solving abilities, as well as cement a problem solving process that is more generically useful.

Much like other types of puzzles, there are strategies that give you an early foothold into the problem and a way to break it down into smaller, more approachable chunks. With an actual puzzle, you might sort the pieces into coherent groups of similar colors or features, find look for obvious matches and grow outwards. With minesweeper, you might start with a random click, and then move around the exposed edges, marking off obvious mines and exposes obvious clear areas, only clicking randomly once more when you've exhausted all possibilities.

While there are strategies for approaching similar kinds of algorithms, I would recommend that you start with a broader problem solving strategy that you embrace as a general habit, and not just when you're grinding LeetCode as interview prep.

Be Strategic, Think First

Rather than diving in, approach the problem in stages:

Think:

Analyze the problem
Restate the problem
Write out examples of input and output
Break the problem into its component parts
Outline a solution in psuedo-code
Step through your example data with your psuedo-code

Execute

Code it up
Test your solution against your examples
Refactor

(If you're familiar with this approach, skip down to Algorithm Patterns)

Analyze the Problem

You may have had a flash of insight when you first saw the problem. This is typically your mind connecting to some prior experience. Hold on to that insight! However, you should still spend some time looking at the problem, particularly for ways that your insight differs from the actual question.

Any well written puzzle has the components needed to answer the problem contained in a sentence or two. However just because you read the problem doesn't mean you understand the problem. And if you don't understand the problem, you will stumble about aimlessly, or solve what you assumed the problem was.

Look for key words which determine the shape of the challenge.

Identify the input.
Identify the desired output.
Identify critical keywords and phrases.

For example, LeetCode #26

Given a [sorted] [array] nums, [remove the duplicates] [in-place] such that each element appear only once and [return the new length].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with [O(1) extra memory].

Input:

an array. So we know we're probably going to do some kind of iteration.
an array of numbers. That's more implied rather than specifically stated and doesn't really matter as much as we can use the same set of conditionals.

Return:

length of altered array
side effect: a modified array

Critical Words and Phrases:

sorted: repeated elements will be next to each other
remove...duplicates
in-place: the array itself must be destructively modified. This constraint dictates what array methods we may use.
O(1) extra memory: we are limited to O(1) space complexity, allowing us to define variables, but not create a copy of the array.

Restate the Problem

Now, in our own words, rephrase this so it is meaningful to ourselves. If you are in an interviewing situation, you may restate it back to the interviewer, both to set it in your own mind, and to make sure that you heard and understood them correctly.

Restated:

Given a sorted array of numbers, passed by reference, destructively modify the original array in-place by removing duplicate, so that each value only appears once. Return the length of the modified array.

Write out Example Inputs and Expected Outputs

All we are doing is mapping inputs to outputs. The challenge is figuring out how to get from A to B, however first we need to establish what A and B are. Even if you are given test cases, write your own. Looking at something doesn't create nearly as much understanding as doing it for yourself.

This is also a great time to explore your understanding of the problem and look for quirks that might trip up a naive solution. That includes edge cases like empty inputs, an array filled with duplicates of the same value, a massive data set, etc. We don't need to worry about anything outside of the constraints of the problem

Write out at least 3 examples:

[] -> [], return 0
[1] -> [1], return 1
[1, 1, 2, 3, 4, 4, 4, 5] -> [1, 2, 3, 4, 5], return 5
[1, 1, 1, 1, 1] -> [1], return 1

Given the inputs, do you have enough information to map to the result? If you don't, take a step back and continue examining the problem before continuing. If you are interviewing, feel free to ask for clarification.

Look for a simple and consistent process that you can apply regardless of the value to reach the outcome. If you end up with a convoluted series of steps and exceptions, you've likely gone too far and passed over a simpler solution.

Break the Problem into Small Parts

Starting with the simplest possible example, simply the problem down to an essential puzzle and build upon that. In this case, that is an array of three elements, two duplicated, e.g. [1, 1, 2]. Reducing the problem to such a small case makes it more approachable and clarifies the the first step you need to take. Your task from there is to develop a procedure which solves that simple case and holds true for all other cases in the problem set.

So we know we need to do a couple things:

Iterate through an array
Keep track of where in the array we are
Check adjacent values for equality
Destructively remove any duplicate values after the first occurrence
Get the final array length and return it

This is a relatively simple example problem, however there is a gotcha lurking in it: lots of iteration methods don't play nicely with removing elements from the array while you're iterating through the array, because the index values change. You may end up skipping a duplicate because the pointer incremented over it.

This gotcha indicates that we'll want to use an approach that gives us explicit control of iteration.

In a more involved problem, we might consider some or all of these components into helper functions, allowing us to write a clear and succinct solution, as well as test the validity of each of our sub-parts separately.

Psuedocode the Solution

If we've clearly grasped the problem, identified the core tasks and hopefully spotted the flaws in our own assumptions and any gotchas, we write out a human-legible description of what our approach will be. Hopefully once we've done that we can cleanly transform it into working code.

How you write pseudocode is up to you. Your notation doesn't need to be perfectly spelled and grammatically correct. It can be a gestural combination of code and words meant to convey meaning. Your pseudocode will provide a meaningful roadmap that you can refer back to if you find yourself lost deep in the particulars of implementation, so make sure that you record enough to be useful later.

If you're interviewing, this is a great opportunity to walk the interviewer through your intent. And if you're running out of time, you will at least have something on the board that demonstrates your problem solving approach.

Recommendations:

start with a function signature: removeDuplicates :: (Array) -> number
if whiteboarding, leave plenty of space to write your actual code
if using an IDE, write comments and keep them separate from your code so you can reference back later on.
write it as a series of steps and use bullet points

Since we're looking for duplicates, that means we need to perform a comparison. We can look ahead of our current position in the array, or we can look behind.

// removeDuplicates :: (Array) -> number
// if array is empty or has 1 element, return array length and exit
// iterate through array
//     compare each element to the next element
//
//     repeat until false:
//        if the next element is the same as the current element
//        remove the next element
//
//     move on to the next element in the array
//     stop once the second to last element has been reached
// return array length

We start by exiting if our array is only 0 or 1 elements in size, partly because these cases satisfy the conditions of the problem: there are no duplicates possible, and partly because they'll break our code if we try and compare the first value with a second that doesn't exist.

We also establish our iteration exit condition, and because we'll be using a look-ahead, we make sure to stop before we reach the last element.

Because we don't move our pointer position until after we've dealt with any duplicates, we should be clear of the shifting indices issue.

Step Through the Sample Data

Take a moment and mentally run some of the sample data through our pseudocode:

[] -> [], return 0
[1] -> [1], return 1
[1, 1, 2, 3, 4, 4, 4, 5] -> [1, 2, 3, 4, 5], return 5
[1, 1, 1, 1, 1] -> [1], return 1

Are we missing anything?

There may be an issue with the last example: [1, 1, 1, 1, 1]. What happens if we remove all of the duplicates, and then try and move on to the next element in our array without checking to see if there are any?

We'll want to make sure that our end condition catches any changes in the array length.

Code It

Time for rubber to meet the road. This is where you have all of the assumptions you didn't even know you made come back to haunt you. The better you were able to plan, the fewer there will be.

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    return arr.length
}

Personally I like to put in my return values first. That way I'm clear on what my goal is, and I've also captured the first case of empty or single element arrays.

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    for(let i = 0; i < arr.length; arr++) {}

    return arr.length
}

Yup, we're going with a standard for-loop. I prefer not to use them if there's more appropriate or cleaner syntax, but for this particular problem, we need the ability to control our iteration.

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    for(let i = 0; i < arr.length; i++) {
        while (arr[i + 1] && arr[i] === arr[i + 1]) arr.splice(i + 1, 1)
    }

    return arr.length
}

And that works out of the box, except for:

removeDuplicates([0,0,1,1,1,2,2,3,3,4])    //> 6, should be 5

Turns out the existence check I snuck in the while loop resolves to falsy if the array value is 0. Thanks JavaScript! So let's just rework that real quick and do a look behind instead of look ahead, which actually cleans the code up a tad as well:

function removeDuplicates(arr) {
    if (arr.length < 2) return arr.length

    for(let i = 0; i < arr.length; i++) {
        while (arr[i] === arr[i - 1]) arr.splice(i, 1)
    }

    return arr.length
}

And that passes. It's a memory efficient solution, we've only defined 1 variable besides the array reference. And it is of average speed, which we could improve upon.

But mostly it was a simple example of a process:

Analyze
Restate
Write examples
Break into small problems
Outline in pseudocode
Step through pseudocode with examples
Code
Test
Refactor

Algorithm Patterns

Aside from specific data structures and algorithms which have known and fairly standardized approaches, algorithm challenges tend to fall into categories that suggest similar solution approaches. Learning these approaches gives you a foothold into the problem.

Multiple Pointers

When we first learn to iterate through a collection, typically an array, we do so with a single pointer with an index going from the lowest value to the highest. This works for some operations and is simple to consider and code. However for problems involving comparing multiple elements, particularly ones where their position in the collection is important, finding corresponding value with a single pointer requires iterating through the array at least once for each value, an O(n²⁾ operation.

If instead we use multiple multiple points we can potentially reduce the computation down to an O(n) operation.

There are two common strategies: Two Pointer and Sliding Window

Two Pointer

Why not start at both ends and work your way in? Or start at a value or pair of values and expand outwards. This is a great approach for finding the largest sequence in a collection.

Because you are handling two points, you will need to define a rule to ensure that they do not cross over each other.

// Time complexity O(n)
// Space complexity O(1)
function sumZero(arr) {
  let left = 0;
  let right = array.length - 1;
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0) return [arr[left], arr[right]];
    else if (sum > 0) right--;
    else left++;
  }
}

Sliding Window

Instead of placing two points at the outer bounds, we can march through our array sequentially moving two pointers in parallel. The width of our window may grow or shrink according to the problem set, but it continues to progress across the collection, capturing a snapshot of whatever sequence best fits the desired outcome.

function maxSubarraySum(array, n) {
  if (array.length < n) n = array.length;
  let sum = 0;

  for (let i = 0; i < n; i++) {
    sum = sum + array[i];
  }

  let maxSum = sum;

  // shift window across array
  for (let i = n; i < array.length; i++) {
    sum = sum + array[i] - array[i - n];
    if (sum > maxSum) maxSum = sum;
  }
  return maxSum;
}

Divide and Conquer

Divide and Conquer often involves a recursive approach: applying the same rule to divide a collection until you've broken it down into the smallest components and identify the answer.

Binary Search and Merge Sort are both excellent examples of recursive subdivision leading to a solution.

O(1) Lookup: Object/Dictionary/Hash

Hashed Key:Value stores, called Objects, Dictionaries or Hashes depending upon your coding language, are incredibly useful tools for storing information when counting frequency, checking for duplicates or the complement of an answer. As there

You may store the value, or you may store the value that you are looking for instead. For example, when looking for zero-sum pairs in an array, we can save the complement rather than the value itself.

Resources:

Fundamentals of Algorithmic Problem Solving (video)
Algorithmic Problem Solving for Programmers
Top 10 Algorithms in Interview Questions
Improving your Algorithms and Data Structure Skills

A Naive Knight's Tour

Ezra Schwepker — Mon, 25 Mar 2019 01:57:14 +0000

Last week I heard of the Knight's Tour Problem, and thought "hey, that sounds fun!" And I was right. Mostly. This is the tale of that journey.

The problem is simple: given an 8x8 chessboard and a Knight placed at an arbitrary location on the board, move the Knight such that it travels to every square only once.

My initial idea turned out to be pretty close to my eventually working solution. However the struggles that I had to get from that initial idea to an actual solution proved revealing.

Here's the initial plan:

Define an 8x8 chessboard of 8 nested arrays, each with 8 values, each set to false.
Define a function which accepts the x and y position of the Knight and the current state of the board
- Mark that coordinate on the board as visited
- Determine which moves are possible from that location
- If there are no more possible moves
  - Check if the board has been visited completely
    - If it has, return the path visited to get there
    - If it hasn't, discard that branch and move on to the next one
- For each possible move, call the function again

Rather than writing the entire algorithm as one block of code, I broke it into a number of parts. This allows me to test each part individually, and to refer to them using declarative names describing my intent rather than details of implementation.

Let's start by defining our recursive function:

function knightsTour(x, y) {}

That was a Bad Idea

I would soon learn that the problem that I had chosen to solve was actually huge. As in, there are ~26.5 billion closed tours (where the Knight returns to its starting location) and ~19.6 quadrillion open tours. While that makes it seem almost as if it is hard for the Knight not to stumble across the right path, for every one of those solutions, there are even more possible wrong answers.

// Possible Move Combinations
4,000,000,000,000,000,000,000,000,000,000,000,000,000

The Knight can easily skip over a square and not be able to reach it later, or just paint itself into a corner where there are no further possible moves within reach.

Is it Recursing Infinitely, or Just Taking Forever?

It's actually really hard to tell the difference between endless recursion and an algorithm which just takes a long time to solve, if you're just sitting there...waiting.

In order to avoid this dilemma, instead of hard coding in the scale of the problem that you want to solve, make your problem scalable, so you can test it for issues before trying to arrive at the entire solution. Aim to have your algorithm run in a matter of seconds or less, and only scale up once you are confident with its validity at that problem size.

Let's re-write that simple function declaration to be scalable:

function knightsTour(x, y, boardSize) {}

Next we'll establish a set of nested arrays to represent the board:

function initializeBoard(boardSize) {
   return [...Array(boardSize)].map(v => 
              [...Array(boardSize)].map(v => false));
}

Now that we have a board, let's make a function to see if every square has been visited:

function entireBoardVisited(board) {
    return board.every(column => column.every(square => square));
}

The Array.prototype.every() function will return true only if every element in the array evaluates to true. So if every square in every column is true, then the entire board has been visited and will return true.

Recursion and Immutability

Something which is important to consider is how we ensure that each step of our branching algorithm isn't polluted by side effects from other branches. If each branch shares the same root chess board, then every time that branch visits a new cell it will mark the cell true. Now that cell has been visited for all branches. That simply won't do.

Instead we need to ensure that for every step along the way we have a chess board that records only the moves made to travel that specific path. That's going to introduce some space complexity which we would want to consider if we were talking about more than an 8x8 board. However for this case the cost is at most 64 8x8 arrays, and the solution is simple:

give each recursive step a deep copy of the board
discard any failed branch's board via garbage collection

Since we know the array is only nested once, our deep copy isn't that deep:

function copyBoard(board) {
  return board.map(column => column.slice());
}

Next we need to determine what moves are possible given any coordinate on a board of arbitrary size:

function possibleMoves(x, y, board, size) {
  const moves = []

  const possibilities = [[1, 2], [1, -2], [-1, 2], [-1, -2],
                         [2, 1], [2, -1], [-2, 1], [-2, -1]]
  for (let [offsetX, offsetY] of possibilities) {
    const newX = x + offsetX;
    const newY = y + offsetY;

    if ( newY < size && newY >= 0 
      && newX < size && newX >= 0 
      && !board[newX][newY]) {
        moves.push([newX, newY]);
    }
  }
  return moves;
}

I'd love to know a cleaner way to write that if statement. Please drop a comment if you have an idea!

Basically, if the possible move is in bounds and unvisited, we add it to our list of possible moves at the given coordinate.

My biggest mistake here was assuming that because the logic seemed correct, that it was. It wasn't. I had made several tiny but important errors in my first draft. I went on to write the actual recursive algorithm and struggle through a series of errors because of that assumption.

Don't Make Assumptions, Prove your Expectations

One of the most challenging aspects of programming is simply our own human fallibility. People are imprecise, in our thoughts, in our language. Our minds seamlessly fill in the gaps between fact and assumptions and we need to train ourselves to recognize the difference.

Each time we build out a function, give it limited test data and make sure that it works in isolation. Test Driven Development is great for this. But even if you aren't following that methodology, demonstrate to yourself that your code actually works.

In this case, I had to shrink the board down to a 3x3, then 4x4, then 6x6 size, and prove to myself that I could place the knight at any position and receive a valid result back based upon the border of the board and the contents of the cells.

We're almost ready to recurse! Let's write the most important part of any recursion function first.

The Base Case

Just like you start any while or for loop by defining the condition where it stops, we start our recursive function with the condition where it should stop recursing:

function visitNextPosition(x, y, board, boardSize) {
    // if there are no more moves, check board for completion
        // if the board is complete unwind the successful path
        // if the board is not complete, move on to the next branch
}

With actual code that will look something like this:

function visitNextPosition(x, y, board, boardSize) {
    const copiedBoard = copyBoard(board);
    copiedBoard[x][y] = true;

    const moves = possibleMoves(x, y, copiedBoard, boardSize);
    if (moves.length === 0) {
        if (entireBoardVisited(copiedBoard)) return [[x, y]];
        else return false;
    } else {
        // recursively call function for each possible move
    }
}

So now we've established two possible outcomes to a path:

return the [x, y] coordinates of the final cell inside of an array
return false for a failed branch.

Because our return values are different for the two outcomes, we can test for them and respond accordingly. Once we reach our first solution, we want to unwind our call stack, at each stage, adding the [x, y] coordinate of the step that led to our successful tour. But if we don't find a successful path, we want to unwind only until there are more alternative paths to explore.

function visitNextPosition(x, y, board, boardSize) {
  // base case ...
  } else {
    for (let [nextX, nextY] of moves) {
      let path = visitNextPosition(nextX, nextY, copiedBoard, boardSize);
      if (!!path) {
        path.push([x, y]);
        return path;
      }
    }
  return false;
}

If path evaluates to false, it will fall through the if (!!path) statement and the loop will continue on to the next possible move. If all possible moves are exhausted with no solutions reached, then loop will exit, and the function returns false.

However if the path has reached a successful solution, then it has returned something like [[6, 5]] or [[6, 5], [5, 2], [4, 4]] and all we need to do is add our current coordinates to the tail of our Knight's Tour path.

Let's fire it up!

function knightsTour(x, y, boardSize) {
  const board = initializeBoard(boardSize);

  return visitNextPosition(x, y, board, boardSize);
}

var gogoKnight = "gogoKnight " + Date.now();
console.time(gogoKnight);
console.log(knightsTour(0, 1, 8));
console.timeEnd(gogoKnight);
// 60712.694ms 
// 24105743 cells visited

That's not...bad. But can we do better?

Heuristics

Turns out we can! There's some smart people out there, and many different approaches to this problem. One such approach was proposed by H. C. von Warnsdorff back in 1823 who employed a simple heuristic (a practical method of approaching a problem which significantly reduces the steps needed to solve it):

When looking at the next possible moves, prefer the next move with the fewest possible options

This simple rule has three effects.

It leads us down the shortest paths first. If those paths do not reach a successful outcome, they'll reach their end quicker, and waste less of our time.
It leads us towards the edges of the board. Squares near the border will naturally have fewer options, and thus will be preferred by the heuristic. This has the consequence of filling in the outside first, which moves us away from the center of the board where our Knight can easily waste a lot of time on tours which are doomed to fail.
It prefers isolated squares, and is less likely to leave an orphaned, inaccessible square.

Since we've already written a function which returns an array of possible moves from a given coordinate, all we need to do is apply that function to each possible move from the coordinate that we're currently at and then compare the number of potential moves. If we then resort our array according to the fewest possible subsequent moves, then we've got our heuristic!

function warnsdorff(moves, board, size) {
  const weightedMoves = [];
  for (const [x, y] of moves) {
    const weight = possibleMoves(x, y, board, size).length;
    weightedMoves.push({move: [x, y], weight});
  }
  return weightedMoves
          .sort((a, b) => b.weight - a.weight)
          .map(weighted => weighted.move);
}

Now, we just need to call our Warnsdorff heuristic after we've checked for our base case:

function visitNextPosition(x, y, board, boardSize) {
  cellVisits++;

  const copiedBoard = copyNestedArray(board);
  copiedBoard[x][y] = true;

  let moves = possibleMoves(x, y, copiedBoard, boardSize);
  if (moves.length === 0 ) {
    if (entireBoardVisited(copiedBoard)) return [[x, y]];
    else return false;
  }

  // Resort according to Heuristic:  
  moves = warnsdorff(moves, copiedBoard, boardSize);

  for (let [nextX, nextY] of moves) {
    let path = visitNextPosition(nextX, nextY, copiedBoard, boardSize);
    if (!!path) {
      path.push([x, y]);
      return path;
    }
  }
  return false;
}

And oh man, what a difference!

console.time(gogoKnight);
console.log(knightsTour(0, 1, 8));
console.timeEnd(gogoKnight);
// 7.121ms
// 64 cells visited
// Versus:
// 60712.694ms 
// 24105743 cells visited

Even though we've added a function which adds a significant amount of processing to each move, the resulting savings are massive.

That is absolutely brilliant! These heuristics deserve some more looking into.

JavaScript; what's the meaning of `this`?

Ezra Schwepker — Wed, 13 Mar 2019 17:45:37 +0000

Alright JavaScript, what the hell. We were cool. Now, I just don't know anymore. I was hanging out with Ruby for the past couple months and I got used to how consistent and sensible self is. Now I'm back and things are...weird.

What I'm struggling with most is whether or not JavaScript's implementation of this is a necessary evil with a first-class function language, or just another bad idea that we're stuck with.

I'm going to condense for you some thoughts gleaned from MDN, Kyle Simpson and the ECMA 2020 Spec. (just for fun, search for "this" in the Spec 😂)

For those that aren't already frustrated by this, let's get you on board the "wtf, JavaScript" train. this should allow us to write functions with an reference to the owning object without having to hardcode the name of the object.

function Person(name) {
    this.name = name;
    this.printName = function() { console.log(this.name); };
}

const joe = new Person("Joe");
const sal = new Person("Sal");

joe.printName();    //> "Joe"
sal.printName();    //> "Sal"

So that's pretty damn useful. We've just used this to attach a property and a method to an object and to return the property using the method.

However, methods in JavaScript are just functions, and functions are values which can be bound to new variables, given as arguments to other functions, and returned from functions. Which means we can do this:

const printName = joe.printName;
printName;    //> ƒ () { console.log(this.name); }

printName();  //> (nothing prints)

Now that the function printName is being called from outside of the object context in which it found the value of this.name, it has no idea what this.name should resolve to. But it does actually know what this refers to:

const name = "Mike";    // declared in Global Scope

printName();   //> "Mike"

It turns out that the global object (as well as modules) has its own this property. If the function you are executing doesn't have a this defined by its execution context, it will look default to the global this.

console.log(this);    //> Window { ... }

console.log(window.globalThis);    //> Window { ... }

That still isn't that confusing. Let's go deeper.

function anExample() {
    console.log(this);
    function aNestedExample() {
        console.log(this);
    }
    aNestedExample();
}
anExample();
//> Window { ... }
//> Window { ... }

const anObj = {};
anObj.aMethod = anExample;

anObj.aMethod();
//> { aMethod: f }
//> Window { ... }

And that right there is the heart of the matter. Even though we have attached the anExample function to an object as a method, the function inside of it is still referring to the global object.

Why?

Turns out there are 2 important factors:

1) Is "use strict" mode enabled?
2) How is the function invoked?

Is `"use strict"` enabled?

There's an additional factor! Let's slightly modify the example above to use "use strict"

"use strict";

function anExample() {
    console.log(this);
    function aNestedExample() {
        console.log(this);
    }
    aNestedExample();
}
anExample();
//> undefined
//> undefined

const anObj = {};
anObj.aMethod = anExample;

anObj.aMethod();
//> { aMethod: f }
//> undefined

If "use strict" is enforced, JavaScript will not search outside of the function's execution context for a this value, so if the function does not define one for itself, this resolves to undefined.

How is the function invoked?

If the function is invoked as a function without any object provided as a context for this to refer to, then this will refer to the global object.

function example() {
    console.log(this);
}
example();    //> Window { ... }

const anObj = {
    property: 5,
    method: function() {
        console.log(this);
        function noThis() {
            console.log(this);
        }
        hasThis();
    }
}
anObj.method();
//> { property: 5, method: f }
//> Window { ... }

this is not lexically scoped. Even if it is contained within a function which has a this value and is lexically located within an object, it still refers to the global object.

What actually matters is whether or not the function is invoked as a method:

const anObj = {
    property: 5,
    method: function() {
        console.log(this);
        return function noThis() {
            console.log(this);
        }
    }
}
const anotherObj = {};

anObj.method()();
//> { property: 5, method: f }
//> Window { ... }

anotherObj.asAMethod = anObj.method();    
//> { property: 5, method: f }

anotherObj.asAMethod();
//> { asAMethod: f }

In this example, even though the function noThis is lexically within a method on another object which does have a this when invoked it doesn't have its own this unless it is invoked as a method on a new object. Otherwise refers to the global object.

So the actual notation that you use to invoke a method matters.

anObject.method;    // Dot Notation: this == true
anObject["method"]; // Computed Access: this == true
asAFunction();      // Function invocation: this == false

The value of this is generated each time the function is invoked. Any function which isn't invoked as an object method will not generate a this value.

But there's one final twist. Object generator functions and classes do have a this value when they are invoked, even though they aren't being called as a method:

class Person {
    constructor(name) {
        console.log(this);
        this.name = name;
    }
}
const joe = new Person("Joe");
//> Person {}

function Person(name) {
    console.log(this);
    this.name = name;
}
const joe = new Person("Joe");
//> Person {}

And that makes sense, they're generating an object and need to be able to reference the object while it is being created in order to add properties and methods to it.

If we define a method on the prototype, it still refers to the created object correctly, because we're using a method call!

Person.prototype.newMethod = function () {
    console.log(this);
}
joe.newMethod();    //> Person { name: "Joe" }

Ok, that's actually kind of sensible, but it sets a trap with nested functions where you aren't calling the nested function as a method.

There's two common solutions to that problem:

1) Save the value of this as a variable, e.g. that, _this, self or _self.

const anObj = {
    property: 5,
    method: function() {
        const that = this
        function noThis() {
            console.log(this);
            console.log(that);
        }
        noThis();
    }
}
anObj.method();
//> Window { ... }
//> { property: 5, method: f }

Saving the value of this allows it to be used with normal lexical scoping rules.

2) Use Arrow Functions

const anObj = {
    property: 5,
    method: function() {
        const that = this
        const noThis = () => {
            console.log(this);
            console.log(that);
        }
        noThis();
    }
}
anObj.method();
//> { property: 5, method: f }
//> { property: 5, method: f }

Arrow functions do not define their own this value, instead they look outwards up the lexical scope chain for a this value, acting just like you wish this would.

However, because they do not define their own this if you don't nest them inside of function defined with the function keyword and call that as a method from an object, your arrow function won't know what the value of this is either:

const anObj = {
    method: () => console.log(this)
}
anObj.method();    //> Window { ... }

So if you want to use this:

1) Use dot . or bracket [ ] notation when calling your function.
2) Use function to define your methods instead of arrow functions.
3) Either bind the value of this or use arrow functions within your methods for lexical scope.
4) Don't use this unless you expect to use the function as a method or have prepared for it to refer to the global object instead.

Ok, but why?

Whether or not JavaScript's solution to this is a good idea should be judged against the problem that it faces. Unlike languages like Ruby where objects own their methods and those methods are typically defined within or upon the object which self will refer to, JavaScript doesn't have formal methods.

Methods in JavaScript are actually key:value pairs on an object which stores the reference value to the function object. When calling a method with dot or bracket notation, the expression object.method() is actually two parts: object.method and the function invocation. object.method evaluates to myMethodFunction which is then is then invoked.

Unlike Ruby, where the object receives a message and determines if it can respond to the message based upon the methods defined upon it, all JavaScript objects know is what keys they have defined and what values correspond to those keys. Since the functions used as methods can be defined anywhere and may be referenced by many different objects, there's no clear owner of any function and JavaScript is forced to determine this based upon the context by which it was called rather than how it was defined.

So this makes sense. It's complicated, it's tricky, and having this refer to global rather than lexical scope is a bad idea, but now that we understand that, we anticipate it and just use that or => instead!