Jobs

Interviews

Discussions

Guess Number Higher or Lower

Easy

Samsung

0 views

Topics:

Binary Search

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

-1: Your guess is higher than the number I picked (i.e. num > pick).
1: Your guess is lower than the number I picked (i.e. num < pick).
0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

Constraints:

1 <= n <= 2³¹ - 1
1 <= pick <= n

Guess Number Higher or Lower

Easy

Samsung

0 views

Topics:

Binary Search

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns three possible results:

-1: Your guess is higher than the number I picked (i.e. num > pick).
1: Your guess is lower than the number I picked (i.e. num < pick).
0: your guess is equal to the number I picked (i.e. num == pick).

Return the number that I picked.

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

Constraints:

1 <= n <= 2³¹ - 1
1 <= pick <= n

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of 'n'? Is it within the range of a standard integer?
Is 'n' always a positive integer greater than or equal to 1?
Is there a guarantee that the secret number is within the range [1, n], i.e., is there always a solution?
What should I return if the input 'n' is invalid (e.g., negative or zero)?
Can I assume the guess API is reliable and will always return -1, 1, or 0 for any guess within the defined range?

Brute Force Solution

Approach

We need to find a secret number within a range. The brute force method is like guessing every single number in the range, one at a time, until we find the correct one. We simply check each possibility.

Here's how the algorithm would work step-by-step:

Start by guessing the first number in the range.
See if this guess is the correct secret number.
If it's not the secret number, guess the next number in the range.
Keep guessing each number, one after another, until you guess the secret number.
The moment your guess matches the secret number, you've found the answer.

Code Implementation

def guess_number_higher_or_lower_brute_force(highest_possible_number):
    secret_number = 6 # This is only here to simulate the secret number to find
    
    current_guess = 1

    # We iterate through all possible numbers in range
    while current_guess <= highest_possible_number:

        # Check if the current guess is the secret number
        if current_guess == secret_number:
            return current_guess

        # If the guess is too low, proceed to the next higher number
        if current_guess < secret_number:
            current_guess += 1

        # If guess too high, return -1. Necessary for the case where secret number does not exist
        else:
            return -1

    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The described brute force approach iterates through a range of numbers, guessing each one until the secret number is found. In the worst-case scenario, the secret number is the last number in the range, or not in the range at all, requiring us to check every number from 1 to n, where n is the upper bound of the range. Therefore, the time complexity is directly proportional to the input size n, resulting in O(n) time complexity.

Space Complexity

O(1) – The provided plain English explanation describes a brute-force approach where we iteratively guess numbers. We are not storing any intermediate guesses or creating any auxiliary data structures like arrays or hash maps. The only extra space used is for the variable that holds the current guess, which is constant regardless of the range size (N, representing the range of numbers to guess from). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find a secret number by making guesses. The most efficient strategy is to repeatedly narrow down the range of possible numbers by half with each guess. This cuts the search area in half with each try.

Here's how the algorithm would work step-by-step:

Start by guessing the middle number between the lowest and highest possible numbers.
If the guess is too low, the secret number must be higher, so eliminate the bottom half of the range, including the guess.
If the guess is too high, the secret number must be lower, so eliminate the top half of the range, including the guess.
Repeat the process with the remaining range, always guessing the middle number.
Continue narrowing the range until the guess is correct.

Code Implementation

def guess_number(maximum_number) -> int:

    low_number = 1
    high_number = maximum_number

    while low_number <= high_number:

        mid_number = low_number + (high_number - low_number) // 2

        guess_result = guess(mid_number)

        if guess_result == 0:
            # We have found the number, return it

            return mid_number

        elif guess_result == -1:
            # Guess was too high, adjust the high number

            high_number = mid_number - 1

        else:
            # Guess was too low, adjust the low number

            low_number = mid_number + 1

    return -1 # Should not happen, for safety

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm uses a binary search approach to find the target number. The search space is halved in each iteration of the while loop. Given an input range of size n, the number of iterations required to find the number will be logarithmic, specifically log base 2 of n. Thus, the time complexity is O(log n).

Space Complexity

O(1) – The provided solution uses a binary search approach to find the secret number. It only requires storing a few variables like low and high to keep track of the search range. The number of variables used is constant and does not depend on the range of possible numbers (N). Therefore, the auxiliary space complexity is O(1), indicating constant space usage regardless of the input size.

Edge Cases

Case	How to Handle
n is 1	The secret number must be 1, so return 1 immediately.
Secret number is the minimum value (1)	Binary search should converge to the lower bound correctly.
Secret number is the maximum value (n)	Binary search should converge to the upper bound correctly.
n is a very large number (approaching integer limit)	Ensure the mid calculation uses (low + (high - low) / 2) to avoid integer overflow.
guess() function returns values outside of -1, 0, 1	Assume the guess function conforms to the provided specification and raise an exception if it does not.
n is close to the integer limit, and the secret number is also high	The difference between n and the secret number shouldn't affect performance due to binary search.
Integer overflow occurs during the calculation of 'mid'	Calculating mid as low + (high - low) / 2 mitigates the potential for integer overflow.
The guess API is inconsistently returning values	If the guess API is inconsistent, the algorithm may loop indefinitely or return an incorrect answer, but we assume the API is working correctly

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of 'n'? Is it within the range of a standard integer?
Is 'n' always a positive integer greater than or equal to 1?
Is there a guarantee that the secret number is within the range [1, n], i.e., is there always a solution?
What should I return if the input 'n' is invalid (e.g., negative or zero)?
Can I assume the guess API is reliable and will always return -1, 1, or 0 for any guess within the defined range?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by guessing the first number in the range.
See if this guess is the correct secret number.
If it's not the secret number, guess the next number in the range.
Keep guessing each number, one after another, until you guess the secret number.
The moment your guess matches the secret number, you've found the answer.

Code Implementation

def guess_number_higher_or_lower_brute_force(highest_possible_number):
    secret_number = 6 # This is only here to simulate the secret number to find
    
    current_guess = 1

    # We iterate through all possible numbers in range
    while current_guess <= highest_possible_number:

        # Check if the current guess is the secret number
        if current_guess == secret_number:
            return current_guess

        # If the guess is too low, proceed to the next higher number
        if current_guess < secret_number:
            current_guess += 1

        # If guess too high, return -1. Necessary for the case where secret number does not exist
        else:
            return -1

    return -1

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by guessing the middle number between the lowest and highest possible numbers.
If the guess is too low, the secret number must be higher, so eliminate the bottom half of the range, including the guess.
If the guess is too high, the secret number must be lower, so eliminate the top half of the range, including the guess.
Repeat the process with the remaining range, always guessing the middle number.
Continue narrowing the range until the guess is correct.

Code Implementation

def guess_number(maximum_number) -> int:

    low_number = 1
    high_number = maximum_number

    while low_number <= high_number:

        mid_number = low_number + (high_number - low_number) // 2

        guess_result = guess(mid_number)

        if guess_result == 0:
            # We have found the number, return it

            return mid_number

        elif guess_result == -1:
            # Guess was too high, adjust the high number

            high_number = mid_number - 1

        else:
            # Guess was too low, adjust the low number

            low_number = mid_number + 1

    return -1 # Should not happen, for safety

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 1	The secret number must be 1, so return 1 immediately.
Secret number is the minimum value (1)	Binary search should converge to the lower bound correctly.
Secret number is the maximum value (n)	Binary search should converge to the upper bound correctly.
n is a very large number (approaching integer limit)	Ensure the mid calculation uses (low + (high - low) / 2) to avoid integer overflow.
guess() function returns values outside of -1, 0, 1	Assume the guess function conforms to the provided specification and raise an exception if it does not.
n is close to the integer limit, and the secret number is also high	The difference between n and the secret number shouldn't affect performance due to binary search.
Integer overflow occurs during the calculation of 'mid'	Calculating mid as low + (high - low) / 2 mitigates the potential for integer overflow.
The guess API is inconsistently returning values	If the guess API is inconsistent, the algorithm may loop indefinitely or return an incorrect answer, but we assume the API is working correctly