First Bad Version
Easy
Question
For the past month, you've pushed changes to a project, where every change is based on its previous version. You recently notice the latest version of your project is failing.
Given a list of n
versions that are either True
if it worked or False
if it failed, find which version your project started to fail at.
Note: Solve this problem in O(logn) time.
Input: [True, True, True, True, False, False]
Output: 4
The project started failing at Version 4.
Input: [True, False, False, False]
Output: 1
The project started failing at Version 1.
Clarify the problem
What are some questions you'd ask an interviewer?
Understand the problem
Given this list, when did the project start failing? [True, True, True, True, True, False, False, False]
4
5
6
7
Take a moment to understand the problem and think of your approach before you start coding.