Greedy Algorithms

Meta
mdkkqjan

Go to company page Meta

mdkkqjan
Mar 25 7 Comments

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

comments

Want to comment? LOG IN or SIGN UP
TOP 7 Comments
  • Twitter
    HSKP77

    Go to company page Twitter

    HSKP77
    Bro you just think it through idk what else to tell you
    Mar 25 2
  • Google / Eng
    LeeJaeDong

    Go to company page Google Eng

    PRE
    Amazon
    LeeJaeDong
    Proof by contradiction, or take advantage of some sorted property that lets one choice rule out other choices as suboptimal without needing to try them.
    Mar 25 0
  • A lot of the answers in here aren’t actionable so I’ll try my hand.

    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/
    Mar 25 0
  • Google
    dental

    Go to company page Google

    dental
    I guess you can demonstrate that for each iteration making the ideal decision leads to the right answer.

    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.
    Mar 25 0
  • New
    ❣️

    New

    ❣️
    2 ways to prove greedy works are exchange proofs and greedy stays ahead arguments, you could adapt these proofs to less formal “reasoning” for an interview setting
    Mar 25 0