Bad Product
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n
versions [1, 2, ..., n]
and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version)
which returns whether version
is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
Example 2:
Input: n = 1, bad = 1
Output: 1\
Constraints:
1 <= bad <= n <= 231 - 1
Solution
Intuitively, we know that the product versions is a sequence of good versions, followed by a group of bad versions.
This means that we are looking for the first index which isBadVersion(ans)
returns true
.
Therefore, we must update the answer when we find a smaller version that is bad, repeat until we find the smallest.
1def firstBadVersion(self, n: int) -> int:
2 left, right = 1, n
3 ans = -1
4
5 while left <= right:
6 mid = (left + right) // 2
7 if isBadVersion(mid):
8 ans = mid
9 right = mid - 1
10 else:
11 left = mid + 1
12
13 return ans
Depth first search can be used to find whether two components in a graph are connected.
Which of the following uses divide and conquer strategy?
Solution Implementation
Which technique can we use to find the middle of a linked list?
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.