DEV Community: Katherine Kelly

Technical Interview Resources for the Junior Dev

Katherine Kelly — Thu, 20 Aug 2020 20:07:52 +0000

During my job search post coding bootcamp, I’ve had several interviews covering a wide range of technical concepts and behavioral scenarios. Even as a junior software engineer, it’s clear to me that software engineers need a strong foundation in computer science fundamentals like data structures and algorithms, as they serve as the bedrock of technical interviews.

I naively thought technical interviews would always be centered around solving a Leetcode-style problem that companies use to assess your coding ability for efficiency, readability, and completeness. Yes, you will frequently encounter this type of interview, however, technical interview questions can run the gamut beyond a programming challenge. The best way to prepare for an interview is to feel prepared for whatever may be thrown at you. Of course, this is easier said than done, but every interview will only better prepare you for the next one.

Yet, it can feel like information overload on the internet with free and paid resources alike that purport to get you learning everything you need to know before your upcoming interview. Though I can’t speak about what is considered the norm in technical interviewing, I can only provide my own following observations and resources I found helpful.

Technical Phone Screen

Technical phone interview rounds have been more vague on what to expect, other than being told that I'll have to solve a technical coding question. As an example, I got this once from a recruiter, “(the coding question) will be in the areas of design, algorithm and/or data structure”, and the interviewer gave me a medium-level Leetcode problem to solve. Another time, a recruiter said I can anticipate “questions regarding computer science and operating system fundamentals” and I was asked to flex my object-oriented design skills with an open-ended problem on designing a library-like service.

Interview With Hiring Manager

In another interview scenario when speaking with a hiring manager, it’s been my experience that there is a 50/50 chance you will be asked technical trivia questions (again, just my experience so take this percentage with a grain of salt). For an associate frontend role at a large tech company, I was peppered with JavaScript questions after several behavioral questions from the engineering manager. For a full stack role, I was asked questions about Unix, Git, and SQL, with the head of engineering acknowledging that several of the questions were “esoteric”, especially for a junior developer like me who hasn't had any work experience yet.

Final Round Interview

In final round interviews, the recruiter or hiring manager was generally explicit on what I should expect for each interview session during the long day, even prepping me with sample questions. Perhaps this is due to the fact you’ve made it as far as you have (congratulations!) and they want to see you succeed.

Below, I’ve compiled resources I’ve found helpful when preparing for various types of technical interviews and resources found after the interview when I wanted to brush up more on the topic. Feel free to share any resources you’ve found helpful below in the comments!

**resource I recommend

Data Structures and Algorithms / Coding Challenges

** Leetcode
** Interview Cake (paid resource for full course)
** Cracking the Coding Interview (book for purchase)
Cracking the Coding Skills PDF
Codility
HackerRank - Introducing Cracking the Coding Interview Tutorial and Practice

System Design / Systems Architecture

** Grokking the System Design Interview (paid course)
System Design Cheatsheet
Top 10 System Design Interview Questions for Software Engineers
How to Succeed in a System Design Interview

Technical Knowledge and Judgement

** Reddit - What Are Some Essential Technical (But Non-Coding) Interview Questions That New Grads Should Know the Answer To?
Cross-Site Request Forgery
What’s the Difference Between Single-Page and Multi-Page Apps?
Single Page Applications: A Powerful Design Pattern for Modern Web Apps
** W3C Accessibility Standards Overview

Systems

List of Unix Commands

Things to Know:

How systems boot and load Linux
The shell, and how it interacts with the underlying operating system
UNIX file systems and storage
Process management and state
The Linux virtual memory model
Techniques for resource control
Common system troubleshooting tools and techniques

Object Oriented Design

How to Approach Object Oriented Design Questions in Programming Interviews?
** The Top 10 Object-Oriented Design Questions Developers Should Know

Product Thinking

Product Managers Interviewing Engineers
Product Manager

Git

Git Commands
Git Tips and Tricks

Behavioral

not technical per se, but you will often get asked these questions during your technical interview, usually about collaboration and challenges, etc.

Cracking the Soft Skills PDF
** 30 Behavioral Interview Questions You Should Be Ready to Answer

Binary Search and How to Implement It

Katherine Kelly — Fri, 14 Aug 2020 21:23:43 +0000

Binary search is an efficient way to search through a sorted array for a target value. It takes a divide and conquer approach, where we get the middle element of the array and create left and right side arrays without the middle element (divide). Then we’ll check to see if the target is less than or greater than the middle element, and if so, we’ll keep searching through the left half or right half, respectively, with each step effectively halving the number of elements to be looked at (conquer).

Time and Space Complexity

The time complexity of binary search is logarithmic at O(log n). We will look through only half of an increasingly smaller data set per step. To get a time complexity of less than O(n), we must avoid touching all n elements, which binary search accomplishes.

Space complexity will depend on how you implement your algorithm (recursively vs. iteratively and create new subarrays vs. searching in-place). Implementing a recursive algorithm can have a space complexity of O(n) or O(log n), depending on if new subarrays are created. Taking an iterative approach will result in O(1) space.

Recursive Approach | new subarrays, O(n) space

When I learned binary search, I got familiar with this approach first of creating new arrays as it was easy to remember and intuitive. However, the tradeoff for ease of simple implementation is additional space, which is a factor you’ll want to consider in any situation.

function binarySearch(array, target) {
  // set your base case for recursive functions
  // if the array is empty, we know the element is not present  
  if (array.length === 0) return false;

  let midIdx = Math.floor(array.length / 2);
  let midVal = array[midIdx];
  // subarrays should not include the middle element
  let leftArray = array.slice(0, midIdx);
  let rightArray = array.slice(midIdx + 1);

  // if target is less than midVal, target should be likely in
  // the left array (pass in leftArray to the recursive call)
  if (target < midVal) {
    return binarySearch(leftArray, target);
  // if target is greater than midVal, target should be likely 
  // in the right array (pass in rightArray to the recursive call)
  } else if (target > midVal) {
    return binarySearch(rightArray, target);
  } else {
    return true;
  }
}

Recursive Approach | in-place, O(log n) space

To be able to reference the original array’s indices and keep track of the pointers that will help form the left and right halves of the array, we’ll want to pass in additional arguments to the function called low and high. low’s default value should be set to 0, as it serves as the lowest index while high’s default value is the last index in the array. midIdx is the middle index that will be the “halving point” of the “subarrays”, and we'll compare the element at its index (midVal) to the target value to see if the values match, or if the target is greater or less than the middle value.

This method will cut the space complexity down to O(log n), which is due to its call stack.

function binarySearch(array, target, low=0, high=array.length-1) {
  // set your base case for recursive functions
  // if low is greater than high, that means we’ve gone through 
  // the array and target is not present
  if (low > high) return false;

  // add low + high and divide in half to get midIdx 
  let midIdx = Math.floor((low + high) / 2);
  let midVal = array[midIdx];

  // when passing in low and high arguments to the recursive call, 
  // be sure to exclude midIdx (b/c we've already looked at it)
  if (target < midVal) {
    return binarySearch(array, target, low, midIdx - 1);
  } else if (target > midVal) {
    return binarySearch(array, target, midIdx + 1, high);
  } else {
    return true;
  }
}

Iterative Approach | in-place, O(1) space

The iterative approach also requires keeping track of low and high variables that act as the left and right sides of the array, with midIdx acting as the halving point and where we’ll be checking to see if midVal is equal to, less than, or greater than the target.

Though a recursive function may be easier to implement, an iterative approach will result in a space complexity of O(1).

function binarySearch(arr, target) {
  // setting the low and high indices
  let low = 0;
  let high = arr.length - 1;

  // want to keep searching until at least one element 
  // exists in the array
  while (low <= high) {
    const midIdx = Math.floor((low + high) / 2);
    const midVal = arr[midIdx];

    // return true if target equals midVal
    if (target === midVal) {
      return true;
      // if target is less than midVal, reassign high to 
      // midIdx - 1 (bc we've already looked at midIdx)
    } else if (target < midVal) {
      high = midIdx - 1;
      // else, the target is in the second half of array so 
      // reassign low to midIdx + 1
    } else {
      low = midIdx + 1;
    }
  }
  return false;
}

Check out the resources below for more information on binary search. Happy coding!

Resources
Binary Search Algorithm - Interview Cake
Binary Search Algorithm - Wikipedia
Iterative and Recursive Binary Search Algorithm

Destination Memoization

Katherine Kelly — Thu, 06 Aug 2020 07:00:52 +0000

If you read my post last week about tabulation, one of two dynamic programming (DP) strategies used to break down a problem into similar and smaller subproblems, then you know this post is a follow up about its sister strategy: memoization. Also, the post title is another giveaway about the wonders of memoization. Alas, the destination of this post is not a tropical vacation.

Memoization

Memoization is a recursive DP strategy that utilizes a hash map to store the results of the subproblems ((since this will be written in JavaScript, I’ll refer to this as an object going forward). The object is typically referred to as the memo (hence the moniker memoization!) and acts as a cache, and any subsequent calls to it will simply fetch the stored result in constant time.

Leetcode: Fibonacci

To illustrate memoization, I’ll walk through the following Leetcode problem and classic code challenge: Fibonacci.

The Fibonacci numbers, commonly denoted F(n) form a sequence,
called the Fibonacci sequence, such that each number is the sum of
the two preceding ones, starting from 0 and 1. That is,
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), for N > 1.
Given N, calculate F(N).

Example 1:
Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1

Example 2: 
Input: 5
Output: 
Explanation: F(5) = F(4) + F(3) = 3 + 2 = 5

Set Up Your Memo

As we’ll build a recursive function, we will want to pass in a memo object as an additional argument to the function.

function fibonacci(n, memo = {}) {
//
}

The keys in the object will represent unique arguments passed to the function, and the values will represent the result for those arguments. In this specific problem, the keys will be numbers going up to and including n.

Add a Base Case Condition

All recursive functions need a base case that will ultimately halt the recursion and exit the function (otherwise we would enter into an infinite loop) and a recursive step where we continue the recursion by making another call.

The base case condition will return the stored value in the object if the function’s argument is in the memo (exists as a key).

if (n in memo) return memo[n];

This is also a good time to take care of edge cases if n === 0 or n === 1.

if (n === 0 || n === 1) return n;

Recursive Call and Storing the Results

Before we return the result of the recursive call, we’ll want to store it in the memo. The efficiency of memoization is with the lookup of the previous subproblem’s result, instead of having to recompute the same problem again.

function fibonacci(n, memo = {}) {
  if(n in memo) return memo[n];

  if (n === 0 || n === 1) return n;

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);

  return memo[n];
}

Time and Space Complexity

The above method uses O(n) time and space.

I hope you found this helpful. If you want to learn more about memoization, do check out the materials below. Happy coding!

Memoization - Interview Cake
Fibonacci - Leetcode

Destination Tabulation

Katherine Kelly — Sat, 01 Aug 2020 06:59:45 +0000

Welcome to my post on tabulation, where the destination is learning about tabulation (sorry, no tropical vacation)!

Tabulation

Tabulation is an iterative dynamic programming strategy used to efficiently solve large problems by breaking down the problem into smaller problems. It’s considered a bottom up approach since it solves all of the related subproblems first before building larger values from these and solving the the big problem last.

The results of each solved subproblem is stored in a table of n elements (hence its moniker tabulation, but it’s just a plain old array), with the first element in the table being the smallest subproblem and the last element representing the largest and final answer.

What’s Dynamic Programming?

Dynamic programming (DP) is an algorithmic technique used to efficiently solve an optimization problem by breaking the problem down into smaller subproblems. Efficiency is achieved by avoiding duplication calculations and only solving each subproblem once by storing its result in an additional data structure. Each subsequent subproblem will build on the previous subproblem’s result until you get to the last and final problem. There are two DP strategies: tabulation and memoization.

Keep in mind that utilizing DP does not apply for every problem. It can only be used if the problem has a sense of repetitive subproblems that overlap. It can be tricky at first to spot whether a problem should be solved using DP, but more practice and exposure to problems will get you there.

Leetcode: Climbing Stairs

To illustrate tabulation, I’ll walk through the following Leetcode problem: Climbing Stairs.

You are climbing a stair case. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct
ways can you climb to the top?

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: 4
Output: 5
Explanation: There are 5 ways to climb to the top.
1. 1 step + 1 step + 1 step + 1 step
2. 2 steps + 1 step + 1 step
3. 2 steps + 2 steps
4. 1 step + 1 step + 2 steps
5. 1 step + 2 step + 1 step

In thinking about our problem, we know it will be n steps to the top but we need to figure out the distinct ways to reach the top. You can only take 1 step or 2 steps each time.

Reaching the i^th step can be done in one of two ways:

Take a single step from (i - 1)^th step
Take a step of two from (i - 2)^th step

The total number of ways to reach i^th is equal to the sum of the ways of reaching (i - 1)^th step and ways of reaching (i - 2)^th step.

Set Up Your Table

The first thing you'll want to do is set up your table array based on the size of your input. We can do this two ways:

create the array off the bat with n elements and filling all values with 0 (since we know we'll be dealing with integers). Then we'll want to initialize some values in the table that will answer trivially small subproblems and edge cases (usually the first entry in the problem).

const n = 4;
const table = new Array(n).fill(0);
// [0, 0, 0, 0]
table[1] = 1;
table[2] = 2; // with 2 steps, there are 2 ways to climb to the top

declare the array with the smallest subproblems already included. I'll go with this method since arrays are dynamic in JavaScript and it'll be a bit less code.

const table = [0, 1, 2]; 
// initialized it to include `n = 2`'s subproblem result or else
// it would throw off the below implementation

The following represents what our initialized table looks like:

i	0	1	2	3	4
table[i]	0	1	2

Iterate Through N to Fill in Remaining Table Values

We'll then want to iterate using a for loop starting at 3 since we've already pre-populated the array to account for the earlier subproblems. We'll want to terminate the loop when i is less than or equal to n (i <= n) since the indexes of the array line up with n, as we took 0 steps into consideration.

In the loop, we'll populate the rest of our table by setting the value at index i to be the sum of the previous two subproblems at index i - 1 and i - 2.

Finally, we can return table[n] since it will be the largest final answer.

const climbingStairs = function(n) {
  const table = [0, 1, 2];

  for (let i = 3; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }
  return table[n];
}

console.log(climbingStairs(4)); // 5
console.log(climbingStairs(5)); // 8

Visual representation of getting 4:
table[4 - 1] + table[4 - 2]

i	0	1	2	3	4
table[i]	0	1	2	3	5

Time and Space Complexity

The above method uses O(n) time since it has a loop that runs n - 3 times.

The space complexity above is also O(n) because it stores a full array of the subproblems.

There is a way to optimize on space down to O(1) by not storing the full array. We'll only need to save the last two subproblems to help calculate the next one.

const climbingStairs = function(n) {

  // handling edge cases if n equals 0 or 1
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  }

  // create last and secondLast variables with 2 and 1, respectively
  // to handle edge cases
  let secondLast = 1; // 
  let last = 2;

  for (let i = 3; i <= n; i++) {
    // initialize temp variable to store last's current value as
   // we'll be reassigning last to the the sum of last + secondLast
    const temp = last;
    last = last + secondLast;
    secondLast = temp;
  }
  return last;
}

console.log(climbingStairs(5)); // 8

I hope you found this helpful. Next week, I’ll look at memoization, the other dynamic programming strategy that utilizes recursion and a hash map. Until then, happy coding!

Climbing Stairs - Leetcode
What is Dynamic Programming? - Educative.io
Tabulation - App Academy
Dynamic Programming - Wikipedia

Trie Like Pie

Katherine Kelly — Fri, 24 Jul 2020 07:45:09 +0000

If you're not familiar with tries and want to learn more, then this post is for you! A trie is like pie in that both rhyme* but that’s where the similarities end. A trie is a tree-like data structure used to efficiently store a set of strings. It’s also commonly referred to as a prefix tree or digital tree.

*and it’s a helpful mnemonic since I initially pronounced trie like ‘tree’. Fun fact- trie was coined by Edward Fredkin who pronounced it like 'tree' as in 're-trie-val', but others have since pronounced it as 'try' to distinguish it from 'tree'.

How a Trie Works

A trie is known as a prefix tree because it builds a path from the root of the tree to any node that represents a prefix for at least one string in the set.

The root is associated with an empty string, and all of the descendants of a node will have a common prefix of the string associated with that node. The final leaf in the path acts as a terminal node and results in a complete word (a word recognized by the trie must begin at the root and end at a terminal node).

Below is a trie visualized with the darker shade representing a terminal node/completed word.

When to Use a Trie

It’s useful to use a trie if you have a dictionary of words and you want an efficient insert and lookup to see if a word exists in the dictionary (i.e. a spellcheck or predictive text program).

Big O Time and Space Complexity

The worst case time complexity for both inserting and searching is O(m) where m is the length of the word. Complexity depends on how long the given word is and not the number of words stored in the trie, as we will only be traveling a single path from root to terminal node.

The space complexity for a trie will depend on how often prefixes are shared among words. The guaranteed worst case is O(m * n) where m is the length of the word and n is the number of words.

Implementing a Trie

We can implement a trie by creating both a Trie and Node class.

Node Class

The Node class will not store values within the nodes of a trie, which is different than other tree structures. Instead, we will store values for each edge that leaves a node. Since a trie is not a binary tree, it can have any number of children, which will be stored in an Object.

The isTerminal property will keep track of whether the node represents a terminal node. Remember, a word is only recognized by the trie if it begins at the root and ends at a terminal node (last leaf in the path).

class Node {
  constructor() {
    this.children = {};
    this.isTerminal = false;
  }
}

Trie Class

For a basic Trie class implementation, we'll include insert() and search() functions.

insert()

When inserting a word into the Trie, we'll need to check if the first character of the word already exists as an edge. If the edge exists, then we'll want to use it to add our existing word. If the edge does not exist, then we'll need to create the edge. The method below takes a recursive approach to add the new destination node along with the remaining characters.

class Trie {
  constructor() {
    this.root = new Node(); 
  }

  insert(word, root = this.root) {
    let char = word[0];

    // if current root has no edge for the char, then we create a
    // new edge for char and point it to a new destination node
    if (!root.children[char]) {
      root.children[char] = new Node();
    }

    // if there are no more remaining chars in word, we can
    // mark the destination node's terminal property as true
    if (word.length === 1) {
      root.children[char].isTerminal = true;
    // otherwise, recursively insert the remaining chars 
    // into destination nodes
    } else {
      this.insert(word.slice(1), root.children[char]);
    }
  } 
}

search()

The search() function will tell us whether a word is recognized by the trie. This happens with a traversal down the tree. We start at the root and continually travel through the edges that correspond to the front character of the string.

The word is recognized by the trie if we traverse down to a terminal node and the string is empty. A word would not be recognized by the trie if the string is empty and we end up on a non-terminal node or if there is a character without an associated edge.

// ...

search(word, root = this.root) {
  // if we've gone through all the characters in word
  if (word.length === 0) {
    // word exists if the current node is a terminal node
    if (root.isTerminal) {
      return true;
    } else {
      return false;
    }

  // taking the first character of the string
  let char = word[0];
  // if an edge exists for this char, then recursively check the
  // subtree at the edge's destination with the remaining chars
  if (root.children[char]) {
    return this.search(word.slice(1), root.children[letter]);
  } else {
    return false;
  }
}

The full code implementation is:

Tries may not seem like a super useful or common data structure but they are great for dictionary and word lookup problems. Also, tries can come up in interviews so it's good to get familiar with it. Happy coding and do enjoy some pie with your trie learning!

Resources
Trie - Interview Cake
Trie - Wikipedia
Tries - App Academy
Implement Trie (Prefix Tree) - Leetcode

CAP Theorem: Why You Can't Have It All

Katherine Kelly — Sat, 18 Jul 2020 05:40:43 +0000

I've been learning the basics of tackling system design problems to better prepare myself for these types of questions in interviews. As a junior developer, system design interviews can be intimidating and difficult to feel adequately prepared for because of the open-ended nature and lack of experience/opportunities to put the skills into practice. Developing large-scale systems is no simple feat!

In previous posts, I've written about SQL vs. NoSQL and caching, which are small components to designing large-scale systems. Perhaps I'll make all of these posts into a series someday, titled something like "The (Very) Small Building Blocks of a System Design Interview Written For Beginners By a Beginner."

Thanks for coming to my TED talk! But I do have a topic I want to cover today: CAP Theorem. CAP stands for consistency, availability, and partition tolerance. CAP theorem is the concept that it is impossible for a distributed software system to guarantee all three properties; you can only have two of the three.

When designing your distributed data store, you will have to consider tradeoffs and the needs of your system so you can choose a data management system that will deliver on the properties your application needs most.

Distributed System

What's a distributed system? It's a network that stores data on more than one node (either a physical or virtual machine) at the same time. All cloud applications are distributed systems.

Consistency

Clients will see the same data at the same time, regardless of which node they connect to.

To achieve this, when data is written to one node, it must be immediately replicated or forwarded to all of the other nodes in the system before the write is considered a "success".

Availability

If a client makes a request for data, they will get a response even if one or more nodes are down. All of the remaining working nodes in the system will return a valid response for any request.

This is achieved by replicating data across different servers.

Partition Tolerance

A partition is when there is a message loss or partial failure between two nodes.

The system will continue to work despite the partition and can sustain any amount of network failure that doesn't result in a failure of the entire network.

To achieve this, data must be sufficiently replicated across a combination of nodes and networks to keep the system up and running through sporadic outages.

Selecting a NoSQL Database

Non-relational/NoSQL databases are the best option for a distributed network application because of its horizontal scalability and distributed nature by design (can quickly scale across a vast network with a lot of interconnected nodes).

NoSQL databases can be classified by the two CAP properties they support:

CP Database (Consistency, Partition Tolerance)

CP databases will deliver on consistency and partition tolerance, sacrificing availability. A guarantee of availability cannot occur because if a partition happens between any nodes, the system will have to shut down the inconsistent node until the partition resolves.

MongoDB is a common NoSQL database that stores data as BSON (binary JSON) documents. It follows a single-master set up where only one primary node receives all the write operations, and the other nodes in the same replica set are secondary nodes that replicate the primary node's data. Typically used for big data and real-time apps running at several different locations, MongoDB follows the CP classification as it resolves network partitions by maintaining consistency at the expense of availability.

AP Database (Availability, Partition Tolerance)

AP databases deliver on availability and partition tolerance, sacrificing consistency. A guarantee of consistency can't occur because if a partition happens, all nodes remain available but there is a chance that the affected node may deliver stale data.

Cassandra is another popular NoSQL database that stores data in a wide-column format. Without a master node (unlike Mongo), all nodes have to be available continuously, and as such it follows the AP classification. It is highly performant at the cost of consistency, though Cassandra does provide consistency eventually.

CA Database (Consistency, Availability)

CA databases can deliver on consistency and availability, but cannot accommodate partition tolerance. CA databases are relational/SQL databases.

As with any of your system design needs, you will have to consider all of the benefits of the different database stores and tradeoffs that will work best for your problem. You should also clarify with the interviewer what type of guarantee they are looking for in the system. Talking through the tradeoffs at every stage is key in a system design interview. Understanding the basics is a great first step in getting more comfortable with system design questions.

Resources
CAP Theorem - Grokking the System Design Interview (paid resource)
CAP Theorem - IBM

Rails Caching, Pt. 2

Katherine Kelly — Fri, 10 Jul 2020 07:04:25 +0000

Last week I covered some Ruby on Rails caching basics such as page, action, and fragment caching and how you can set up a cache on your application in development to test it out. Rails offers caching features out of the box so it's simple to dip your toe into the world of caching.

For this post, I wanted to look at Cache Stores, as well as some other caching techniques I didn't cover last week.

Other Rails Caching Techniques

I previously covered page caching (cached endpoints are short-circuited by the web server and don't go through your Rails stack but not good with before filters like authentication), action caching (web request hits the Rails stack so those before filters can be run before cache data is served), and fragment caching (default Rails caching that's good for fragments and partials).

Here a few more caching methods:

Russian Doll Caching

Russian doll caching builds on fragment caching and allows for nesting cached fragments inside other cached fragments. Using the touch method can tie the models together so that any action that changes updated_at for the nested/inner record will also change it for the associated/outer record, making sure the cache is updated and not providing any stale data.

class Destination < Application record
  has_many :activities
end

class Activity < ApplicationRecord
  belongs_to :destination, touch: true
end

<% cache destination do %>
  <% render destination.activities %>
<% end %>

SQL Caching

Rails features query caching that caches the result set returned by each query. Returned results from the query are stored in a query cache in memory. If the same query is made again, Rails won't query the database again but pull the result from memory. It's important to keep in mind that the query caches are created at the start of an action and destroyed at the end of that action. If you require queries to be stored in a more persistent manner, you can do so with low level caching.

Low-level Caching

There may be a situation where you'd rather cache certain values or a query instead of just view fragments. Rails caching works great for storing any kind of information. This is where low-level caching comes in.

A simple and effective way to implement low-level caching is using Rails.cache.fetch. This method does both reading and writing to the cache.

If passed only one argument, the key is fetched and the value from the cache is returned
If a block is passed in, the block will only be executed in the event of a cache miss (the return value of the block will be written to the cache and attached to the key passed in, and the return value will be returned)

class Destination < ApplicationRecord
  def top_activity
    Rails.cache.fetch("{#cache_key_with_version}/
      top_activity", expires_in: 12.hours) do
        Activities::API.find_activity(id)
    end
  end
end

When using low-level caching for instance level information, you will need to generate a cache key. cache_key_with_version method will generate a string key based on the model's class name, id, and updated_at attributes, something like destinations/100-1-202006026193031061005000/top_activity.

Cache Stores

As your cached data has to live somewhere, there are many options for cache stores. Rails has a default cache store that's easy to use though with limitations. If you have caching already toggled on (as referenced in the development config/environments/*.rb file) the cache will be implemented by default with a default bounded size of 32Mb. You can pass in a :size option to increase the capacity to the initializer if you wish:

config.cache_store = :memory_store, { size: 64.megabytes }

For small, low traffic sites with only a handful of server processes and those in development and test environments, this default cache can work well. However, this store is not going to cut it for a large application deployment.

MemCacheStore

MemCacheStore utilizes Danga's memcached server and serves as a centralized cache for your app. By default, Rails uses the bundled dalli gem. This is also the most popular cache store choice for production websites due to its high performance and redundancy with a single, shared cache cluster.

The cache will be initialized in the relevant config/environments/*.rb file. In config/environments/production.rb you can uncomment out the following:

  # Use a different cache store in production.
  # config.cache_store = :mem_cache_store

You'll need to specify the addresses for all memcached servers in your cluster. If no addresses are provided, the default assumption is that memcached is running on localhost on the default port, which is not an ideal situation for larger websites.

config.cache_store = :mem_cache_store, "cache-
1.travelexample.com", "cache-2.travelexample.com"

RedisCacheStore

Another cache store option is RedisCacheStore. The Redis cache store makes use of Redis support for automatic eviction when it reaches max memory, letting it behave like a Memcached cache server.

You'll need to add the redis gem to your Gemfile. There is also additional support you can enable with the faster hiredis connection library by adding its Ruby wrapper to your Gemfile. The Redis cache store will automatically require and use hiredis if it's available. And then you'll want to add the configuration to the relevant config/environments/*.rb file.

config.cache_store = :redis_cache_store, { url: ENV['REDIS_URL'] }

Other Cache Stores

There are other cache stores available such as MemoryStore or FileStore but you can read more about these and get more information on Rails caching at Rails Guides's Caching With Rails.

Happy caching!

Resources
Caching With Rails: An Overview - Rails Guides
Caching Strategies for Rails - Heroku

Rails Caching, Pt. 1

Katherine Kelly — Fri, 03 Jul 2020 22:57:17 +0000

I've been exploring caching recently, mostly at a high level to better understand the importance of a cache and what goes on behind the scenes (check out Cache Me If You Can and Implementing an LRU Cache for those posts!).

It's widely understood that a cache is often the most effective way to boost an application's performance. Web sites that feature a single server and a single database can sustain a load of thousands of concurrent users with caching.

If you have a Ruby on Rails application, Rails offers a set of caching features out of the box. This post is going to be part one of a dive into the most common cache techniques and how you can implement caching in development to check it out!

Caching in Development

Since caching is only enabled by default in the production environment, we'll need to enable caching directly in the local development environment.

But, Rails makes it super easy now (on Rails 5 and above) to set up caching in development. You just need to run rails dev:cache to toggle caching on and off and if it's turned on, Rails will create a tmp/caching-dev.txt file. You also won't need to restart the server, as one would have had to do with older versions of Rails. Here is what it looks like in config/environments/development.rb:

# Enable/disable caching. By default caching is disabled.
  # Run rails dev:cache to toggle caching.
  if Rails.root.join('tmp', 'caching-dev.txt').exist?
    config.action_controller.perform_caching = true
    config.action_controller.enable_fragment_cache_logging = true

    config.cache_store = :memory_store
    config.public_file_server.headers = {
      'Cache-Control' => "public, max-age=#{2.days.to_i}"
    }
  else
    config.action_controller.perform_caching = false

    config.cache_store = :null_store
  end

Rails Caching Techniques

In Rails, there are three different types of caching techniques: page, action, and fragment caching.

Rails provides fragment caching by default. To use page and action caching, you'll have to add these specific actionpack gems to our Gemfile.

Page Caching

Page caching is a cache approach that stores response bodies in files that the web server can access.

A request to endpoint A arrives
Its response is determined and gets stored in a file B
Next time A is requested, the web server sends B directly

It only applies to GET or HEAD requests with response code 200. This can result in a quick response because the cached endpoints are short-circuited by the web server and don't even reach your Rails application. However, this approach only works for pages that don't need to go through the entire Rails stack. Anything that involves authentication and account-based systems are not good contenders.

As of Rails 4, page caching has been removed, but you can access and use it by adding actionpack-page_caching to your Gemfile.

Action Caching

Action caching is similar to page caching except the incoming web request hits the Rails stack through Action Pack so that any authentication and before filters can be run before the data in the cache is served.

As of Rails 4, action caching has been removed, but you can access and use it by adding actionpack-action_caching to your Gemfile.

Fragment Caching

By default, Rails offers fragment caching. Depending on the needs of your web application, you can utilize fragment caching to cache different parts of the page. This allows flexibility in what parts you want cached and when it should expire. Fragment caching lets a fragment of view logic (partials, widgets, etc.) to be wrapped in a cache block and served out of the cache store when the next request is made.

As an example, if you have a travel app and wanted to cache each destination on a page, the code could like something like this:

<% @destinations.each do |destination| %>
  <% cache destination do %>
    <% render destination %>
  <% end %>
<% end %>

Rails will write a new cache entry with a unique key when your app gets its first request to this page. The key will resemble the following:

app/views/destinations/
1-202006026193031061005000/bea67108094918eeba42cd4a6e786901

The number after destinations is the product_id followed by a timestamp value of the updated_at attribute of the destination record. This timestamp ensures that Rails is not serving stale data. If updated_at has changed, a new key will be generated and Rails will write a new cache to that key. The old key won't be used again. This is key-based expiration in a nutshell.

If the view fragment itself changes (if the HTML changes) the cache fragment will also be expired.

You can also conditionally cache a fragment using cache_if or cache_unless:

<% cache_if beachside?, destination do %>
  <%= render destination %>
<% end %>

Collection Caching

The render method also allows you to cache individual templates rendered for a collection. The below example can read all cache templates at once instead of one by one like above using each.

<% render partial: 'destinations/destination', 
collection: @destinations, cached: true %>

Tested

When I played around with implementing the cache, my initial page load after all of the database queries was 316ms:

Write fragment views/destinations/show:
ea9a60feb104fccbb55d6feb00a7dcb8/hacks/265-20200528222447858679 (0.1ms)

Rendered destinations/show.html.erb within layouts/
application (Duration: 187.9ms | Allocations: 26579)

Completed 200 OK in 316ms (Views: 141.6ms | ActiveRecord:
120.6ms | Allocations: 65663)

When I reloaded the page, the time was cut down to 62ms and the fragments were taken from the cache!

...
Read fragment views/destinations/show:ea9a60feb104fccbb55d6feb00a7dcb8
/hacks/265-20200528222447858679 (0.2ms)

Rendered destinations/show.html.erb within layouts/
application (Duration: 8.2ms | Allocations: 1860)

Completed 200 OK in 62ms (Views: 56.9ms | 
ActiveRecord: 2.0ms | Allocations: 29929)

Next week, I'm going to look into Rails Cache Stores as well as other caching techniques I didn't cover here. (Edit: Rails Caching, Pt. 2 is up!)

Happy caching!

Resources
Caching With Rails: An Overview - Rails Guides
Caching Strategies for Rails - Heroku

Implementing an LRU Cache

Katherine Kelly — Sat, 27 Jun 2020 23:47:07 +0000

Last week, I wrote about caching and discussed different caching approaches and ways to keep your cache data in sync with the database. A cache is a super effective way to make your application or website more performant, as it can store frequently requested data in a fast-retrieval, data storage layer instead of querying the database every time.

However, a cache is limited in size and memory. To maintain what gets stored in memory, there needs to be a way for the cache to regulate what goes in (cached) and what goes out (evicted).

This post is dedicated to a common cache policy (that often comes up in coding interviews): the Least Recently Used (LRU) cache. An LRU cache will discard the least recently used item in the cache to make space for new item(s).

Implementation

Implementing a Least Recently Used (LRU) cache traditionally involves a hash map and a doubly linked list.

The linked list would have the most-recently used item at the head of the list and the least-recently used item stored at the tail.

I love Interview Cake's examples of visualizing an LRU cache. Below is the doubly linked list illustrated sweetly (see what I did there?):

Via Interview Cake

At this point, getting the least-recently used item would take O(1) time since we can look at the tail, but accessing any other specific item that's not the tail or head would take O(n) time since we would have to walk through the entire list.

To make lookups efficient, a hash map is used to map items to linked list nodes. More sweetness from Interview Cake illustrating this:

Via Interview Cake

Access and Eviction

Below are the following steps to go through each time an item is accessed in the cache.

Look up the item in the hash map
If the item is the hash map, hooray, it's a "cache hit" and it's already in the cache
1. Find the corresponding linked list node with the hash map
2. Move the item's linked list node to the head of the linked list. It's now the most recently used item.
If the item is not in the hash map, boo, it's a "cache miss" and you'll have to load the item into the cache
1. Cache full? Then an item will have to be evicted (evict the LRU cache item, the tail, by removing it from the linked list and hash map)
2. Create a new linked list node for the item and insert it at the head of the linked list
3. Add the item to the hash map, with the new node as the value

Code

Like I mentioned above, implementing an LRU cache can often come up in coding interviews. Leetcode features an LRU cache problem where you have to implement get and put operations for the cache.

get(key) gets the value of the key if the key exists in the cache
put(key, value) sets or inserts the value if the key is not already present
If the cache has reached its capacity, it should invalidate the least recently used item before inserting a new item.

In my solution below, it features a few classes including LRUCache, DoublyLinkedList, and Node.

Happy coding!

Resources
LRU Cache - Interview Cake
LRU Cache - Leetcode

Cache Me If You Can

Katherine Kelly — Fri, 19 Jun 2020 05:16:06 +0000

Caching is an important process that can improve your website or application’s performance. At a high level, a cache is a data storage layer that acts like short-term memory by storing data that has been recently requested, taking advantage of the locality of reference principle in which recently requested data will likely be requested again. A cache’s main purpose is to increase data retrieval performance by reducing the number of times the main database/storage layer will need to be queried.

In this post, I wanted to look into the basics of a cache such as the different approaches to caching, how its data remains consistent with data in a database, and the different eviction policies that determine how things in a cache are removed to free up space.

Cache Approaches

Application caching and database caching are the two main approaches to caching, though most systems will rely greatly on both. Application caching will require direct integration in the application’s code. It typically works by checking if the data requested is in the cache. If not, it will retrieve the data from the database and then write the value into the cache.

Via http://lethain.com

The opposite aspect is database caching, where the cache is placed between the application and the database.

Via http://lethain.com

Cache Invalidation

There will need to be maintenance to ensure the data located in the cache is consistent with the database, as the database is the single source of truth. If your data is modified in the database, it should be invalidated in the cache. Below are the main schemes used for cache invalidation:

Write-through cache: data is written into the cache and the corresponding database at the same time
- pros: fast retrieval in the cache and complete data consistency
- cons: higher latency for write operations, as the work is done twice
Write-around cache: data is only written to the database, bypassing the cache
- pros: reduces the cache from being flooded with write operations that won’t be read
- cons: may create a “cache miss” for a read request that will have to be read from the slower backend storage and face higher latency
Write-back cache: data is only written to the cache initially and then written to permanent storage after specified intervals or under specific conditions
- pros: low latency and high throughput for a write-intensive application
- cons: risk of data loss and inconsistency in the event of a crash
Read-through cache: the cache sits between the application and database, and the application only requests data from the cache
- pros: good for read-heavy workloads
- cons: higher latency and results in a “cache miss” the first time
Cache Aside: the cache is sitting aside the database and the cache will be checked first to see if the data exists. If not, the application will request data from the database and then update to the cache
- pros: simple implementation, good for read-heavy workloads
- cons: possible data inconsistency and results in a “cache miss” the first time

Cache Eviction Policies

A cache is limited in its size and memory in order to remain performant. In order to maintain what is stored in local memory, there will need to be a way for the cache to regulate what goes in (cached) and what goes out (evicted).

The most common cache eviction polices are:

First In First Out (FIFO): cache acts like a queue and removes the first block accessed without considering how often or how many times it was accessed before
Last In First Out (LIFO): cache acts like a stack and evicts the block accessed most recently without considering how often or how many times it was accessed before
Least Recently Used (LRU): cache will discard the least recently used item
Most Recently Used (MRU): cache will discard the most recently used item
Least Frequently Used (LFU): cache will count how often an item is needed and the items that are least used are discarded first
Random Replacement (RR): cache will randomly select an item and discard it to make space when necessary

There is a lot more about caching I couldn't cover so please utilize the resources below for further reading. Next week, I’ll look at implementing an LRU cache. Stay tuned!

Resources
Cache Eviction Policies - Grokking the System Design Interview (paid resource)
Introduction to Architecting Systems
Cache(computing)
Things You Should Know About Database Caching

ACID Properties

Katherine Kelly — Sat, 13 Jun 2020 08:27:44 +0000

Last week, I wrote about SQL and NoSQL databases. One of the main differences between the database types is ACID compliancy. ACID stands for atomicity, consistency, isolation, durability, and describes a set of transaction properties that guarantees database validity even if an error occurs. A majority of SQL/relational databases are ACID compliant databases. I wanted to learn more about ACID properties and why it's an important consideration when deciding what database to use.

Transactions

A quick note about transactions. A transaction is a collection of instructions. All transactions must follow ACID properties in order to guarantee database validity. I'll use banking transactions between customers below to illustrate the 4 properties.

Atomicity

Atomicity ensures that each transaction is treated as a single unit that follows the "all or nothing" rule; a transaction either happens completely or not at all. If any part of the transaction fails, the entire transaction will fail.

For example, customer A wants to withdraw $100 from their account and then deposit it into customer B's account. If any of the instructions fail (insufficient funds or server crashes, etc.), the transaction will fail and any changes will be rolled back.

Consistency

Consistency guarantees that a transaction must be valid before it gets written to the database. A transaction is valid when it follows all of the defined rules, including constraints, cascades, triggers, and any combination of these. Inconsistent transactions will result in the database being rolled back to a previous state that complies with the given database rules.

If customer A wants to withdraw $100 from their account but only has $50 in their account, consistency prevents them from withdrawing the funds and the transaction will be aborted.

Isolation

As transactions are typically executed at the same time (i.e. multiple transactions that read and write to a table at the same time), isolation sees that each transaction acts as an individual transaction and would receive the same state if the transactions were executed sequentially. Isolation is important for concurrency control.

If customer C has an account balance of $1000 that both customers A and B can make withdrawals from (say $50 and $100, respectively), one of the customers will have to wait until the other customer transaction is finished, in order to avoid inconsistent data.

Durability

Durability ensures that once a transaction has been completed and committed, it will remain committed even in the event of a system failure (crash or power failure). These completed transactions are stored in non-volatile memory.

If customer A successfully deposited $500 in their account, this transaction should not disappear if any system failure occurs.

As I mentioned above, a majority of SQL/relational databases are ACID compliant. NoSQL databases tend to sacrifice ACID compliancy for faster performance. There is strong data reliability and a guarantee that the transactions are safe.

There may be clear cut scenarios where an ACID-compliant database is the best solution, such as e-commerce, healthcare, financial services apps (when data integrity is of the utmost concern). Yet, there other times where you may want to take other factors into consideration in deciding between a SQL or NoSQL database.

Now fully understanding what ACID stands for, I feel better informed when having to make database decisions.

Resources
ACID - Wikipedia
Atomicity Consistency Isolation Durability (ACID) - Techopedia
What are ACID properties in a database? - Educative

To SQL or NoSQL

Katherine Kelly — Sat, 06 Jun 2020 01:22:05 +0000

When working on personal projects or large-scale applications, developers will often have to set up a database layer to persist the data. With all of the different databases out there, there is not a one-size-fits-all database solution and what you choose will depend on your project needs and any tradeoffs considered.

Below are the two main types of databases.

SQL / relational databases - data is structured and database is accessed with SQL (Structured Query Language)
NoSQL / non-relational databases - data is unstructured and database is developed to scale and handle many queries

Here’s a side-by-side breakdown of the two types:

	SQL	NoSQL
STORAGE	Data is structured and stored in tables Each row contains information about one entity (record) Each column contains separate data points (attributes)	Data is unstructured, and there are different types of NoSQL databases with different storage models Document Databases: Data is stored in documents and the documents are grouped together in collections. Each document can have a different structure. Key-Value Stores: Data is stored in an array of key-value pairs, with the key acting as an attribute name that is linked to a value Wide-Column Databases: Instead of "tables", columnar databases have column families, which are containers for rows. These databases are best used for analyzing large datasets. Graph Databases: Data is saved in graph structures with nodes (representing entities), properties (information about the entities), and lines (connections between the entities). These are best used to store data whose relations are best represented in a graph.
DATABASES	Open Source: PostgreSQL, MySQL, SQLite, MariaDB Other: Oracle DB, MS SQL Server	Document Databases: MongoDB Key-Value Stores: Redis, Dynamo, Voldemort Wide-Column Databases: Cassandra, HBase Graph Databases: Neo4J, InfiniteGraph
SCHEMA	Fixed schema Columns must be decided on and set up before you add any entries/rows Each row must have data for each column Schema can be altered later, but it will modify the entire database and will go offline to update	Dynamic schema New columns can be added on the fly Each entry/row equivalent doesn't have to contain data for each column equivalent
QUERYING	Uses SQL to define and manipulate the data	Queries are focused on a collection of documents, sometimes called UnQL (Unstructured Query Language)
SCALABILITY	Database can scale vertically Vertical scaling is more costly as it needs more horsepower (CPU, RAM) of the hardware to increase capacity Horizontal scaling across multiple servers is possible but it's challenging and time consuming	Database can scale horizontally Horizontal scaling needs more machines (servers) in the NoSQL database infrastructure to increase capacity, which is cheaper because servers/hardware/cloud hosting is cheap
RELIABILITY / ACID COMPLIANCY (Atomicity, Consistency, Isolation, Durability)	Majority of SQL databases are ACID compliant Strong data reliability and safe guarantee of performing transactions	Majority of NoSQL databases sacrifice ACID compliance for performance and scalability
WHEN TO USE	When you need to ensure ACID compliance (e-commerce and financial apps, etc) The data is structured, unchanging, consistent Business is not facing hyper-fast growth that requires more servers	When you don’t want data to become a bottleneck Working with big data Storing large volumes of data that often have little structure (and can store different types of data together and on the fly) Taking advantage of cloud computing and storage because it’s cheaper and can spread out across multiple servers for scalability When rapid development is important

Resources
Grokking the System Design Interview - SQL vs. NoSQL (paid resource)
mongoDB - NoSQL vs SQL Databases

DEV Community: Katherine Kelly

Technical Interview Resources for the Junior Dev

Technical Phone Screen

Interview With Hiring Manager

Final Round Interview

Data Structures and Algorithms / Coding Challenges

System Design / Systems Architecture

Technical Knowledge and Judgement

Ruby on Rails

JavaScript

React

Systems

Object Oriented Design

Product Thinking

Git

Behavioral

Binary Search and How to Implement It

Time and Space Complexity

Recursive Approach | new subarrays, O(n) space

Recursive Approach | in-place, O(log n) space

Iterative Approach | in-place, O(1) space

Destination Memoization

Memoization

Leetcode: Fibonacci

Set Up Your Memo

Add a Base Case Condition

Recursive Call and Storing the Results

Time and Space Complexity

Destination Tabulation

Tabulation

What’s Dynamic Programming?

Leetcode: Climbing Stairs

Set Up Your Table

Iterate Through N to Fill in Remaining Table Values

Time and Space Complexity

Trie Like Pie

How a Trie Works

When to Use a Trie

Big O Time and Space Complexity

Implementing a Trie

Node Class

Trie Class

insert()

search()

CAP Theorem: Why You Can't Have It All

Distributed System

Consistency

Availability

Partition Tolerance

Selecting a NoSQL Database

CP Database (Consistency, Partition Tolerance)

AP Database (Availability, Partition Tolerance)

CA Database (Consistency, Availability)

Rails Caching, Pt. 2

Other Rails Caching Techniques

Russian Doll Caching

SQL Caching

Low-level Caching

Cache Stores

MemCacheStore

RedisCacheStore

Other Cache Stores

Rails Caching, Pt. 1

Caching in Development

Rails Caching Techniques

Page Caching

Action Caching

Fragment Caching

Collection Caching

Tested

Implementing an LRU Cache

Implementation

Access and Eviction

Code

Cache Me If You Can

Cache Approaches

Cache Invalidation

Cache Eviction Policies

ACID Properties

Transactions