Updates

Haven’t posted in a long while… That’s because I’ve been storing all my bytes of knowledge on another platform — this cool tool I chanced upon recently: https://gingkoapp.com/. I would’ve liked to use Quiver but I don’t do Mac (yet), so the Gingko app will do for now.

Also excited to be starting my SWE career at Carousell!

Advertisements

JS Scribbles

Closure

Closures are functions that have access to their parent scope. To quote MDN, “these functions ‘remember’ the environment in which they were created”. If you’ve worked with JavaScript extensively, you would know that functions naturally have access to the variables in their parent scopes, so this is actually quite intuitive.

This is especially useful when we’re working with asynchronous/callback functions. We can declare them ahead of time before they actually run, and we can rest assured that when they do, they have access to variables declared externally.

Var/Let/Const

Using the Var keyword defines a variable either globally or locally to a function. Using the Let/Const keyword defines a variable within a block scoped (i.e. within an if statement, for loop, etc). Pretty sure I covered this in my ES6 post.

Function Declarations vs Function Expressions

Declaring someFunc(){…} and var someFunc = function(){…} has a different impact on your code. The former is known as a function declaration while the latter is known as a function expression (i.e. we call it an expression as the function is part of a “larger” statement). Try not to confuse this with C terminology, where a function declaration is actually its prototype, and the actual implementation is known as a function definition.

In the first case, the function someFunc is immediately hoisted to the top of the function, so technically it does not matter where you declare it within the function, as long as you happen to use it in the function scope. If two declarations exist for the same function name, priority will be given to be one declared later.

In the second case, the variable someFunc is hoisted to the top as well… but not the anonymous function assigned to it. This assignment only occurs at where you’ve written var someFunc = function(){…}.

Once you’re sure you’ve internalised this, try out the following short quiz.

Algorithms Workout 3: Linked Lists

Dealing with linked lists can be a bit tricky sometimes, they’re kind of like arrays, but not quite. Although their one-dimensional structure makes them relatively easy to manage, I’ve learned to be more careful with how I work with their indexes.

If we’re working with a singly linked list and want to reach the i-th element in the list from the head, we should only iterate current = current.next i-1 times. Obviously, this is because we are already at the head, so we would only take i-1 steps to get to the middle node.

It can be easy to to forget this. In the following code, I obtain the middle index of a linked list by subtracting 1 from the halved (and ceil-ed) value of the list length. I think the act of having “accounted for a 1” somehow makes one less inclined to subtract another 1 (yes you can read that again), but in any case, I have to start the subsequent traversal loop from 1 rather than 0.

Screenshot from 2017-03-16 12-35-15.png

Gayle (CTCI authors) reminds readers to keep two techniques in mind when working with linked lists:

First, is the “runner” technique that involves using a running pointer which we can use to measure the length of a linked list, traverse a few steps ahead of the current pointer, etc.

Second, is recursion.

I come from an OCaml background, so perhaps it is for that reason that I have the bad habit of insisting that my recursive calls should somehow exist within my return statement (which often looks pretty elegant when we’re doing top-down DP).

In some cases, that becomes too cumbersome. Quite often, you want to build up your recursive return values (i.e. Bottom-up/Memoised DP) from the base case, and then reference them as necessary at higher-level calls.

Qn: Given two linked lists where each node represents a place in base-10, produce their sum. (e.g. A: 5 -> 6 -> 7, B: 6 -> 7 -> 3 -> 4, A+B: 7 -> 3 -> 0 -> 1). Assume that the first node starts at the highest place.

Full solution at: https://repl.it/GZug/O2

Our expected return value is a new linked list (sumList) representing the sum of linked lists A and B. Our general strategy here requires to start recursing from the last pair of nodes in A and B.  This question is particularly tricky because you:

  1. Have to manage uneven linked list lengths
  2. Can’t carry values “forward”. If the sum of two nodes is such that 6+6 = 12, the 1 has to be carried “backward” to the sumList node that holds the sum of the previous pair of nodes in A and B.

Screenshot from 2017-03-17 12-29-21.png

Dealing with 1) is quite easy, we can just pad the shorter list with zeroes. Dealing with 2) requires us to declare a wrapper class for each of our nodes in sumList. This wrapper class nodeWithCarry would possess a node field and a carry field. Using bottom-up recursion we can obtain the nodeWithCarry for the next set of nodes down the chain, and then reference the fields on this object to create a new nodeWithCarry for the current pair of nodes we are examining.

 

Algorithms Workout 2: Matrix Rotation

Given a 2D matrix (i.e. 2D array), how do you rotate it by 90 degrees, in place?

Rotating the matrix in layers (rotate the outermost layer and then rotate the second outermost layer) is one way to approach this problem. What is perhaps the most apparent problem of this approach is that of overlapping information — if the top row is replaced by the row on the left, how can we transfer the original contents of the top row onto the row on the right?

A straightforward solution to this would be to use an another 2D matrix to hold the transformed cells. This way, we can always use the original matrix as reference and don’t have to worry about losing information.

There is however, a more space efficient way to do this. As we iterate through the cells of each top/left/bottom/right row, we use a primitive temp variable to store the data for the one particular cell so that we can apply it again later. This is clarified in the code below:

rotatingMtx.png

Though this algorithm does not technically rotate the matrix in place (it does require the temp variable), it is extremely space efficient.

Other takeaways

  • When dealing with a string that has been rotated (i.e. waterbottle -> terbottlewa), concatenating the rotated string with itself (terbottlewa = terbottlewa + terbottle) will produce a string (terbottlewaterbottlewa) that contains the original string as a substring.
  • When working with 2D arrays, the first row and first column can potentially be used as flags.

Algorithms Workout 1

With capstone project deadlines, job applications and a full academic load on my plate,  I should probably try to find ways to make life easier for myself at this point…

Tempting, but nope. For the next two weeks, I’ll be committing to a daily routine that involves working on algorithms-based questions. I’ll be spending about a couple of hours a day working on problems from the CTCI book. I feel that my familiarity with data structures has slipped, so I’ve decided to do this in order to refresh my knowledge before I step into my first interview with a Big 4 company.

Day 1 Takeaways

  • Permutations of a String

We want to return a list of permutations for a given string. For the zero-th index of every permutation, we have choices that comprise the set of unique characters present in the argument string (e.g. for “carry”, we can have ‘c’, ‘a’, ‘r’, ‘y’ at the 0th index).

As we iterate over each of these unique characters, we permute the rest of the string (i.e. the substring) and append each sub-permutation to the selected character.

perms.png

  • Instantiating array of zeroes in ES6
var a = Array(5).fill(0);
  • Binary searches are effective when working with sorted arrays/lists
  • Hash tables are useful for keeping track of unique elements in a list/matching elements between lists
  • Use bitwise operators as a set of flags for space efficiency
var checker = 0;
// -- setting flag
checker |= (1 << pos)
// ^same as checker = checker | (1 << pos)

// -- checking flag
if (checker & (1 << pos)) {...}

Operating Systems I

A large part of my final semester has been about solidifying my domain knowledge in areas related to systems and networks. I hope that, in the limited space of time I have left in college, I will be able to learn as much as I can about these topics before I move on to the working world. This post (as well similar ones in the future) will review some of the core material taught by my professors and explain ideas at a very conceptual level.

What happens when we first start our computer?

When we first initialise our CPU (fancy way of saying start our computer), the first thing that runs is your BIOS (Basic Input/Output System).  Your BIOS is known as your CPU’s firmware; it a piece of software that communicates directly with your machine’s hardware. The BIOS can be configured by you, the user, on start-up (try pressing F2 right after your computer begins to boot) and it runs your machine according to whatever has been configured. It starts up the various components of your machine such as your CPU (Central Processing Unit), RAM (Random-access Memory), GPU (Graphics Processing Unit), etc. Finally, the BIOS confirms that these parts are working as they should, before handing control over to your OS. This video, created by techquickie, covers this process very succinctly.

What is the OS? What does it do?

The OS is wonderful piece of software that manages the hardware and software resources on our computer and makes them available to the various processes we want to run.

Every time we run a program or an application on our computer, a process is created. What the process does is defined by code. In basic terms, every line of code we write is just an instruction (or a set of instructions) for the computer. So, for example, if you somehow manage to run two instances of the same video game on your computer, you would be running two processes.

What kinds of resources does the OS manage?

Most computers today are manufactured with multiple cores. A core is also known as a processing unit; it reads and executes the instructions (code) associated with each process.

It is important to note that each core executes instructions sequentially (i.e. one at a time). Thus, we can execute multiple instructions simultaneously only if we have multiple cores!

We can think of the processing power provided by these cores as resources that our machine possesses. Given x number of processes and y number of cores, how do we allocate processing power? Which processes should be prioritised? When we run multiple programs on our desktop (e.g. Spotify + Dropbox + Chrome) such that x is greater than y, how can we give the user the impression that everything is running concurrently?

Allocating resources

The scheduler is a component within the OS that decides how to divide a particular core’s processing power. Suppose that we have a single-core machine, and three different programs a, b, and c are currently running on this device. The scheduler creates a rotating schedule that delimits specific intervals of time for the core to run processes a, b, c. The rotation occurs so rapidly that, from the typical user’s point of view, it seems as though all three processes are occurring at the same time!

This should provide the layperson with a bare-bones introduction to operating systems. There’s an entire universe of other concepts worth covering: inter-process communication (pipes), threads, signals, locks, semaphores… but that’s for another time.

Unpacking Webpack 2, HMR & Loaders

Just worked through this excellent Webpack 2 tutorial by Emil Oberg. I like how straightforward and accessible it is; Oberg does not assume that you know anything about bundlers, ES6, NODE_ENV variables, etc. Let’s go through some of the concepts and code from his tutorial.

Webpack is a JS file bundler that allows us to combine all of the files we have in our /src (source) directory into our /dist (distribution) directory. In essence, Webpack takes our src/index.js, “pulls” in all of its dependencies (“import”s and “require”s), and organises everything into a single dist/bundle.js file. It can do the same for other The main difference between Webpack 1 and 2 is that the latter accepts ES6 imports, while the former does not.

Here’s an overview of our directory, for a clearer picture:

organisation.png

And here’s a look at the scripts our package.json file that we intend to run via npm:

scripts.png

The scripts build and dev both invoke webpack. build runs webpack once for production, while dev runs dev-server.js, a webpack development server file that 1) watches our source code for changes and 2) runs webpack every time a changed is noticed.

Here, we’ve not specified any settings for Webpack in our npm script. This is because we configure the settings we desire in a separate webpack.config.js file. We’ll get into how this file should look like very soon, but before that, let’s go through how we can actually watch the files we work with so that they are re-compiled whenever a change is made. We have two options:

  1. Hot Reloading: Rebuilds bundle.js + (Refreshes the browser or Refreshes bundle.js)
  2. Hot Module Replacement: Rebuild chunk + Replace chunk in browser

The latter is preferable because it doesn’t refresh all of our JS code. In doing so, it preserves the application state. How do we set this up? We create a webpack development server using webpack-dev-server. This server is essentially “a little Node.js Express server [that] uses the webpack-dev-middleware to serve a webpack bundle” (as defined by the official documentation).

Hot Module Replacement (HMR) with webpack-dev-server

webpackdevserver.png

In the above code, we 1) require webpack, 2) require the webpack configuration file, 3) define some basic settings and 4) tell the server to listen on a particular port — in this case, 8080.

WebpackDevServer expects a “compiler” that takes in the webpack config file as an argument. This is webpack-dev-server’s way of referencing our webpack config file for instructions on how it should bundle our code.

We enable Hot Module Replacement (HMR) by:

  1. Adding an entry point in webpack.config.js (which we haven’t seen)
  2. Adding the HotModuleReplacementPlugin in webpack.config.js
  3. Adding hot:true in our webpack development server configuration (as done above).

Now, let’s see how we can write our webpack.config.js file:

webpackconfigTop.png

In development mode, we use three JS files as entry points:

  1. ./src/index.js is the root JS file for our app’s source code.
  2. webpack-dev-server/client?…  informs webpack of the client entry point (localhost:8080) and activates webpack-dev-server’s inline mode. For more on inline (versus iframe) mode, refer to the docs here. It’s not clear to me why we can’t have an {inline: true} option inside webpack-dev-server.js.
  3. webpack/hot/dev-server injects specific JS code which allows HMR.

It should be pretty clear why we don’t we use all three files as entry points in production!

In development mode, the HotModuleReplacement plugin allows us to do all of that HMR magic. In production mode, we drop the HMR plugin and use the UglifyJs one, because we shouldn’t bother ourselves with hot module replacement in a production environment. The UglifyJsPlugin minifies our code (e.g. reduces lengthy variable names to single letters).

An important note: We also have to enable HMR on our app’s JS source code. To do this, we add the following lines to our index.js:

hotModuleReloading.png

Once done, we place the entry and plugins arrays under a single object. To belabour the point, we’re exporting this webpack config object because we rely on it whenever we run a script that invokes webpack or dev-server.js! Here’s what our module.exports object might look like:

webpackConfigBtm.png

You’ve probably noticed two new items at this point — ‘source-maps’, and module loaders (which we can think of loaders as file “converters” or “transformers”). Let’s go through all of them.

Loaders

babel-loader:

If we’d like to transpile our ES6 (ES2015) code into ES5 code, then we’d have to use Babel. The dev-dependencies to install are babel-core, babel-preset-es2015, babel-preset-stage-0 and babel-loader (of course).

babel-core is, as its name implies, the “core” of Babel. It’s the transpiler. Meanwhile, the babel-preset libraries are provide configurations for transpilation. We define a .babelrc file in order to use these presets.babelrc.png

babel-loader has a few fields. The test field defines which files are to be run through babel. In this case, we only care about JS files and we use Regex to sieve those out. We exclude node_modules in order to save on overhead costs, especially since most of the JS files in the node_modules folder are already written in ES5.

file-loader (& url-loader):

In our source code, we can write out an image.js file as:

kittenImg.png

(Refer to the snapshot of the directory, if you’re lost as to where this should go)

Webpack typically handles JS, but how should it manage our media resources such as this one? Using file-loader, we can load all png|jpg|gif files into our /dist folder and hash their filenames (specifically, it’s an MD5 hash). You can see this in action in the directory snapshot shown earlier.

url-loader is another loader worth mentioning at this point. We don’t always want the browser make a new HTTP request for every media resource — especially if the file is small. This is where url-loader comes in; it allows us to define a size limit under which a media resource will be converted into a DATA URI.

style-loader and css-loader:

We require our style/style.css in our index.js file. style-loader interprets the css while css-loader injects it within the header tag of our webpage.

source-map (*not a loader, but a Webpack devtool):

The source-map devtool provides mappings between our source code (/src) and our bundled code (/dist). Why is this necessary? When we run our code and encounter errors that immediately alert us of their presence in the browser console (in our Chrome Developer tools), clicking on the direct link on the right does not bring us to the problematic code in our bundle.js, but instead, our actual source code.

Wrapping Up

Webpack 2 offers plenty of other useful tools that I won’t go into detail here (such as “tree-shaking” features that can help developers eliminate dead code). Regardless, I hope I’ve provided some insight into how we can use some of the great tools provided by Webpack (and webpack-dev-server).