美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 小龙女报警抓母不算啥!朱茵曾说过的话才是惊恐
  • 何洁过生日晒美照 自称为爱奋不顾身付出
  • 原来左撇子的甜馨字这么漂亮,老爸贾乃亮都自叹不如
  • 体验生活?薛之谦被曝KTV撩妹抽烟
  • 章子怡好继母人设崩塌?小苹果一直跟奶奶住
  • 安琥签约诚利风尚迎首秀?亮相Cabbeen时装发布会
  • 大家更爱健康:可口可乐、百事可乐心酸没人喝
  • 秘鲁10年一遇洪灾 男子洪水中开车:这一幕太惊险
  • 海豚猛撞河豚竟为逼出毒素:吸了会兴奋上瘾
  • 汪小菲为老婆儿女做什么了能让大S这样称赞?
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3133|回复: 12

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

    [复制链接]

    11

    主题

    25

    帖子

    49

    积分

    新手上路

    Rank: 1

    积分
    49
    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

    主题

    103

    帖子

    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.
    --

    32

    主题

    112

    帖子

    179

    积分

    注册会员

    Rank: 2

    积分
    179
    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。

    --

    34

    主题

    101

    帖子

    187

    积分

    注册会员

    Rank: 2

    积分
    187
    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.



    --

    19

    主题

    89

    帖子

    132

    积分

    注册会员

    Rank: 2

    积分
    132
    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?

    29

    主题

    93

    帖子

    152

    积分

    注册会员

    Rank: 2

    积分
    152
    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怎么做?
    --

    19

    主题

    80

    帖子

    127

    积分

    注册会员

    Rank: 2

    积分
    127
    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.



    --

    25

    主题

    89

    帖子

    146

    积分

    注册会员

    Rank: 2

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


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

    23

    主题

    81

    帖子

    133

    积分

    注册会员

    Rank: 2

    积分
    133
    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.
    --

    18

    主题

    101

    帖子

    138

    积分

    注册会员

    Rank: 2

    积分
    138
    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|唐人社区

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

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