Running Javascript code

So you've just written some Javascript code and you want to run it in your browser. How exactly does that work?

This is a topic that seems somewhat mysterious at first, particularly if you have never spent time with a low-level language like Assembly or C.

Today I watched video from Ariya Hidayat, the creator of popular JS libraries PhantomJS and Esprima, on Javascript Engines that was extremely informative about how Javascript code actually runs.

To summarize a few of his slides, he states that the Javascript engine (such as Google Chrome's V8) follows these steps: 
1. Tokenizes / scans the code - The characters in the code are identified as a keyword, an identifier (e.g. variable name), an operator, etc. 
2. Parses and creates an Abstract Syntax Tree (AST) - The AST forms the relationships between the various tokens. 
3. Serialize the AST and generate bytecode - Ariya mentions this as a common optimization that modern Javascript engines use as it's faster than having to traverse the AST normally. 
4. Just-In Time (JIT) compiled - At this point, the code is compiled into machine code right before you need to use it.

Ariya goes into greater detail on each of these steps and if you're interested in getting a detailed understanding of the inner-workings of Javascript, I recommend you to watch it.

There's a JSConf video by Martha Girdler called The Javascript Interpreter Interpreted that provides a gentler, and less detailed introduction to this topic.

Scaling Web Applications

I watched a lecture from a Harvard CS course that provides an excellent overview on scaling web applications.

Key takeaways:

  • Scaling vertically vs. horizontally.
    • Scaling vertically means using a better and better machine as your load increases. The primary downside is that there is a point where you can no longer by a more powerful machine because it's too expensive or simply doesn't exist yet.
  • Always watch out for single point of failures. This is a theme that is emphasized throughout the lecture. The assumption that we should make is that any single piece of machine / technology can and will abruptly stop working. The key is to failing gracefully and have an automated mechanism for transitioning the work to another machine and provisioning another machine to replace the failed machine.
  • Multiple ways of load balancing.
    • Round robin is the simplest method. You simply take turns sending traffic to your various servers.
  • You can scale various layers:
    • Load balancer for the web server
    • Web servers
    • Load balancer for the database
    • Database
  • Managing sticky sessions. Different ways for doing this but the easiest is to tell the load balancer to set a cookie on the client through the HTTP header.

Clarifying JSON

I've used JSON for a while now in my web applications, but I've recently discovered that I've had a few misunderstandings and thought I would share them in case others had similar misunderstandings.

In a recent JSConf talk, Douglas Crockford, who defined and popularized JSON as a data interchange format, talks about how he got the naming of JSON wrong. It's pretty entertaining so I would just recommend watching the one-minute segment on YouTube where talks about this. Essentially, he says it's confusing to call it Javascript, since other programming languages can use it.

Misconceptions about JSON:

  • You can JSON.stringify can convert any value in Javascript to a string that stores it in the JSON format
  • When you do JSON.parse, you don't necessarily receive an object. This might seem like an obvious point, but the 'O' in JSON seemingly implies that JSON only stores Javascript object which is not true.
  • You can use JSON with a variety of programming languages, not just Javascript applications! As long as there is a JSON parser written in a language, you can use that language to receive JSON data
  • When you stringify a JS object, do not expect to preserve the order of the key-value pairs. As ECMAScript specifies, Javascript objects are un-ordered collections and the JSON format provides no guarantee of storing key-values in a particular order.

Additional resources on JSON:

Least Recently Used (LRU) Cache

LRU cache is a common interview problem that requires the creative use of two common data structures. The problem you are trying to solve is that you want to store a limited number of items in your cache (e.g. the user's local storage). Let's just say you only want to store a maximum of 10 items in the cache at any given moment.

If a user accesses 10 photos, all is well and the 10 photos are stored in the cache. But when the user wants to access the eleventh photo, you need to remove the photo that was the least recently used from the cache and store the eleventh photo so you don't exceed the size limit of 10 items.

Constraints:

  • Inserting a new item in the cache must be done in constant time: O(c)
  • Retrieval must be done in constant time: O(c)
  • Deleting an old item (the LRU item) in the cache must be done in constant time: O(c)

Basically, everything must be done in constant time. So what's the trick?

You need to use two data structures:

  • Linked list allows you to insert a new item in O(c) and delete the least recently used item (the head) in O(c)
    • You will also want to keep track of the linked list length
    • You will also need a doubly-linked list to ensure O(c) for removing any node from the linked list
  • Hash Table allows you to retrieve an item in O(c)

So let's say the user wants to access an item, for example using a photo ID string. You first need to do look up the hash table and see if that key points to a linked list node.

If it doesn't point to a linked list node, you will need to check to see your cache is at capacity. If you are at your limit, you need to remove your least recently used, which will be your head node.

Now, you can fetch data. Then, you create a linked list node using the addToTail method and you reference it in your key-value pair of your hash table. The linked list node will include: 1) the key (e.g. the photo ID string), 2) the value (e.g. the bits of the photo) and 3) point to the next node in the linked list.

If the key-value pair already points to a linked list node, then you need to delete that node and insert it using addToTail.

Merge Sort


What is Merge Sort?

Merge Sort is an efficient sorting algorithm that has a time complexity of O(n log n) which is better than elementary sorting algorithms (such as bubble sort) which have a time complexity of O(n2).

Merge Sort works by splitting an array in half recursively until the sliced array you are working with is only one element. Once you have one element, then you want to merge it with another sub-array that is one element. Then, you have a merged sub-array that has two elements.

Click here for a visual explanation of how Merge Sort works

Approach

I implemented Merge Sort using a recursive approach and modularizing my code as much as possible.

Primary Code

var mergeSort = function( array ) {  
  // Split the array in half, recurse until the array has only 2 elements
  var arrs = splitArray( array );
  var firstHalf = arrs[0].length > 1 ? mergeSort( arrs[0] ) : arrs[0];
  var secondHalf = arrs[1].length > 1 ? mergeSort( arrs[1] ) : arrs[1];
  return mergeHalves(firstHalf, secondHalf);
};

I put the recursive logic in the main function and then relied on helper functions to implement the actual splitting and merging functionality.

One thing to note is that the variable arrs is a tuple. In this case, arrs is an array that has two elements that are arrays themselves.

Split Array - Helper Function

var splitArray = function(array){  
  var mid = Math.ceil(array.length/2);
  return [ array.slice(0, mid), array.slice(mid) ];
};

Merge Two Array Halves - Helper Function

var mergeHalves = function(firstHalf, secondHalf){  
  var output = [],
      firstIdx = 0,
      secondIdx = 0;
  // Iterate until both all of the elements in both halves are pushed into output
  while ( firstIdx < firstHalf.length || secondIdx < secondHalf.length ){
    if ( firstHalf[firstIdx] < secondHalf[secondIdx] || secondHalf[secondIdx] === undefined ){
      output.push(firstHalf[firstIdx]);
      firstIdx++;
    } else {
      output.push(secondHalf[secondIdx]);
      secondIdx++;
    }
  }
  return output;
};