Question 3 Ramu is given a bag of n laddus.
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Ramu is given a bag of n laddus. All the laddus should be identical i.e. the weight of every laddu should be same. But on picking up the box with laddus, Ramu noticed some discrepancy. box's weight was lesser than it should be. The shopkeeper told him that he was in short of laddus so he bought one laddu from other shop. Now Ramu wants to find that one laddu in the set of n laddus. To do that he has got a comparator function which compares two set of laddus and return true if their weights are some or the set which have lesser weight.
Determine the min. no. of times Ramu has to use the comparator.
Select any one of the following
Show answer & explanation
Using a comparator/balance scale between sets of laddus divides the search space into 3 parts at each step, taking ceil(log_3(n)) = O(log n) comparisons in the worst case.
Step-by-step Derivation:
Step 1: A two-pan balance scale gives 3 possible outcomes: left lighter, right lighter, or both equal.
Step 2: By dividing n laddus into 3 equal sets (or n/3), each comparison reduces candidate size by a factor of 3.
Step 3: The minimum number of comparisons needed to find the defective laddu in the worst case is ceil(log_3(n)) = O(log n).