## Tuesday, January 4, 2011

### Interesting Algorithm question in Facebook Interview

The question is:

"Given a number in range of 1 to n, what is minimum number of guesses needed to find a specific number if you're just given an answer either "higher" or "lower" for each guess you make"

It sounds tricky, but actually the answer is very simple.

Here's the illustration:

```the number to be guessed
|
V
|----------------------------------------------------------------------|
min                              ^                                    max
|
|
```

Using common method of binary searching, our guess starts from: min + (max-min)/2 or a number in the middle of the range (divide-and-conquer). If our guess is lower than the number, we're given "LOWER" and vice versa.

As the number to be guessed is random, it is possible the number falls right in the middle of the range and matches our first guess.  So the answer of this question is (the key of this question is "minimum number of guesses") is 1.

#### 1 comment:

1. Hi

I like this post:

You create good material for community.