Reason About Binary Search with One-Call-Delayed Feedback

Question

This question asks the candidate to implement a binary search algorithm with a twist: feedback on guesses is delayed, meaning the result of a guess is only available after the next guess is made.

Codemia · Accepted Answer

To solve the problem, we need to adapt the binary search algorithm to account for the delayed feedback mechanism. Normally, in a binary search, we check if the guessed number is too high or too low and adjust our search space accordingly. However, in this case, the feedback for a guess is only available after the next guess, which complicates the decision-making process. 1. Initialize two pointers, `low` and `high`, to represent the range of possible numbers. 2. While `low` is less than or equal to `high`, do the following: - Calculate the midpoint: `mid = (low + high) // 2`. - Make a guess with `mid` and store the result for the next iteration. - If the feedback from the previous guess indicates it was too low, set `low = mid + 1`. - If the feedback indicates it was too high, set `high = mid - 1`. 3. Repeat this process until the correct number is found. The time complexity of this modified binary search remains O(log n) in the average case, as we are still halving the search space with each guess. However, the delay in feedback means that we may need to make additional guesses before we can confirm the result of our previous guess, which could affect the overall number of iterations. ```python class GuessingGame: def __init__(self, secret_number): self.secret_number = secret_number self.last_feedback = None def guess(self, number): if number < self.secret_number: self.last_feedback = 'too low' return None elif number > self.secret_number: self.last_feedback = 'too high' return None else: self.last_feedback = 'correct' return 'correct' def delayed_binary_search(game, low, high): while low <= high: mid = (low + high) // 2 game.guess(mid) if game.last_feedback == 'too low': low = mid + 1 elif game.last_feedback == 'too high': high = mid - 1 return 'Number not found' ``` Consider edge cases such as when the secret number is at the boundaries of the range (e.g., `low` or `high`). Also, handle scenarios where the range is invalid (e.g., `low` > `high`). These cases should be addressed to ensure robustness in the implementation.

Reason About Binary Search with One-Call-Delayed Feedback

OpenAI

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

OpenAI Software Engineer Interview Guide

Related Questions

Design a scalable Search System

Design a Video Streaming for Rippling

Design a Load Balancing Service

Design a Image Processing Service

Build a high-throughput Image Processing Pipeline