How to Spot Greedy Algorithms[Techinque Tuesdays]

This will help you a lot

Jun 22, 2022

Hello there my amazing reader,

When you read this, I will be at my cousin’s wedding Sangeet. The Sangeet is an event that takes place one night before the actual wedding where women meet and sing (Sangeet is Song in Hindi). This is actually the first wedding I’ve attended, so I’m very interested in seeing this ceremony.

In celebration of this extra special event, I will cover something super special. Many of you have spent a long time struggling with figuring out how to Spot Greedy algorithms in your coding problems. I will give you a framework that will let you spot questions that can be solved with a greedy algorithm very effectively.

Highlights

This post will cover the following ideas-

What makes a greedy algorithm- Greedy algorithms are greedy because they don’t look ahead. They take the best decision at the current point without considering if a worse option now might lead to better results later. In math terms, Greedy Algorithms always maximize for the local optima at the cost of often missing the global optimal.
How you can Spot Greedy Algorithms- Using a list of questions and considerations you can spot questions with Greedy Algorithms effectively.
How to get good at this- Practice. Lots of practice.

This post will change your life. Get ready.

What makes a greedy algorithm?

I could give you the theoretical definition (I kinda did in the highlights), but most of you don’t need that. If it is of interest to you, I can actially do another Math Monday dedicated to the Mathematical properties of Greedy Algos. So instead, enjoy this lovely graphic I took from Wikipedia.

Greedy Algorithms show up a lot in AI and decision theory. When the situation is very complex and there are too many factors to consider, Greedy Algorithms can be a great alternative to have something going. The traveling salesman problem is a great example. However, questions in Leetcode style interviews are much simpler, and can generally be solved optimally with Greedy Algorithms. So how can you discover if a question lends itself to the Greedy approach? Let’s take a look.

How to Spot Greedy Algorithms?

I could talk about how to prove if a question is greedy using Math. But most of you will not need to do that in your coding. We shall leave that for a Math Monday.

The first hint that you can use to spot the Greedy Algos is their optimal sub-structure property. If your problem can be broken into sub-problems and that their individual optimal solution is part of the optimal solution of the whole problem, then the greedy algorithm is a viable solution.

Why is this true? Think back to how we defined a greedy solution. It will go for the local optima over the global optima. If the optimal solutions to all your sub-problems are part of your solution, then taking the local optima will lead to globally best solution.

The best way to test this out is to take your question and simulate algorithms on small inputs. These will help you spot the structure quickly.

Along with this, there are a few guiding questions that you can use to help you spot the Greedy Algos. Consider the following-

Do I have a choice between different alternatives at some point? Greedy Algorithms exist for exploring options.
Does this choice result in sub-problems that can be solved individually?
Will I be able to use the solution of the sub-problem to derive a solution for the overall problem?

This discussion is pretty interesting. It explores the ideas mentioned here with a few more examples.

How to Get Good

This is the most boring part of the newsletter. Regular Readers know exactly what I’m going to say. You will have to implement this framework on a lot of Greedy questions, to develop your intuition for this topic.

As you continue to practice, make sure you analyze the problems to refine your comfort with this procedure. As you work with this, you will find your skills getting much better.

Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.

Special Request

This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.

There is a simple form in Substack that you can fill up for it. Here it is. Thank you.

https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform

To get your Substack URL, follow the following steps-

Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.

Click on the circled place to get your URL

You will be redirected to your URL. Please put that in to the survey. Appreciate your help.

In the comments below, share what topic you want to focus on next. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs

If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.

https://forms.gle/XfTXSjnC8W2wR9qT9

Happy Prep. I’ll see you at your dream job.

Go kill all you magnificent maestro,

Devansh <3

To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below

Get 20% off for 1 year