GATE Problem Solving Techniques & Application Skills 2

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?

Accepted Answer

950

Answer

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)?

Accepted Answer

Divide and conquer

Answer

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|?

Accepted Answer

10

Answer

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?

Accepted Answer

18

Answer

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?

Accepted Answer

Dijkstra's algorithm

Answer

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

(GATE) Graduate Aptitude Test in Engineering Practice Test

(GATE) Graduate Aptitude Test in Engineering Practice Test

GATE Problem Solving Techniques & Application Skills 2