OpenAI Breakthrough
OpenAI publishes a blog post on an amazing model that can generate images given text. Roblox raises a ton of money and plans to go public. Plus, an answer to our last Google Coding Interview question!
Hi Everyone!
Tech Dive
Our last tech dives were on Distributed Systems and Database Sharding!
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.
Tech Snippets
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.