[Google Interview] Guess The Number Higher or Lower

[toc]

Company tags: Google

Are you preparing for your next coding interview? If your answer is yes, then here’s a very interesting interview question for you that might come up in your interview.

Problem Statement

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 function int guess(int num), which returns 3 possible results:

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

Return the number that I picked.

⚠️Constraints:

• 1 <= n <= 231 - 1
• 1 <= pick <= n

Let’s have a look at some examples to improve our understanding of this problem.

Examples

Now that you have understood the problem, let’s dive into the methods to solve the problem.

Prerequisite: If you are using a local editor, use the following function as the pre-defined function “guess”:

def guess(num):
    if pick < num:
        return -1
    elif pick > num:
        return 1
    else:
        return 0

Method 1: Using Linear Search

Approach: The simplest approach would be to apply the linear search algorithm to guess whether the number is higher or lower. Go through every number and if it is equal to the pick, return the number.

Algorithm

1. Initialize a variable no to 0.
2. Check for every number till no < = n to find if the guess is equal to the pick
3. Return the current number when the predefined function guess returns the value 0.

Solution: Let’s look at the code.

def guess_no(n, pick):  
    no = 0
    while no <= n:
        if guess(no) == 0:
            return no
        no = no + 1

Test Case Analysis: Let’s run this code on our examples.

# Example 1
n = 10
pick = 6
print(guess_no(n, pick))
# 6

# Example 2
n = 1
pick = 1
print(guess_no(n, pick))
# 1

# Example 3
n = 20
pick = 10
print(guess_no(n, pick))
# 10

# Example 4
n = 10
pick = 9
print(guess_no(n, pick))
# 9

Complexity Analysis: In the worst-case scenario, the picked number is the last guessed number. In this case, the time complexity of this method will be O(n).

Method 2: Using Divide and Conquer

Approach: In this approach, you have to divide n in half and search for the “guess” in another half by passing the variable “mid” value to the predefined function guess. Thus the idea of this approach is to divide the given range and then conquer the guessed number. Doesn’t it look like an implementation of the binary search algorithm??

Algorithm:

1. Initialize the low and high as 0 and n + 1.
2. Calculate the mid-value as (low + high)//2 and pass it to the pre-defined guess function.
3. If the value returned by the function is 0, return mid.
4. If the returned value is 1, update the value of low to mid + 1.
5. If the returned value is -1, update the value of high to mid - 1.

The following diagram represents the working principle of the above algorithm with the help of an example.

Solution: Let’s look at the code:

def guess_no(n, pick):  
    low, high = 0, n 
    while low <= high:
        mid = (low + high) // 2	
        if guess(mid) == 0:
            return mid		
        else:
            if guess(mid) == 1:
                low = mid + 1
            else:
                high = mid – 1

Test Case Analysis: Let’s run this code on our examples.

# Example 1
n = 10
pick = 6
print(guess_no(n, pick))
# 6

# Example 2
n = 1
pick = 1
print(guess_no(n, pick))
# 1

# Example 3
n = 20
pick = 10
print(guess_no(n, pick))
# 10

# Example 4
n = 10
pick = 9
print(guess_no(n, pick))
# 9

Hurrah! It passed all the test cases.

Complexity Analysis:

• Time Complexity: We have used the divide and conquer strategy in this method, hence the time complexity of this method will be O(log n).
• Space Complexity: The space complexity of this method remains constant, i.e O(1).

Bonus Solution: Using Ternary Search

Approach: The approach is almost similar to the binary search with the only difference that we divide n into three parts in this method. Use two mid variables to guess whether the number is high or low.

Algorithm:

1. Initialize the low and high as 0 and n + 1.
2. Calculate the mid1 and mid2 value as low+(high - low)//3 and high-(high-low)//3 respectively.
3. Pass both the mid-values to the predefined guess function. If the value returned is 0, pass the respective mid-values.
4. Else, update the low and high values.

Solution: Let’s look at the code.

def guess_no(low, high):  
    low, high = 0, n 

    while low <= high:
        mid1 = low + (high - low) // 3
        mid2 = high - (high - low) // 3
        if guess(mid1) == 0:
            return mid1
        if guess(mid2) == 0:
            return mid2
        if guess(mid1) + guess(mid2) == 0:
            low = mid1 + 1
            high = mid2 - 1
        elif guess(mid1) == -1:
            high = mid1 - 1
        else:
            low = mid2 + 1

Test Case Analysis: Let’s run this code on our examples.

# Example 1
n = 10
pick = 6
print(guess_no(n, pick))
# 6

# Example 2
n = 1
pick = 1
print(guess_no(n, pick))
# 1

# Example 3
n = 20
pick = 10
print(guess_no(n, pick))
# 10

# Example 4
n = 10
pick = 9
print(guess_no(n, pick))
# 9

Complexity Analysis:

• Time Complexity: The ternary search is similar to the Binary search method with the time complexity of O(log3n) ~ O(logn).
• Space Complexity: The space complexity of this method remains constant, i.e O(1).

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

✍️ Post Credits: Shubham Sayon and Rashi Agarwal

Recommended: Finxter Computer Science Academy

• One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in today’s world that’s shaped by the web and remote work.
• So, do you want to master the art of web scraping using Python’s BeautifulSoup?
• If the answer is yes – this course will take you from beginner to expert in Web Scraping.