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
Is the following code DFS or BFS?
1void search(Node root) { 2 if (!root) return; 3 visit(root); 4 root.visited = true; 5 for (Node node in root.adjacent) { 6 if (!node.visited) { 7 search(node); 8 } 9 } 10}
Which algorithm should you use to find a node that is close to the root of the tree?
Solution Implementation
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Which of the following is the prefix sum of array [1, 2, 3, 4, 5]
?
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.