Hey Guys,

Hope you’re all having a fantastic day! Here’s your Tech Snippets, Interview Problem and Previous Solution for the day.

Tech Snippets

• Notion just released their API

  • Notion is a workspace tool that has grown ridiculously quickly over the past few years. It allows you to aggregate info, add Kanban boards, take notes in a collaborative manner and much, much more. It’s an incredibly powerful tool, so it’s difficult to summarize in one line.

  • After years of begging from the Notion community, the team has finally released an API! (Although, it’s still in beta)

  • This presents a ton of opportunities for any developers who are interested in building products on top of Notion. Notion has a massive user-base of tech savvy people, so there’s definitely a market for apps that extend the functionality of Notion!

  • One example of a tool built on Notion is super.so

    • super.so is a web app that turns Notion pages into a website with custom domains, analytics, fonts and other add ons.

    • The web app was built by Traf as a side project and it went from $0 to $26,000 in monthly revenue in 6 months.

  • Another example is a tool for courses on top of Notion

    • The default tool for course creators right now is teachable. However, many course creators (and course users) are big fans of Notion.

    • I saw a couple of people working on building a course platform on top of the Notion ecosystem, so this might be an interesting idea to explore.

• The Architecture of Open Source Applications

  • This is an awesome series of free books that teach you software architecture using practical examples (from open source code).

  • It consists of

    • The Architecture of Open Source Applications (Volumes I and II) - Goes through popular open source applications (Git, CMake, Audacity, HDFS, etc.) and talks about how they work.

    • The Performance of Open Source Applications - Case studies on how to find and fix bottlenecks in applications.

    • 500 Lines or Less - Experienced programmers take a challenging problem (Ex. Build an in-memory graph database) and walk you through how they’d solve it.

Interview Question

You are given a character array containing a set of words separated by whitespace. Your task is to modify that character array so that the words all appear in reverse order. Do this without using any extra space.

Example

input - ['A', 'l', 'i', 'c', 'e', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'B', 'o', 'b']

output - ['B', 'o', 'b', ' ', 'l', 'i', 'k', 'e', 's', ' ', 'A', 'l', 'i', 'c', 'e']

We’ll send a detailed solution 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 the 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 last question

How would you build a spelling correction system?

Possible Follow On Questions

• How would you check if a word is misspelled?

• How would you find possible suggestions?

• How would you rank the suggestions for the user?

Solution

The core idea for most spell-check systems is based on the Levenshtein distance.

You can think of Levenshtein distance as the minimum number of single-character edits (insertion, deletions or substitutions) required to change one word into the other word.

The Levenshtein distance from the intended word should be one or two edits. Therefore, if we can keep a hash table for all the words in our dictionary and then look for words that have a Levenshtein distance of 2 or less from the text, we can find the intended word. If the text is already in our dictionary, then it’s not misspelled.

The words in our dictionary that have a Levenshtein distance of 2 or less from our text may be too many to list out for the user. Therefore, it’s important that we rank our suggestions and implement a cut-off for the number of suggestions that we list. There are several ways of ranking our suggestions

• History of refinements - users often provide a great amount of data about the most likely misspellings by first entering a misspelled word and then correcting it. This data can be collected and then used to implement rankings.

• Typing errors model - spelling mistakes are usually a result of typing errors (typos). Therefore, these errors can be modeled based on the layout of a keyboard (mran -> mean)

• Phonetic modeling - spelling errors also happen when the user knows how the word sounds but doesn’t know the exact spelling. Therefore, we can map the text to phonemes and then find all the words that map to the same phonetic sequence.