Apple's M1 GPU
An awesome blog post on dissecting Apple's M1 GPU. Plus a System Design Interview question and a solution to yesterday's interview question on building a Queue with Stacks.
Our next tech dive will be on Bitcoin! Stay tuned.
Our last tech dives were on Distributed Systems and Database Sharding!
What is a Messaging Queue?
Why would one be necessary?
How would you build a Messaging Queue?
What features would you add in and what tradeoffs might you make?
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”
As a refresher, here’s the previous question
Build a class
MyQueue that implements a queue using two stacks.
Your class should implement the functions
The difference between a queue and a stack is that queues operate on a First In First Out basis while stacks operate on a First In Last Out basis.
This means that when you
push N items on to the stack and then
pop those N items off the stack, the order of the N items will be reversed. This is due to the Last In First Out property of stacks.
When you're working with a queue, however, the order of items is maintained. If you
enqueue N items on to a queue and then
dequeue those N items, the order of the items will remain the same. This is due to the First In First Out property of queues.
Therefore, if we want to build a queue with stacks, we have to design our data structure in a way so that the order of the items remains the same, rather than reversing (what a stack naturally does).
We can accomplish this by pushing each item inserted through two stacks. The first stack will reverse every item inserted. The second stack will reverse every item inserted again, which means going back to the original order.
So how do we implement this in code?
Whenever the user enqueues an item into our data structure, we'll
push it to
Now, when we want
dequeue items from our queue, we have to reverse the order.
We first call
_reverseStack which handles transfering all the items from
Then, we can
pop the last item in
stack2 and return that.
peek works the exact same way as
dequeue except we are just returning the last item in
stack2 instead of popping it off.
The time complexity is O(n) since each item is transferred from one stack to the other once. The space complexity is also O(n).