JWT Tokens

JWT tokens were created as a way to safely transfer small pieces of data as a JSON object. It's intended to be used to authenticate HTTP requests without sessions. Relying on sessions means utilizing HTTP cookies as a way to validate whether two requests came from the same browser.

JWT can be fully encrypted or simply signed. We'll quickly discuss how signed tokens work.

There are 3 parts to a signed JWT token:

1. header
2. payload
3. secret

The header typically contains at least 2 fields: type and alg (a signing algorithm). Payload contains claims, which is data specific to the user (ie. things like their full name, whether she is an admin, etc). There are 3 types of claims: registered, public and private. We'll skip over these details for this post.

To create a token, we must encode our header and payload as Base64Url (a reversible encoding), then add the secret. The final output are 3 strings separated by a dot (xxxx.yyyy.zzzz) which can later be parsed in the respective environment (ie. the browser).

On a RESTful web server, routes can be protected as follows:

1. client requests authorization using some sort of standard like OpenID, etc.
   
2. under whatever condition (ie. the correct credentials), the server grants authorization
3. server returns a JWT token
4. client stores token (outside the scope of this post)
   
5. client submits the token inside subsequent HTTP user agent authorization header using the Bearer schema to access protected resources

Keep in mind is that tokens are sensitive. Therefore, don't keep it cached by the client longer then required. Also, don't store sensitive data in the token as there's a lack of security in the browser.

Smallest Difference

Given two lists of positive integers, return the two numbers from each list that have the smallest absolute difference.

For example, in [-1, 5, 10, 20, 28, 3] and [26, 134, 135, 15, 17], the numbers with the smallest difference are [28, 26].

We could compare each item on one list to every other item on the next list and keep track of the current difference while recomputing the smallest difference and returning that. This however would turn out to take quadratic time. To do better, we can take advantage of the properties of a sorted array. This would take o(nlogn + mlogm) time where n and m are the lengths of both arrays, respectively. We can then use two pointers starting at index 0 for each array and iterate until we're at the end of either of the two. While iterating, we have to determine which index to increment as well as compute our current difference. If the value from array one is less than the value from array two, that means we should try to get closer to the value of array two - so here we increment index one. If arrayOne[idxOne] is more than arrayTwo[idxTwo], we must increment index two. Before the end of every iteration, we re-compute smallest difference. We'll also need a variable to track smallest pair, which can be mutated here as well.

Three Number Sum

Given an array of distinct integers and a targetSum, find any three numbers that when added together equal to targetSum. Return them in ascending order. If there are more than one triplets, return them all. There will always be at least one.

function threeSum(array, targetSum) {
  array.sort((a, b) => a - b);
  const triplets = [];
  for (let i = 0; i < array.length - 2; i++) {
    let left = i + 1;
    let right = array.length - 1;
    while (left < right) {
      const currentSum = array[i] + array[left] + array[right];
      if (currentSum === targetSum) {
        triplets.push([array[i], array[left], array[right]]);
        left++;
        right--;
      } else if (currentSum < targetSum) {
        left++;
      } else {
        right--;
      }
    }
  }
 
  return triplets;
}

// 1, 2, 7
// 2, 3, 5
threeSum([7, 1, 5, 2, 3], 10);
// 1, 2, 6
// 1, 3, 5
// 2, 3, 4
threeSum([1, 2, 3, 4, 5, 6, 7], 9);