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);

Coding, algorithm and front end interviews

What's up.

I've been studying CS fundamentals to grow my skills and interview at bigger tech companies. For the next month, I plan to write about what I'm doing to prepare. As interviews are approaching, this will definitely help consolidate all the knowledge.

This post mostly follows the Google Interview Front End Prep Guide, with my own twist to it. I've highlighted the things that are important to me (ie. review further, etc). Possibly, some of these will be their own blog posts.

The Google prep guide starts with some interview tips that fall within 4 categories: explain, clarify, improve, practice. Being able to explain your thought process and decisions signals that you're aware and knowledgeable of things that they look for. In practice, this section seems to provide input on how they score candidates. Has him/her explicitly stated and checked their assumptions? Can you properly deal with open-ended questions? So, can the candidate design better examples from bad ones on their own? Can the candidate devise a brute-force solution, then optimize it while thinking out loud (explain what's being done and why). And finally, did the candidate re-read and interpret the code manually to check for errors? Check. Check. Check.

Moving on. So what are the Google's official requirements for front end?

It's a two parts format: Coding & algorithm interviews and a technical front-end interview. An interesting fact: Their guide specifically uses plural for part 1 (coding & algorithm) and singular (so one interview) for part 2 (the front-end). I need to check with my recruiter on this. Anyway, I've also devised some ideas for blog posts for as many topics as possible. Let's continue.

 

The coding and algorithm interviews

Show good understanding of JavaScript, its APIs, Object Oriented Design and Programming, how to test code, and how to come up with corner cases and edge cases for code. At a Google interview, there's a big focus on showing conceptual understanding rather than memorizing code. You'll need to double down on concept rather than implementation - and ensure fundamentals are well articulated.

My planned posts here are:

• Know at least one programming language well (JavaScript, its APIs) (#javascript)
  
• JavaScript and object oriented programming (#javascript)
  
• JavaScript and how to test code (coming up with corner and edge cases) (#javascript)
  

 

Algorithms

Bottom-up versus top-down algorithms, complexity analysis, how to improve/change it. These include sorting, search and binary search, divide-and-conquer, dynamic programming/memorization, greediness and recursion. Yea, it's a big list. They specifically ask candidates to be ready to discuss complex algorithms like Dijkstra and A*. So we'll practice that here.

Planned posts:

• Bottom-up versus top-down algorithms (#algorithms)
  
• Complexity analysis: an introduction (#complexity-analysis)
  
• Dijkstra and A* (#famous-algorithms)

 

Sorting, Data structures, Graphs, Recursion

Planned posts:

• The trade-off between QuickSort/MergeSort/HeapSort (#sorting)
  
• Data structures: algorithms that go along with each (#data-structures)
  
• Representing a graph in-memory: pointers, matrix, adjacency list and their pros/cons (#graphs)
  
• Computational complexity and tradeoffs for basic graph traversals, BFS and DFS (#graphs)
• How recursion can solve iterative problems more elegantly (#recursion)

I skipped Mathematics. I will probably focus on completing some n-choose-k problems on my own time.

 

The technical front end interview

Onto the front end part. The ask here is that you're prepared to cover topics related to front end latency and understanding idiomatic JavaScript. Additionally, candidates must articulate strengths/shortcomings for a diverse range of topics, from web security, browser technology to JavaScript inheritance.

I would like to keep my front end posts interesting. Perhaps explore demos. I do want to be very careful as some of these topics get hairy very quickly. Hopefully I can find a proper pedagogy while properly managing rabbit holes. I think not giving up until we ask really good questions and make them fun posts is essential. So I probably need to start drafting these as early as possible. Perhaps a good structure is Who, What, Where, When, and How - to cover historical events and rudimentary examples. For the security ones, if we need to work with older versions of Node.js/Express to devise a real attack, that would be cool. Getting a tip from a Googler on what's priority here would be nice. Regardless, it'll be important to stick to basics and perhaps leave room to do a part 2 series piece afterwards.

Planned posts:

• Front end latency (#frontend, #browser)
  
• Understanding idiomatic JavaScript (#javascript)
  
• Cross-site scripting & Cross-site request forgery (#web-security)
  
• Prototypical inheritance (#javascript)
  
• DOM API & manipulation (#dom)
  
• CSS manipulation (#css)
  
• Browser / DOM events & event handling (#dom, #browser)
  
• XHR request & HTTP headers (#browser)
  
• JavaScript closures (#javascript)
  

 

The front-end design interview 

For this, they want to test your combined knowledge, theory, experience and judgement towards solving real-world engineering problems. They list the following as sample topics: web app, mobile app and API design (where the front/back meet).

Planned posts:

• Solving for real world front-end engineering problems

• Designing APIs (where the front end and back end meet)

 

Lastly, other important topics (yes, Google's big papers) 

If there's time (I can't promise since I'd assume these be more related to Google's General Interview Track for back end engineers), it would be nice to cover the famous papers and projects: The Google File System, Bigtable, MapReduce, Google Spanner and Google Chubby. We'll see. Wish me luck!