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.
Hi Everyone!
Tech Dive
Our next tech dive will be on Bitcoin! Stay tuned.
Our last tech dives were on Distributed Systems and Database Sharding!
Tech Snippets
Interview Question
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”
Previous Solution
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 enqueue, dequeue, and peek.
Solution
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 stack1.
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 stack1 to stack2.
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).