Greedy Algorithms Quiz — Quiz

Question 1

A greedy algorithm…

Makes the best-looking choice at each step and never revisits itTries every possible combinationAlways gives the optimal answerRequires recursion

Question 2

What is the best way to check whether a greedy idea is wrong?

Run it on the sample input onlyLook for a counter-exampleCheck that it is O(n)Ask whether it uses sorting

Question 3

To keep the MOST non-overlapping intervals, sort intervals by…

Start timeEnd timeLengthThey don't need sorting

Question 4

How many intervals must be removed from [[1,2], [2,3], [3,4], [1,3]] so the rest don't overlap?

Question 5

Can you reach the last index of [3, 2, 1, 0, 4] in Jump Game? Type yes or no.

Question 6

What is the minimum number of jumps to reach the end of [2, 3, 1, 1, 4]?

Question 7

In Gas Station, if the running tank goes negative at station i, the next candidate start is…

Station 0Station iStation i + 1The station with the most gas

Question 8Select all that apply

Which problems are typically solved greedily? (select all that apply)

Non-overlapping intervalsAssign cookiesCoin change with arbitrary coinsLongest common subsequence