DEV Community: Simon Mei

Boiled down: merge sort w/recursion

Simon Mei — Thu, 30 May 2024 17:10:18 +0000

In my coding journey, I've encountered recursion many times and can only wrap my head around basic recursion algorithms like factorials and the Fibonacci sequence. When it comes to merge sort, I bang my head against the wall because while I understand the idea of it, when it comes down to the code, it just didn't make sense... until now...

I do feel that with recursion, it's an idea where you understand it better the more you see and work with it.

Merge sort idea

This video explains extremely well how merge sort with recursion works: Harvard CS50x lecture (watch until 1:58:33).

The three basic steps are:

Sort the left half of the list
Sort the right half of the list
Merge sorted halves

Okay, that's a lot of help... how do we sort the thing?!

We use a two-pointer system to compare the left and right halves.

Let's look at the code and then break it down:

function mergeSort(list) {
  if (list.length == 1) { // base case
    return list;
  }

  // Get the midpoint to split the list into halves
  let midpoint = Math.floor(list.length / 2);

  let leftHalf = list.slice(0, midpoint);
  let rightHalf = list.slice(midpoint);

  /* 
  Recursive step which further splits halves down into smaller halves
  until the base case
  */
  let left = mergeSort(leftHalf);
  let right = mergeSort(rightHalf);

  // Left half pointer
  let l = 0;
  // Right half pointer
  let r = 0;
  // List pointer
  let k = 0;

  // Compare values to fill list
  while (l < left.length && r < right.length) {
    if (left[l] < right[r]) {
        list[k] = left[l]
      l++
      k++
    } else {
        list[k] = right[r];
      r++
      k++
    }
  }

  // This only works when only left half still contains elements
  while (l < left.length) {
      list[k] = left[l];
    l++
    k++
  }
  // This only works when only right half still contains elements
  while (r < right.length) {
      list[k] = right[r];
    r++
    k++
  }

  return list;
}

Break down

Base case

if (list.length == 1) { // base case
  return list;
}

This base case is crucial since it enables the rest of the recursion steps to work. Once we reach the base case, we can build up our sorted list.

Let's use a simple list to think about this: [1, 5, 2, 3]. When we get to the base case, we should have 4 pieces: [1], [5], [2], and [3].

Recursive step (first look)

Now, if we look at the initial left half of [1, 5, 2, 3], we have [1, 5], which is also the step before we get to the base case.

let left = mergeSort(leftHalf); // [1]
let right = mergeSort(rightHalf); // [5]

Now that we have our base cases returned, we can begin to sort them.

Sort

We want to initialize a couple of pointers to help us keep track of elements from each half, and a pointer to keep track of where we are in the unsorted list.

// Left half pointer
let l = 0;
// Right half pointer
let r = 0;
// List pointer
let k = 0;

Now let's sort and merge values into our list:


// Compare values to fill list
while (l < left.length && r < right.length) {
  if (left[l] < right[r]) {
      list[k] = left[l]
    l++
    k++
  } else {
      list[k] = right[r];
    r++
    k++
  }
}

Using our basic example, we are working with [1] (left half) and [5] (right half).

Notice, if we were merging a larger list, we might encounter a scenario where (for argument's sake) all elements from one half go into our list while the other half remains.

This is how we handle that:

while (l < left.length) {
    list[k] = left[l];
  l++
  k++
}

while (r < right.length) {
    list[k] = right[r];
  r++
  k++
}

These loops only run when the pointer hasn't reached the end of its respective half.

Now, our list is equal to [1, 5].

Return and recursive step (second look)

We return this list to the previous recursive step...

Notice that while we've sorted [1, 5] on the left half, the algorithm was also busy sorting the right half, which should be [2, 3].

This is how our code and values look:

let left = mergeSort(leftHalf); // [1,5]
let right = mergeSort(rightHalf); // [2,3]

Now we run through our algorithm to sort and merge these two halves into a bigger list which is our final step, because we get [1, 2, 3, 5].

Time complexity

The time complexity to split our list into halves all the way down to the base case is logn, and the time complexity to merge them all back together is n, which means the time complexity for merge sort is nlogn.

Thoughts

After taking a look at what I've written, I feel like this is what others have written and talked about, also. Haha. But writing this for myself really solidified the idea.

I hope this made some sense, bare with me as I'm still new at writing blogs, and I was never the best at English class.

Boiled down: packages, npm, webpack, babel, task runner

Simon Mei — Tue, 07 May 2024 13:34:07 +0000

Packages

JavaScript packages are pieces of code that has been made available to be used by more than one person or group. If you needed a password-hashing program, you may be able to leverage a package called bcrypt, instead of creating it from scratch yourself. This helps you save time and stops people from reinventing the wheel all the time.

npm

npm is a software registry and package manager. You can use npm to discover packages and to install them in your project.

npm consists of three distinct components:

the website: used to discover packages and to manage profiles
the CLI: developers can interact with npm through the CLI tool
the registry: a large public database of JavaScript software and the meta-information surrounding it

Why use npm?

Package managers help automate tedious tasks such as navigating to package websites to download and move packages into your projects.

Imagine you have a project you want to share with others, but it has many large packages that can slow down the data transfer process. With npm, you can specify your packages or "dependencies" in a configuration file (called package.json) and share that file instead. Using package.json, others will know exactly which packages and which version your project uses.

webpack

Most programming languages provide a way to import code from one file to another, but JavaScript is not inherently able to do so. For security reasons, browsers cannot go into the server's file system to search for modules to use, therefore, we need to load the entire module file into a variable that'll be shared globally.

That looks like this (moment.js being the package):

<script src="node_modules/moment/min/moment.min.js"></script>
<script src="index.js"></script>

Instead, we can use webpack (also an npm package), a JavaScript module bundler. Popularized by React, webpack allows you to use the require syntax from node.js to import modules.

Running the following command installs webpack and the webpack CLI:

$ npm install webpack webpack-cli --save-dev

--save-dev saves your packages as a development environment dependency, which will be reflected in the package.json file.

Now, running the following command turns your require statements into legitimate JavaScript code that will have pulled the content from the required file(s):

$ ./node_modules/.bin/webpack index.js --mode=development

It will create a single output file dist/main.js which is what we use in our HTML file instead of index.js:

<script src="dist/main.js"></script>

Every time we make a change to index.js, we will need to run the webpack command, but this time, webpack has saved our "entry file" (index.js) and our "mode" in the file webpack.config.js. So, now we run:

$ ./node_modules/.bin/webpack

Bundling saves us time in not having to load external scripts via global variables, using require in JavaScript instead of adding <script> tags in HTML, and better performance.

babel

Babel is a transpiler which converts modern JavaScript into a backwards compatible version for old environments (browsers, platforms, legacy code bases).

We can use the ES2015 import statement instead of require for loading modules, which is the more common way today. Most modern browsers support ES2015, so it's hard to tell if babel helped, but if you had some ancient browser, you'd be able to find our code has been transpiled.

task runner

Using npm's built-in scripting capabilities, we can write some npm scripts to make using webpack easier. We can do so by editing package.json:

"script": {
  "test": "echo \"Error: no test specified\" && exit 1",
  "build": "webpack --progress --mode=production",
  "watch": "webpack --progress --watch"
}

Running npm run build will run webpack while showing percent progress (--progress), and minimizing the code for production (--mode=production).

Running npm run watch will automatically re-run webpack each time any JavaScript file changes.

npm knows the location of each npm module path, which is why we don't specify the full path for webpack: ./node_modules/.bin/webpack.

We can get another tool that provides a simple web server for live reloading:

$ npm install webpack-dev-server --save-dev

Then add an npm script to package.json:

"serve": "webpack-dev-server --open"

Now, you can run npm run serve to automatically open index.html that will rebuild its own bundled JavaScript and refresh the browser automatically.

Conclusion

There are a lot of tools being used here to make web development simpler, but arguably these tools are also overwhelming to use initially.

Many popular frameworks leverage these tools to make the development process less painful by creating everything mentioned here for you. For example, React's create-react-app or Vues' vue-cli will set up all this stuff for you.

Boiled down: Class in JavaScript

Simon Mei — Thu, 02 May 2024 18:03:12 +0000

Similarities and differences between Class and Constructor Functions

In JavaScript, classes are similar to constructor functions in that they both provides ways to create objects with prototypal inheritance. Some claim that classes are essentially syntatic sugar for over constructor functions, but there are differences...

Classes differ from constructor functions in that

They are labelled by a special internal property called [[IsClassConstructor]]
Class must be called with new
Class methods are non-enumerable, so we can't use for..in to retrieve class methods (which we don't usually want anyway)
Classes always use strict inside its construct

class User {
  greet() {
    return "Hello, there"
  }
}

Class Expressions

Classes can be defined inside another expression, passed around, returned, assigned, etc.

// Class expression
let User = class {
  greet() {
    return "Heyo";
  }
}

Class expressions may also have a name:

let User = class CoolClass {
  greet() {
    return CoolClass
  }
}

new User().greet(); // Returns CoolClass definition
console.log(CoolClass) // error, not visible outside of the class

Class fields

Class fields is a feature that allows you to define properties directly on the class itself, instead of within the constructor method. It provides concise and readable code:

class User {
  name = "Joseph";
  surname = "Joestar";

  greet() {
    console.log(`Hello, this is ${this.name} ${this.surname}`)
  }
}

const user = new User();
user.greet(); // Hello, this is Joseph Joestar

Add a # in front of the variable turns properties into private ones: #name.

You can also create static fields to define a property that is shared among all instances of the class.

class User {
  static type = "Admin";

  constructor(name) {
    this.name = name;
  }

  greet() {
    console.log(`Hi, I am ${this.name} and I have ${this.type} permissions`)
  }
}

const user = new User("Joseph");
user.greet(); // Output: Hi, I am Joseph and I have Admin persmissions

Note: Class fields are a relatively new feature in JavaScript and may not be supported across all browsers and JavaScript environments. You may need to use polyfill or a transpiler like Babel to ensure compatibility with older environments.

Boiled down: Getters/setters in JavaScript

Simon Mei — Thu, 02 May 2024 17:11:28 +0000

Security and flexibility with getters and setters

In JavaScript, there are two kinds of object properties:

Data properties:

let myObj = {name: "Joseph", surname: "Joestar"}
// name and surname are data properties

myObj.name // Joseph

Accessor properties

let myObj = {
  get name() {
    return this._name;
  },
  set name(value) {
    this._name = value;
  },
  get surname() {
    return this._surname;
  },
  set surname(value) {
    this._surname = value;
  },
  get fullName() {
    return `${this._name} ${this._surname}`
  }
}
// properties starting with an underscore are internal
// and should not be touched outside the object

// get name and set name are accessor properties
myObj.name = "Jolene"
myObj.name // Jolene

You can see how data properties allow us to directly access an object's properties, whereas accessor properties provide us getters and setters to retrieve and manipulate an object's properties.

We can even keep the actual value under a different variable name. But why should we use accessor properties? They allow us more control over operations with our objects and safeguard data that we don't want to be directly accessed or manipulated.

Within our setter, we can manipulate the data before storing it in our object's property such as validation.

Compatability using getters and settters

If we introduce new properties in the future for an object that may affect other properties, we can modify the accessor properties to make it compatible with our current needs.

Lessons from leetcode: 347 Top K Frequent Elements

Simon Mei — Fri, 23 Feb 2024 17:21:34 +0000

For future Simon to look back on...

As a self-taught dev, learning the ins-and-outs of Python usually happens as I am solving problems on leetcode or writing random programs in replit. This post is more for myself to remember what I've learned. If you're still interested in reading, then I hope this helps you!

List Comprehension

I learned the importance of initializing a list of empty lists using list comprehension or a for loop, over simply using multiplication thanks to this leetcode problem: Top K Frequent Elements.

I created a list of empty lists like this:

bucket = [[]] * 5 # [[], [], [] ,[] ,[]]

And whenever I tried to update one list in bucket, every other list was updated as well.

bucket[1].append(5) # [[5], [5], [5], [5], [5]]

I was scratching my head about this for a while, thinking it was the other parts of my code that was the problem. In reality, it all started with my bucket initialization. I had essentially created an object [] that I copied 5 times in bucket, and thus each [] was a reference to the first [] object. Updating one would mean updating all.

The way around this would be to create a for loop or to use list comprehension which allows us to write the code more compactly.

bucket = []
for _ in range(6):
  bucket.append([])

bucket = [[] for _ in range(6)]

Bucket sort

Another neat trick I learned from this leetcode problem was to use bucket sort to complete the task. Often times, I am thinking about using the least amount of resources as possible, and I usually run into a dead end doing so.

Funny thing is that my initial method of solving the problem involved using the same amount of space and more time than the solution I learned from neetcode. So, I really need to focus more about saving time first and optimize space second.