Greedy Algorithm Mastery: Interview Prep Quiz Quiz

1. Q1

   Which of the following best describes the core principle behind a greedy algorithm?

   1. Making the locally optimal choice at each step with the hope of finding a global optimum.
   2. Exploring all possible solutions to find the absolute best answer.
   3. Dividing the problem into smaller subproblems and solving them recursively.
   4. Randomly selecting a solution and iteratively improving it.

2. Q2

   In the Activity Selection Problem, what criterion is typically used to select the next activity?

   1. Earliest start time
   2. Shortest duration
   3. Earliest finish time
   4. Maximum profit

3. Q3

   What is the primary advantage of using Huffman Coding for data compression?

   1. Minimizing the average code length for frequently occurring characters.
   2. Providing strong encryption for sensitive data.
   3. Guaranteeing lossless compression for all types of data.
   4. Simplifying the encoding and decoding process significantly.

4. Q4

   For the Fractional Knapsack Problem, how is the greedy approach applied?

   1. Selecting items in decreasing order of weight.
   2. Selecting items in increasing order of value.
   3. Selecting items in decreasing order of value-to-weight ratio.
   4. Selecting items randomly until the knapsack is full.

5. Q5

   In Job Sequencing with Deadlines, what factor determines the selection of jobs?

   1. Jobs with the earliest deadlines are prioritized.
   2. Jobs with the highest profits are prioritized, respecting deadlines.
   3. Jobs with the shortest processing times are prioritized.
   4. Jobs are selected randomly.

6. Q6

   Which data structure is commonly used to efficiently implement Kruskal’s algorithm for finding the minimum spanning tree?

   1. Heap
   2. Binary Search Tree
   3. Disjoint Set Union (DSU)
   4. Linked List

7. Q7

   What is the primary difference between Kruskal’s and Prim’s algorithms for finding minimum spanning trees?

   1. Kruskal’s is faster than Prim’s.
   2. Prim’s grows the MST from a single starting vertex, while Kruskal’s adds edges in increasing order of weight.
   3. Kruskal’s can handle negative edge weights, while Prim’s cannot.
   4. Prim’s is easier to implement than Kruskal’s.

8. Q8

   What is a common real-world application of Huffman Coding?

   1. Database indexing
   2. Image compression (JPEG)
   3. Network routing
   4. Operating system scheduling

9. Q9

   What is the typical time complexity of the Fractional Knapsack algorithm?

   1. O(n)
   2. O(n log n)
   3. O(n^2)
   4. O(2^n)

10. Q10

    Under what condition is a greedy algorithm most likely to fail in finding the optimal solution?

    1. When the problem has optimal substructure.
    2. When the problem has overlapping subproblems.
    3. When the locally optimal choice does not lead to a globally optimal solution.
    4. When the input size is very small.

11. Q11

    Why might dynamic programming be preferred over a greedy approach for certain optimization problems?

    1. Dynamic programming is always faster than greedy algorithms.
    2. Dynamic programming guarantees an optimal solution by exploring all possibilities.
    3. Greedy algorithms always require more memory.
    4. Dynamic programming is simpler to implement.

12. Q12

    What is the 'greedy choice property'?

    1. The property that an optimal solution to the problem can always be found by making a series of locally optimal choices.
    2. The property that the problem can be divided into smaller, overlapping subproblems.
    3. The property that the problem has many possible solutions.
    4. The property that the problem is NP-complete.

13. Q13

    Which of the following problems is LEAST suitable for solving with a greedy algorithm?

    1. Fractional Knapsack
    2. Activity Selection
    3. Traveling Salesperson Problem (TSP)
    4. Huffman Coding

14. Q14

    What is a common strategy for proving the correctness of a greedy algorithm?

    1. Exhaustive search
    2. Mathematical induction, showing that the greedy choice always leads to an optimal partial solution.
    3. Empirical testing with large datasets
    4. Randomized simulations

15. Q15

    Suppose a new problem seems suitable for a greedy approach. What's a critical first step in determining if this is truly viable?

    1. Immediately implement the greedy algorithm and test it.
    2. Focus on optimizing the data structures for speed.
    3. Attempt to prove that the greedy choice property holds and that an optimal substructure exists.
    4. Compare the problem to known dynamic programming problems.