[Solution]Problem 83: Packing Robots [Brilliant]
Variable Reduction, Ordering, Problem Solving
Hey, it’s your favorite cult leader here 🐱👤
On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those coding/tech/software engineering Interviews. 🔥🔥💹💹
To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!
p.s. you can learn more about the paid plan here.
How did you do?
This is a problem that has tripped up a surprising number of people I’ve worked with. And yes, this can be done through brute force. But that doesn’t really help you. If you learn how to work through this systematically, you can apply that system elsewhere.
Problem
The robots are being packed into a container for their next evaluation. Which arrangement meets these packing requirements?
Loy is in one of the two middle spaces.
Mig is left of Lex and right of Rae.
Rae is directly next to Mig.
Make sure you practice such questions quickly. Your interviews will likely contain a couple of these (especially now that more and more people are falling out of love with Leetcode). In actual interviews, you can skip a few steps to save time. But when studying these questions, mastering the right methods will help you solve much harder questions. I covered this principle in depth in the post- How to Use Easy Questions, so make sure you read that if you haven’t already.
Step 1: Reading the Problem
One of the first things that trips people up is not thoroughly reading the problem. This means they end up with incorrect assumptions and attempt to build solutions on top of that. The worst thing is, these assumptions are the hardest thing to spot, so they lose out on a question that should’ve been easy money. If you’ve ever struggled with a question, looked at the solution, and cursed yourself for missing something obvious, you’ve likely had this happen to you.
So what is this nasty assumption people make? Read the constraints-
Loy is in one of the two middle spaces.
Mig is left of Lex and right of Rae.
Rae is directly next to Mig.
Notice that this makes one thing clear- a bot doesn’t have to be adjacent to the another to be to one side of it. When adjacency is required, this is explictly stated (rule 3).
Thus, Mig →X→ Lex is a valid ordering (we are only considering rule 2 for now).
This is something that a lot of people I have mock-interviewed overlook. In a high-pressure, timed scenario like an interview, it’s easy to miss these small details. As I’ve shown many times in this newsletter, tough questions often have hints baked into their wording (this question, a favorite of Google, is a good example). You want to get into the habit of reading through questions in a lot of detail.
With that out of the way, what can we do next? There is a way to simplify the problem, a lot. I’m about to show you a technique that will drop the complexity of such problems by a whole order of magnitude.
Step 2: Grouping the Best Friends
Each robot in this list is another factor to consider. Thus, if you could drop the number of robots, your solution becomes exponentially easier. The key is in getting rid of pieces without losing information. So how do we do this?
In our case, one way to do so to look see if there are any robots that go in groups. A group would be defined as the following-
If I can use the position of bot1 to deduce the position of bot2, then bots 1 and 2 are in the same group
-Group Theory is something you should study if you want to improve your OOP and design. Learn more about it here
In our case rules 3 tells us that Mig and Rae are adjacent. Thus we know that they go together. Furthermore, we know that Mig is to the right of Rae. Thus, we know that no matter what, the two bots will always be positioned as - Mig→Rae. We can treat them as one robot (just taking up two spaces). Bringing down the number of orderings by a factor of n (we go from n! to (n-1)!).
Grouping like components may seem trivial here, but it is a very powerful technique. When you try to model complex systems, you will most likely have simpler representations first. The best simplifications will be the models where you group variables/components that behave together. It’s something you see all the time in designing complex systems (even in AI). More on this soon.
So what do we do with our group? We can use it to filter through.
Step 3: Filtering out the bad solutions
Our grouping actually cuts out a lot of guesswork. We know the following-
Rae can’t be in the second spot, since this would put Mig in spot 3. Thus, Loy would not be able to occupy any middle spot, violating the rules.
Rae can’t be in spot 3, since that puts Mig in the rightmost spot. Mig has to be to the left of Lex.
Rae can’t be in spot 4 either, since Mig won’t be to the right.
This tells us that we have the following ordering-
Rae→Mig→X→X
Now, fitting Loy, we can easily solve this-
Rae→Mig→Loy→Lex.
And we’re done. Give yourself a pat on your back if you got this right. And make sure you master the grouping technique we used. It will serve you well.
Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke,
Go kill all,
Devansh <3
Reach out to me on:
Small Snippets about Tech, AI and Machine Learning over here
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd