GATE Problem Solving Techniques & Application Skills 2 — Questions and Answers
Question 1: 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?
- 900
- 950 (Correct answer)
- 975
- 990
Correct answer: 950
5% of 1000 = 50 defective items, so 1000 - 50 = 950 non-defective items remain.
Question 2: A problem requires O(n²) time to solve using a brute-force approach. Which technique most likely reduces this to O(n log n)?
- Dynamic programming
- Divide and conquer (Correct answer)
- Greedy algorithm
- Backtracking
Correct 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.
Question 3: In a Venn diagram with sets A and B, |A| = 30, |B| = 25, |A ∪ B| = 45. What is |A ∩ B|?
- 5
- 10 (Correct answer)
- 15
- 20
Correct answer: 10
By inclusion-exclusion: |A ∩ B| = |A| + |B| - |A ∪ B| = 30 + 25 - 45 = 10.
Question 4: 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?
- 12
- 15
- 18 (Correct answer)
- 21
Correct answer: 18
Net rate = 1/6 - 1/9 = 1/18 per hour, so the tank fills in 18 hours.
Question 5: Which approach is best for finding the shortest path in a weighted graph with non-negative edge weights?
- Bellman-Ford algorithm
- Dijkstra's algorithm (Correct answer)
- Floyd-Warshall algorithm
- Prim's algorithm
Correct answer: Dijkstra's algorithm
Dijkstra's algorithm efficiently finds single-source shortest paths in graphs with non-negative weights using a greedy approach.
Question 6: A train travels 360 km in 4 hours. At the same speed, how long will it take to travel 270 km?
- 2.5 hours
- 3 hours (Correct answer)
- 3.5 hours
- 4 hours
Correct answer: 3 hours
Speed = 360/4 = 90 km/h; time = 270/90 = 3 hours.
Question 7: When applying dynamic programming to a problem, the key property required is:
- Greedy choice property
- Optimal substructure and overlapping subproblems (Correct answer)
- Polynomial reducibility
- Matroid intersection
Correct 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).
GATE Problem Solving Techniques & Application Skills 2
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?