V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lewis89
V2EX  ›  程序员

这样的面试题是否有意义?

  •  
  •   lewis89 · 2020-01-19 18:32:02 +08:00 · 4327 次点击
    这是一个创建于 1761 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个算法题

    要求用二分查找实现

    public double sqrt(int num){
        //实现
    }
    
     /**
         * 二分查找 求平方根
         * @param num
         * @return
         */
        public double sqrt(int num) {
            //这个题应该要看精度 如果没有特殊的精度要求
            double low = 0;
            double high = num;
            while (low < high) {
                double mid = (low + high) / 2;
                if ((mid * mid) > num) {
                    high = mid;
                } else if ((mid * mid) < num) {
                    low = mid;
                } else {
                    // mid * mid == num 因为我做这个题目时候会觉得这个条件可能永远不会成立
                    // 但是 double 类型存在一个精度问题
                    // 当 mid 的精度到达一定位置时候 mid * mid 会得到一个整数 其刚好是 num 的近似平方根
                    return mid;
                }
            }
            return -1;
        }
    

    这个题目 当时是没有精度要求的,我根本就想不到 两个 double 相乘,在一定精度情况下居然能够得到一个整数, 当然我理解其中的原理,由于二进制长度限制,有限的位置不可能表示无限精度的小数,所以其乘法运算可能会出现溢出的情况,然后乘法运算溢出后的结果刚刚是一个整数。

    第 1 条附言  ·  2020-01-19 19:16:09 +08:00
    标题党 仅供讨论, 没有任何贬低这个题的意思,主要我面试的时候当时也没考虑到
    这种二分迭代终止的方式,面试完了 才想起来。

    当然毫无疑问的挂了.. 有去面 tuhu 的 可能用得上,算是小小的泄题了..
    24 条回复    2020-01-20 10:55:39 +08:00
    yuankui
        1
    yuankui  
       2020-01-19 18:39:01 +08:00
    面试官正在为自己想到这么优秀的解法而骄傲
    lewis89
        2
    lewis89  
    OP
       2020-01-19 19:03:17 +08:00
    @yuankui #1 这个解法是我事后想到的,出题的事后 他也没讲精度,没有精度约束的话 只能这样求解,但是我又不敢这样写。
    RtIHZ
        3
    RtIHZ  
       2020-01-19 19:06:26 +08:00   ❤️ 1
    ```
    const double DELTA = 0.000001;
    if (abs(mid * mid - num) < DELTA) {
    // ...
    }
    ```
    InkStone
        4
    InkStone  
       2020-01-19 19:06:35 +08:00
    我觉得你想多了,面试官可能单纯是想让你用牛顿法……
    RtIHZ
        5
    RtIHZ  
       2020-01-19 19:08:03 +08:00
    这题我觉得出的没毛病。
    InkStone
        6
    InkStone  
       2020-01-19 19:08:53 +08:00
    或者就像三楼那么写二分,完全没有问题。楼主你事后想出来的这个写法有 UB,肯定不能这么写的……
    lewis89
        7
    lewis89  
    OP
       2020-01-19 19:09:14 +08:00
    @InkStone #4 指明了要用二分法..
    lewis89
        8
    lewis89  
    OP
       2020-01-19 19:09:57 +08:00
    @InkStone #6 我知道 3 楼那个写法也是一个选择..
    also24
        9
    also24  
       2020-01-19 19:11:50 +08:00
    既然你已经意识到了精度问题,那么完全可以定义一个精度阈值:

    类似:const double eps =1e-7;

    然后最后一个 else 改为:else if ( fabs ((mid * mid) -num ) < eps )

    如果害怕面试官看不懂,在 eps 那一句再加上个注释就好了。
    lewis89
        10
    lewis89  
    OP
       2020-01-19 19:13:13 +08:00
    @also24 #9 面试的时候 没想到过 一般都是做的整数查找 迭代的终止条件比较清楚 mid == target
    小数当时没有意识到,尴尬了..
    bitholic
        11
    bitholic  
       2020-01-19 19:49:34 +08:00
    面试官可能只是随便找了到 leetcode 原题而已,https://leetcode.com/problems/sqrtx/
    zhgg0
        12
    zhgg0  
       2020-01-19 19:54:55 +08:00
    你这写法最终得到的结果差太远了吧,不考虑小数位,得到的整数位都不对。
    xuanbg
        13
    xuanbg  
       2020-01-19 20:15:17 +08:00
    楼主这个算法计算 2 的平方根要迭代多少次啊……而且算不准 4、9、16 这些数的平方根
    misdake
        14
    misdake  
       2020-01-19 20:36:49 +08:00
    mid 不再变化的时候,取 low 和 high 中误差较小的一个。
    lhx2008
        15
    lhx2008  
       2020-01-19 20:46:20 +08:00
    这个题本质是二分查找,二分查找不总是有等于号的情况的,可以参考 lower bound 的写法,或者一个简单的变式,找[0,0,0,0,1,1,1] 中 0 的个数,这个题其实 if 格式和平方根是一样的。
    xupefei
        16
    xupefei  
       2020-01-19 20:56:50 +08:00
    你可以写 if(mid*mid >= num && (mid+1)*(mid+1) <= num) return mid 哇。
    lewis89
        17
    lewis89  
    OP
       2020-01-19 21:08:19 +08:00
    @xuanbg #13 你运行一下试试 可以算准的,对于没法直接整数的 可能有误差
    ihciah
        18
    ihciah  
       2020-01-20 02:06:16 +08:00
    impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
    let mut low: i64 = 0;
    let mut high: i64 = x as i64;
    while low < high {
    let mid = low + (high - low + 1) / 2;
    if mid * mid > x as i64 {
    high = mid - 1;
    } else {
    low = mid;
    }
    }
    low as i32
    }
    }
    不是精确查找,if 两个分支就够了。
    lewis89
        19
    lewis89  
    OP
       2020-01-20 07:10:23 +08:00
    @xupefei #16 当时没想过,实际上不一定要相等才能结束迭代,可以差值在一个范围内 break 出迭代 也能返回一个近似值
    lewis89
        20
    lewis89  
    OP
       2020-01-20 07:14:20 +08:00
    @bitholic #11 并不是 上面要求的返回值是 double 类型,没要求 int 类型,double 类型的话 OJ 不太好判题
    lewis89
        21
    lewis89  
    OP
       2020-01-20 07:20:35 +08:00
    @bitholic #11 如果是 int 型的话 我可能就已经想出来了
    ebingtel
        22
    ebingtel  
       2020-01-20 08:43:54 +08:00
    double mid = (low + high) / 2;……容易溢出的吧
    ineed123
        23
    ineed123  
       2020-01-20 10:04:26 +08:00
    double mid = (high - low) / 2 + low; 或 double mid = low + ((high - low) >> 1); // 防止溢出
    Jrue0011
        24
    Jrue0011  
       2020-01-20 10:55:39 +08:00
    看到楼主这帖子。。我这种大学数学全忘了的在网上搜了下,高数里有个二分法求方程根的近似值,别说还挺像的。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1048 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 22:22 · PVG 06:22 · LAX 14:22 · JFK 17:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.