To ace your coding interview for a software engineering job, you’ll need to understand greedy algorithms. Greedy algorithms solve optimization problems using the “greedy heuristic,” making locally optimal choices at each stage. Greedy algorithms are often intuitive and implemented more simply than other algorithms, but are not guaranteed to find globally optimal solutions.
Let’s take a look at some typical greedy algorithm questions.
5 typical greedy algorithm interview questions
-
Given the array points (balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend), return the minimum number of arrows that must be shot to burst all balloons.
-
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.
-
Given an array of strings words, return the smallest string that contains each string in words as a substring. If there are multiple valid strings of the smallest length, return any of them.
-
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1.
-
Given a set of n activities with their start and finish times, we need to select the maximum number of non-conflicting activities that can be performed by a single person, given that the person can handle only one activity at a time.
Below, we take a look at 50 greedy algorithm questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:
-
Easy greedy algorithm interview questions
- Medium greedy algorithm interview questions
- Hard greedy algorithm interview questions
- How to prepare for a coding interview
Let's get started.
1. Easy greedy algorithm interview questions
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of greedy algorithms.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.
Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the “phone screen” stage, so you should be comfortable answering them without being able to write code or use a whiteboard.
Question 1: Assign cookies
- Text guide (Medium/Fatboy Slim)
- Video guide (Nick White)
- Video guide (Kevin Naughton Jr.)
- Code example (fabrizio)
Question 2: Can place flowers
- Text guide (dilyar85)
- Video guide (NeetCode)
- Video guide (Nideesh Terapalli)
- Code example (soumyadeep2007)
Question 3: Lemonade change
- Text guide (Tutorial Cup)
- Video guide (Nick White)
- Code example (lee215)
Question 4: Partition array into three parts with equal sum
- Text guide (walkccc)
- Video guide (Ren Zhang)
- Code example (rock)
Question 5: Split a string in balanced strings
- Text guide (Medium/Rahul Gupta)
- Video guide (Kevin Naughton Jr.)
- Code example (dnuang)
Question 6: Maximum units on a truck
- Text guide (Dev.to/seanpgallivan)
- Video guide (Naresh Gupta)
- Code example (rock)
Question 7: Minimum moves to convert string
- Text guide (TechieDelight)
- Video guide (Programming Live with Larry)
- Code example (pollux1997)
2. Medium greedy algorithm interview questions
Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
Question 8: Jump game
- Text guide (Learnbay)
- Video guide (NeetCode)
- Code example (1337beef)
Question 9: Gas station
- Text guide (After Academy)
- Video guide (NeetCode)
- Code example (daxianji007)
Question 10: Jump game II
- Text guide (Medium/Nerd For Tech)
- Video guide (NeetCode)
- Code example (Cheng Zhang)
Question 11: Remove duplicate letters
- Text guide (Zirui)
- Video guide (Naresh Gupta)
- Code example (lixx2100)
Question 12: Wiggle subsequence
- Text guide (LeetCode)
- Video guide (probability_coding_is_fun_is_1)
- Code example (TenffY)
Question 13: Remove K digits
- Text guide (OpenGenus)
- Video guide (Nick White)
- Code example (kevinlai)
Question 14: Queue reconstruction by height
- Text guide (Medium/codeandnotes)
- Video guide (TECH DOSE)
- Code example (YJL1228)
Question 15: Non-overlapping intervals
- Text guide (Medium/The Startup)
- Video guide (NeetCode)
- Video guide (TECH DOSE)
- Code example (WangQiuc)
Question 16: Minimum number of arrows to burst balloons
- Text guide (Medium/Rohith)
- Video guide (Naresh Gupta)
- Code example (Joshua924)
Question 17: Task scheduler
- Text guide (Medium/Shymmy W. Garcia)
- Video guide (Naresh Gupta)
- Code example (g27as)
Question 18: Maximum length of pair chain
- Text guide (GeeksForGeeks)
- Video guide (Coding Gist)
- Video guide (TECH DOSE)
- Code example (yuxiong)
Question 19: Dota2 senate
- Text guide (FatalErrors)
- Code example (caihao0727mail)
Question 20: Split array into consecutive subsequences
- Text guide (junhaow)
- Video guide (Nideesh Terapalli)
- Code example (fun4LeetCode)
Question 21: Maximum swap
- Text guide (sugarac)
- Video guide (Algorithms Illustrator)
- Code example (joe53211)
Question 22: Monotone increasing digits
- Text guide (zhenyu0519)
- Video guide (Geek gang)
- Code example (Zee)
Question 23: Partition labels
- Text guide (algorithmsandme)
- Text guide (LeetCode)
- Video guide (NeetCode)
- Code example (DBabichev)
Question 24: Reorganize string
- Text guide (zhenyu0519)
- Video guide (Kevin Naughton Jr.)
- Code example (zestypanda)
Question 25: Increasing triplet subsequence
- Text guide (Medium/xiao mei)
- Video guide (Algorithms Made Easy)
- Code example (sim5)
Question 26: Max increase to keep city skyline
- Text guide (Tutorialspoint)
- Video guide (Nick White)
- Code example (lee215)
Question 27: Score after flipping matrix
- Text guide (Medium/Anj)
- Video guide (Leet Terps)
- Code example (faangboy)
Question 28: Hand of straights
- Text guide (Massive Algorithms)
- Video guide (NeetCode)
- Code example (lee215)
Question 29: Minimum add to make parentheses valid
- Text guide (Helloacm)
- Video guide (happygirlzt)
- Code example (lee215)
Question 30: Advantage shuffle
- Text guide (LeetCode)
- Text guide (Dev.to/seanpgallivan)
- Video guide (Algorithms Made Easy)
- Code example (caraxin)
Question 31: Minimum increment to make array unique
- Text guide (Tutorialspoint)
- Video guide (Happy Coding)
- Code example (lee215)
Question 32: Boats to save people
- Text guide (Massive Algorithms)
- Video guide (Kevin Naughton Jr.)
- Code example (lee215)
Question 33: Smallest range II
- Text guide (Medium/Jimmy Shen)
- Video guide (Algorithms Made Easy)
- Code example (dim_sum)
Question 34: Delete columns to make sorted II
- Text guide (Programmerall)
- Video guide (Hunter Macias)
- Code example (lee215)
Question 35: Bag of tokens
- Text guide (Medium/Glyn Liu)
- Video guide (Kevin Naughton Jr.)
- Code example (lee215)
Question 36: String without AAA or BBB
- Text guide (LeetCode)
- Video guide (happygirlzt)
- Code example (votrubac)
Question 37: Array of doubled pairs
- Text guide (hiepit)
- Video guide (Coding Decoded)
- Code example (Walkccc)
3. Hard greedy algorithm interview questions
Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
Question 38: Candy
- Text guide (LeetCode)
- Video guide (Algorithms Made Easy)
- Code example (meng789987)
Question 39: Create maximum number
- Text guide (Medium/dume0011)
- Code example (dietpepsi)
Question 40: Patching array
- Text guide (HackingNote)
- Video guide (Timothy H Chang)
- Code example (StefanPochmann)
Question 41: Smallest range covering elements from K lists
- Text guide (LeetCode)
- Video guide (IDeserve)
- Code example (awice)
Question 42: Minimum cost to hire K workers
- Text guide (shengqianliu)
- Video guide (Shiran Afergan)
- Video guide (AlgoCademy)
- Code example (lee215)
Question 43: IPO
- Text guide (Massive algorithms)
- Video guide (Imran Sarwar)
- Video guide (Ren Zhang)
- Code example (shawngao)
Question 44: Set intersection size at least two
- Text guide (Titanwolf)
- Code example (fun4LeetCode)
Question 45: Course schedule III
- Text guide (Dev.to/seanpgallivan)
- Video guide (Timothy H Chang)
- Code example (KakaHiguain)
Question 46: Couples holding hands
- Text guide (Medium/Jolyon)
- Video guide (Arpan Pathak)
- Code example (LeetCode)
Question 47: Minimum number of refueling stops
- Text guide (Dev.to/seanpgallivan)
- Video guide (Algorithms Made Easy)
- Code example (chipbk10)
Question 48: Longest chunked palindrome decomposition
- Text guide (Tutorialspoint)
- Code example (lee215)
Question 49: Stamping the sequence
- Text guide (Dev.to/seanpgallivan)
- Video guide (Algorithms Made Easy)
- Code example (FLAGbigoffer)
Question 50: Minimum number of taps to open to water a garden
- Text guide (Medium/Kostya)
- Video guide (Tony Teaches)
- Code example (BlueCamel)
4. How to prepare for a coding interview
4.1 Refresh your knowledge
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only greedy algorithms but also the rest of the relevant algorithms and data structures. Check out our guides for detailed explanations and useful cheat sheets.
Algorithms explained:
- Depth-first search
- Breadth-first search
- Binary search
- Sorting
- Dynamic programming
- Greedy algorithm
- Backtracking
- Divide and conquer
Data structure guides:
4.2 Practice on your own
Once you’re confident in all of these, you’ll want to start working through lots of coding problems.
For greedy algorithms you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:
- Depth-first search interview questions
- Breadth-first search interview questions
- Binary search interview questions
- Sorting interview questions
- Dynamic programming interview questions
- Backtracking interview questions
- Divide and conquer interview questions
We also recommend working through our list of 73 data structure interview questions.
One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview.
It's also a good idea to work on a piece of paper or google doc, given that in the real interview you'll have to code on a whiteboard or virtual equivalent.
3.3 Practice with others
Of course, if you can practice with someone else playing the role of the interviewer, that's really helpful. But sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.
That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.
Any questions about greedy algorithms?
If you have any questions about greedy algorithms or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!