Hi Everyone!

Hope you’re all having a fantastic day.

Tech Dive

No tech dive for today unfortunately! Here’s the schedule for future tech dives

• Tomorrow - Database Sharding in Practice

Our last tech dive was on APIs!

• Request-Response APIs

• Event-Driven APIs

Industry News

GitHub Octoverse Report

Every year, GitHub analyzes their statistics and releases a State of the Octoverse report. It goes over interesting numbers on GitHub, that shed light on the developer ecosystem. Here are some of the most interesting data points.

Top Languages over the Years

JavaScript has remained steady as the most popular on GitHub for the past 6 years. The most interesting change is the rocketship that is TypeScript, going from below 10th in 2017 to a solid 4th place now.

Open Source Contribution

At the start of Stay-At-Home, there was a huge spike in open source project creation. While open source contribution has tapered down, it’s still at a much higher level than pre-pandemic.

Average time to merge pull request

Based off data analyzed from GitHub Enterprise, developers were typically committing code four times per day.

The time to first review is around 54 minutes and the time from last review to merge is 12 minutes. Overall, it takes an average of one hour and 36 minutes to merge a pull request.

You can view the full report here.

Interview Question

What does it mean to partition a database vertically vs. horizontally?

What is database sharding and why is it useful?

What are some different ways of implementing sharding?

We’ll send a detailed solution with our tech dive tomorrow, so make sure you move our emails to primary, so you don’t miss them!

Gmail users—move us to your primary inbox

• On your phone? Hit the 3 dots at top right corner, click "Move to" then "Primary"

• On desktop? Back out of this email then drag and drop this email into the "Primary" tab near the top left of your screen

Apple mail users—tap on our email address at the top of this email (next to "From:" on mobile) and click “Add to VIPs”

Previous Solution

As a refresher, here’s the previous question

You are given an m x n board of characters and an array of words.

Return all the words from the array that appear on the board.

Words must be constructed from letters of sequentially adjacent cells, where adjacent cells are either horizontally or vertically aligned. You cannot repeat letters.

Here’s the question in LeetCode.

Solution

We can solve this using a Trie and Depth First Search.

We first create a Trie that contains all the words in our array. This allows us to quickly check for found-words when we do our Depth First Search.

While doing our DFS, we utilize a “backtracking” type approach (remember that backtracking is a form of DFS).

For each letter, we check it’s 4 neighbors and see if they’re valid, haven’t already been visited (using a visited set that keeps track of coordinates we’ve been to), and would help us form a valid word (we can check this using our Trie).

If so, then we’ll add the letter to our visited set and then explore the neighbors for that letter. Once we explore the possibilities for the letter, we’ll backtrack and remove the letter from our visited set and continue on with the parent.

Whenever we come across a letter that completes a word in our array, we can add it to a set.

After going through the entire board with our DFS, we can convert the set of boardWords to an array and just return that.

Here’s a link to the REPL with Python 3 code.

If you have any feedback or questions, feel free to reply to this email!

Best,

Arpan