How do you “prove” a problem can be solved using a greedy algo in an interview setting?
Usually it’s pretty obvious based on intuition but that’s not enough to say in an interview
TC: 220k
Want to see the real deal?
More inside scoop? View in App
More inside scoop? View in App
blind
SUPPORT
FOLLOW US
DOWNLOAD THE APP:
FOLLOWING
Industries
Job Groups
- Software Engineering
- Product Management
- Information Technology
- Data Science & Analytics
- Management Consulting
- Hardware Engineering
- Design
- Sales
- Security
- Investment Banking & Sell Side
- Marketing
- Private Equity & Buy Side
- Corporate Finance
- Supply Chain
- Business Development
- Human Resources
- Operations
- Legal
- Admin
- Customer Service
- Communications
Return to Office
Work From Home
COVID-19
Layoffs
Investments & Money
Work Visa
Housing
Referrals
Job Openings
Startups
Office Life
Mental Health
HR Issues
Blockchain & Crypto
Fitness & Nutrition
Travel
Health Care & Insurance
Tax
Hobbies & Entertainment
Working Parents
Food & Dining
IPO
Side Jobs
Show more
SUPPORT
FOLLOW US
DOWNLOAD THE APP:
comments
I guess I’ll start out by saying there are 2 flavors of greedy algorithms from what I’ve seen.
The first is the ones where the greedy choice yields an immediate result that is “the answer”. Think of merging 2 sorted arrays, for instance, where selecting the smallest value over and over yields the correct final solution. These are the kinds where you can prove them via intuition because you can sort of just see that they work after only a few iterations. This would be proof by induction.
The second is harder and might require math to be rigorously proven. It is when you iterate along a bunch of choices in an efficient manner and any one of them can be the correct final choice. These can be harder to spot because iterating through it doesn’t yield clear results as to whether you’re heading the correct direction. So how do you know it works? Well, instead of showing what iteration 1, 2, and 3 would look like and leaving that as a proof, instead you would just prove that the ideal answer is guaranteed to be among one of the possibilities you’re iterating. See this problem for an example:
https://leetcode.com/problems/minimum-cost-to-hire-k-workers/description/
Similar to DP which is characterized by overlapping subproblems and optimal substructures. Greedy algorithms only have the optimal substructures. I’d focus on explaining that the solution is the result of these substructures. Not sure how to prove formally though just by stepping through a few simple problems and edge cases.