Hi Everyone!

Tech Dive

Our last tech dives were on Distributed Systems and Database Sharding!

• Distributed Systems Tech Dive

• Database Sharding Tech Dive

Industry News

OpenAI has released a blog post on their DALL·E model

This model takes in text as input and then generates an image that matches that text. OpenAI has not released the model, but they’ve provided samples of what kind of results they’ve gotten. Obviously, results like this tend to be a bit biased towards the model, but the results are still incredibly impressive.

Input - an armchair in the shape of an avocado

Model Output

Input - a store front that has the word ‘openai’ written on it

DALL·E is a 12 billion parameter version of OpenAI’s GPT-3 model and is a transformer-language model.

The dataset used to train the model was text-image pairs, but OpenAI doesn’t give any further details on how the dataset was obtained or exactly what it contained.

That information will probably be released when OpenAI publishes their paper on the model.

Here’s the blog post

Tech Snippets

• Roblox raises $520 million at $29.5 billion valuation. The company will go public through a Direct Listing.

• A Look At The CPU Security Mitigation Costs Three Years After Spectre/Meltdown

• Have a NodeJS server? Update it now!

Interview Question

Build a class MyQueue that implements a queue using two stacks.

Your class should implement the functions enqueue, dequeue, and peek.

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 previous question

You are given an array of k linked lists.

Each list is sorted in ascending order.

Merge all the linked lists into one sorted linked list and return it.

Here’s the question in LeetCode.

Solution

We can solve this question with Divide and Conquer.

We start with K linked lists and we merge every pair. This leaves us with k/2 remaining linked lists.

We can then recursively call our function on the remaining k/2 linked lists where we combine every pair to result in k/4 and so on.

We continue this process until we reach our final linked list.

The amount of times we have to repeat this process (until we reach the final linked list) is log(k) and we will traverse an average of N nodes per pairing where N is the average length of a linked list in the original array.

Therefore, our time complexity is N*log(k).

Here’s the solution in Python 3

For the solution, I decided to sacrifice on space complexity to make the solution more readable and easily understandable.

If you’d like to see the optimal solution (and to read other solutions), check this article out.