Facebook 面试题:第一个错误的代码版本

zzzrf:代码库的版本号是从 1 到 n 的整数。某一天,有人提交了错误版本的代码,因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。
你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错,具体接口详情和调用方法请见代码的注释部分。

在线做题地址

样例

n = 5:

    isBadVersion(3) -> false
    isBadVersion(5) -> true
    isBadVersion(4) -> true

因此可以确定第四个版本是第一个错误版本。

算法:二分

假设第 k 个版本为第一个错误版本,那么 1---n 个版本分为 1---k-1 为正确版本,k---n 为错误版本,
我们需要以尽量少的次数去找到这个 k,显然我们如果一个个找过去的平均复杂度是 O(n)
那么我们可以考虑用二分来找到这个 k,二分的复杂度为 O(logn)

  • 二分[1,n]这个区间
  • 判断 isBadVersion ( mid )
    • 如果为 false 说明第一个错误版本在 mid 的右边,令 left = mid
    • 反之则在 mid 左边,令 right = mid
  • 缩小判断范围,当 left+1>=right 的时候结束二分
  • 最后再次判断下 isBadVersion ( left ),如果是错误版本的话返回 left,反之返回 right

复杂度分析

  • 时间复杂度 O(logn)
    • 二分的时间复杂度
  • 空间复杂度 O(1)
    • 无需额外空间
public class Solution {
    /**
     * @param n: An integer
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        int left = 1, right = n; // 左右边界
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            // 判断 mid 是否为正确版本,如果是的话,那么说明错误版本在 mid 的右边,反之则在左边
            if (SVNRepo.isBadVersion(mid)){
                right = mid; // 向[left,mid]查找错误版本
            }
            else { 
                left = mid; // 向[mid,right]查找错误版本
            }
        }
        // 最后判断下 left 是否是错误版本
        if (SVNRepo.isBadVersion(left)){
            return left;
        }
        return right;
    }
}

更多题解参考

被迫回国还能顺利上岸 Facebook?

hakunamatata11:课程概述 疫情下,从一名鹅厂高级产品经理一跃成为 Facebook E5 SDE,前期经历了 3 次面试失败,他都做了哪些准备才能一举拿下 offer,顺利上岸 内容介绍 算法面试如何突击 - 3 个月刷 600 道 行为面试到底考察啥 - 面试官都惊了 系统设计 - 找准方向其实也不难 Facebook 面试流程 - 原来是这…

Facebook 视频下载的 5 种最佳方法

kevenlee:Facebook 上的视频怎么下下载? Facebook (脸书)是大家比较熟知的国外社交媒体网站,里面有很多有趣的视频,很多人想将它们下载下来分享给朋友或家人观看但是网站没有提供直接下载的渠道,因此怎么下载 Facebook 上的视频一直是大家比较关注的问题,今天在这里我将分享五种 FB 视频下载方法,无论你使用 Android 还是 i…

Facebook graph API,获取所有广告帐户 - php

Improve this question 我有Facebook应用程序。有已授予ads_management和ads_read权限的用户的用户ID和访问令牌。如何获得与该用户相关联的所有广告帐户的列表?看到php解决方案会很疯狂。谢谢! 参考方案 使用/adaccounts端点。如果您使用的是PHP SDK,则可以使用。我在这里使用me作为ID。您可以将其…

facebook api(java或php):如何在打开应用程序时请求用户添加应用程序? - java

我已经使用flex创建了一个Facebook应用程序。我在apache-tomcat和tinyfbclient中都尝试过服务器端,并使用php并使用php facebook api。如果用户未添加我的应用程序,则无法获取用户信息。我如何检查用户是否将我的应用程序添加到了他的Facebook个人资料,如果没有,则如何打开一个允许他添加应用程序的窗口?谢谢! 参…

Facebook 面试题:子集 II

zzzrf:FB 还是比较爱考原题的 给定一个可能具有重复数字的列表,返回其所有可能的子集。 点此做题 样例 1: 输入:[0] 输出: [ [], [0] ] 样例 2: 输入:[1,2,2] 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] 解题思路 这道题我们需要使用 dfs+回溯的方法来进行求解。 由于题目明确指…