A call center agent has a list of 305 phone numbers of people in alphabetic…
2024
A call center agent has a list of 305 phone numbers of people in alphabetic order of names (but she does not have any of the names). Needs to quickly contact Deepak Sharma to convey a message to him. If each call takes 2 minutes to complete, and every call is answered, what is the minimum amount of time in which she can guarantee to deliver the message to Mr Sharma.
- A.
18 minutes
- B.
610 minutes
- C.
206 minutes
- D.
34 minutes
Attempted by 191 students.
Show answer & explanation
Correct answer: A
Key idea: use binary search because the phone numbers are sorted alphabetically by name.
Call the middle number in the list and ask whose number it is (or ask if this is Deepak Sharma).
Using the answered name, determine whether Deepak Sharma would be alphabetically before or after that name and discard the irrelevant half of the list.
Repeat this halving process until you reach Deepak Sharma.
Number of calls required (worst case):
With 305 entries, the worst-case number of calls is ceiling(log2(305)).
Since 2^8 = 256 and 2^9 = 512, log2(305) is between 8 and 9, so ceiling(log2(305)) = 9 calls.
Total time:
9 calls × 2 minutes per call = 18 minutes. Therefore, 18 minutes is the minimum time in which she can guarantee to deliver the message to Deepak Sharma.