美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 《汉尼拔》第四季有回归的可能性了!
  • 略惊悚:Wi-Fi变狗仔 还能全息成像
  • 厉害了!中国动车组获欧盟铁路最高认证
  • 黄种人首进9.9秒!苏炳添百米创个人最好成绩
  • 北斗/GPS导航定位基准服务启用!精度/信号大提升
  • 神秘外星人在哪?科学家发现了这个地方...
  • 黄金竟有这神用途:成抗击癌症的“子弹”
  • 海盗传说:真的有海怪、美人鱼吗?
  • 夏天穿浅色衣服更凉快?被骗好多年……
  • 为什么互联网大佬都开始养猪养鸡了?
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3137|回复: 12

    内推面经 -问一个多次遇到的面试题- 唐人社区|北美华人论坛

    [复制链接]

    14

    主题

    29

    帖子

    60

    积分

    注册会员

    Rank: 2

    积分
    60
    QQ
    发表于 2016-10-18 08:11:07 | 显示全部楼层 |阅读模式
    分享到:
    {$content}

    唐人社区-北美华人论坛-内推面经版-问一个多次遇到的面试题



    JobHunting
    标 题: 问一个多次遇到的面试题


    我和同学被两家不同的公司考了这个题。

    输入是一个排好序的decimal数组和一个target number。要求找出这个数组中最接近
    target的数。例子:
    [1.0, 2.5, 3.0], target = 0.5, 那么就返回1.0.
    [1.0, 2.5, 3.0], target = 2.0, 那么就返回2.5.

    要求用Java写,函数的signature要我自己写,所以所有数字我都定义成double。我觉
    得这就用普通的binary search吧?
    int left = 0;
    int right = len - 1;
    while(left
    回复 百度谷歌雅虎搜狗搜搜有道360奇虎

    举报

    26

    主题

    105

    帖子

    161

    积分

    注册会员

    Rank: 2

    积分
    161
    QQ
    发表于 2016-10-18 08:51:28 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


    普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
    更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
    后每个bucket里面是有序的double list.
    --

    33

    主题

    121

    帖子

    194

    积分

    注册会员

    Rank: 2

    积分
    194
    QQ
    发表于 2016-10-18 08:55:41 | 显示全部楼层
    JobHunting
    标  题: 问一个多次遇到的面试题


    我和同学被两家不同的公司考了这个题。

    输入是一个排好序的decimal数组和一个target number。要求找出这个数组中最接近
    target的数。例子:
    [1.0, 2.5, 3.0], target = 0.5, 那么就返回1.0.
    [1.0, 2.5, 3.0], target = 2.0, 那么就返回2.5.

    要求用Java写,函数的signature要我自己写,所以所有数字我都定义成double。我觉
    得这就用普通的binary search吧?
    int left = 0;
    int right = len - 1;
    while(left <= right) {
        int mid = ...;
        然后比较大小左右移动left和right
    }

    请问这道题的陷阱在哪里呢?既然他问的是decimal,而不是integer,那么应该有陷阱。

    followup question是怎么能做到比O(lg n)更快。前提是函数只被call一次,不是多次
    被call。

    --

    37

    主题

    110

    帖子

    202

    积分

    注册会员

    Rank: 2

    积分
    202
    QQ
    发表于 2016-10-18 09:12:45 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


    貌似数组中即使有duplicated number也不会怎样,仍旧可以使用传统的binary search
    【 在 sunvssoon (sunvssoon) 的大作中提到: 】
    : 普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
    : 更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
    : 后每个bucket里面是有序的double list.



    --

    21

    主题

    95

    帖子

    143

    积分

    注册会员

    Rank: 2

    积分
    143
    QQ
    发表于 2016-10-18 09:24:59 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


    感觉bucket和hashtable预处理都要O(n) 理论上binary search是最快的。但是这个题
    Trinary search 会不会快一些? 选left=(begin+end)/3, right=2*(begin+end)/3,
    然后比较看在target在三个区间哪里,再移动begin, end。但是每次选完 left和right
    , 都有可能要compare two times, 所以会不会更快好像要证明一下。

    【 在 crewyou () 的大作中提到: 】
    : 我和同学被两家不同的公司考了这个题。
    : 输入是一个排好序的decimal数组和一个target number。要求找出这个数组中最接近
    : target的数。例子:
    : [1.0, 2.5, 3.0], target = 0.5, 那么就返回1.0.
    : [1.0, 2.5, 3.0], target = 2.0, 那么就返回2.5.
    : 要求用Java写,函数的signature要我自己写,所以所有数字我都定义成double。我觉
    : 得这就用普通的binary search吧?
    : int left = 0;
    : int right = len - 1;
    : while(left <= right) {
    : ...................


    --
    Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
    Would you capture it or just let it slip?

    30

    主题

    99

    帖子

    157

    积分

    注册会员

    Rank: 2

    积分
    157
    QQ
    发表于 2016-10-18 09:34:36 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


        //return the closet number
        public double closestNumber(double[] nums, double target) {
            if (nums == null || nums.length == 0) {
                return -1;
            }
            int low = 0, high = nums.length - 1;
            while (low < high) {
                int mid = low + (high - low) / 2;
                double diff1 = Math.abs(nums[mid] - target);
                double diff2 = Math.abs(nums[mid + 1] - target);
                if (diff1 >= diff2) {
                    low = mid + 1;
                } else {
                    high = mid;
                }
            }
            return nums[high];
        }


    follow up怎么做?
    --

    20

    主题

    80

    帖子

    128

    积分

    注册会员

    Rank: 2

    积分
    128
    QQ
    发表于 2016-10-18 09:41:10 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


    怎么query bucket呢.
    【 在 sunvssoon (sunvssoon) 的大作中提到: 】
    : 普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
    : 更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
    : 后每个bucket里面是有序的double list.



    --

    28

    主题

    94

    帖子

    158

    积分

    注册会员

    Rank: 2

    积分
    158
    QQ
    发表于 2016-10-18 09:52:28 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


    很久前面O记问到过这道题,答曰:数组中的数减去target的值然后找出绝对值最小的
    即可
    --

    27

    主题

    88

    帖子

    147

    积分

    注册会员

    Rank: 2

    积分
    147
    QQ
    发表于 2016-10-18 10:14:34 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


    产生buckets不是需要O(n)?
    [在  sunvssoon (sunvssoon) 的大作中提到:]
    :普通解法就是binary search 吧, 找到离这个target的左右邻居, 比较下就行。
    :更快是不是bucket idea, 分成[0,1), [1,2) [2,3), 假如太细的话, 可以多层, 然
    :后每个bucket里面是有序的double list.
    --

    20

    主题

    106

    帖子

    147

    积分

    注册会员

    Rank: 2

    积分
    147
    QQ
    发表于 2016-10-18 11:03:24 | 显示全部楼层
    JobHunting
    标  题: Re: 问一个多次遇到的面试题


    最好的结果就是binary searchhttps://www.quora.com/Search-Algorithms-Why-cant-
    there-be-an-algorithm-faster-than-binary-search
    不过有一种叫interpolation search的利用插值,可以在数据均匀的情况下更快,但也
    可能更慢。你可以设计一种新的算法,把binary search和interpolation search结合
    起来。很插值,插几轮效果不好,就去binary.
    【 在 crewyou () 的大作中提到: 】
    : 我当时就说如果数组是排好序的数组,里面的元素没什么特征,那么最好只能是log
    n
    : 。然后我说肯定有trap,于是跳出binary search后我做了越界等检查,也注意了全程
    : 使用double类型。
    : 后来想了想,即使数组中有重复元素,还是要用binary search。



    --
    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -问一个多次遇到的面试题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -问一个多次遇到的面试题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
    Sasa.com

    Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

    本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

    安全联盟认证 安全联盟认证

    快速回复 返回顶部 返回列表