Problem Solving Techniques & Application Skills Flashcards

A factory produces items in batches. In the first batch, 5% are defective. If 1000 items are inspected and defectives are removed, how many non-defective items remain?

Answer: 950

5% of 1000 = 50 defective items, so 1000 - 50 = 950 non-defective items remain.

A problem requires O(n²) time to solve using a brute-force approach. Which technique most likely reduces this to O(n log n)?

Answer: Divide and conquer

Divide and conquer typically splits the problem into halves and recombines, giving T(n) = 2T(n/2) + O(n), which resolves to O(n log n) by the Master Theorem.

In a Venn diagram with sets A and B, |A| = 30, |B| = 25, |A ∪ B| = 45. What is |A ∩ B|?

Answer: 10

By inclusion-exclusion: |A ∩ B| = |A| + |B| - |A ∪ B| = 30 + 25 - 45 = 10.

A pipe fills a tank in 6 hours and another empties it in 9 hours. If both are open simultaneously, how many hours does it take to fill the tank?

Answer: 18

Net rate = 1/6 - 1/9 = 1/18 per hour, so the tank fills in 18 hours.

Which approach is best for finding the shortest path in a weighted graph with non-negative edge weights?

Answer: Dijkstra's algorithm

Dijkstra's algorithm efficiently finds single-source shortest paths in graphs with non-negative weights using a greedy approach.

A train travels 360 km in 4 hours. At the same speed, how long will it take to travel 270 km?

Answer: 3 hours

Speed = 360/4 = 90 km/h; time = 270/90 = 3 hours.

When applying dynamic programming to a problem, the key property required is:

Answer: Optimal substructure and overlapping subproblems

Dynamic programming applies when the problem exhibits both optimal substructure (optimal solution contains optimal sub-solutions) and overlapping subproblems (same sub-problems solved repeatedly).