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

 找回密码
 立即注册

点击进入授权页面

只需一步,快速开始

  • 交警蜀黍把交通违法的人做成了表情包 火了!
  • 福岛核事件“产出”新血型?专家说话了
  • 如果太阳突然消失……人类彻底惨了
  • 俄罗斯联盟火箭连续失败!最关键原因无解
  • 宁波16岁少女减肥 暴瘦18斤猝死
  • 石榴籽能吃吗?没想到有这么多好处
  • 新发现!人类大脑就是台量子计算机:如此神奇
  • 最先进波音客机:首架787-10开始最终装配
  • 深夜虐狗:那些秀恩爱的动物们 单身汪不哭!
  • 河南农民挖出人形何首乌:样子太污了
  • 在纽约购置学区房不但能让子女获得优质教育,而且能获取学区房增值的红利-美国投资指 ...
  • 战略家:现在是金融类股的反弹消退的时候了
  • 苹果可能在2017年看到一个“惊喜”的反弹
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3109|回复: 12

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

[复制链接]
TA在交友中心
0 0 26
  @ME:   

11

主题

23

帖子

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奇虎

举报

TA在交友中心
0 0 56
  @ME:   

24

主题

89

帖子

132

积分

注册会员

Rank: 2

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


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

28

主题

100

帖子

154

积分

注册会员

Rank: 2

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

--

TA在交友中心
0 0 78
  @ME:   

32

主题

95

帖子

176

积分

注册会员

Rank: 2

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



--
TA在交友中心
0 0 38
  @ME:   

16

主题

81

帖子

116

积分

注册会员

Rank: 2

积分
116
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?
TA在交友中心
0 0 49
  @ME:   

24

主题

85

帖子

131

积分

注册会员

Rank: 2

积分
131
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怎么做?
--
TA在交友中心
0 0 43
  @ME:   

17

主题

76

帖子

113

积分

注册会员

Rank: 2

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



--
TA在交友中心
0 0 50
  @ME:   

21

主题

78

帖子

122

积分

注册会员

Rank: 2

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


很久前面O记问到过这道题,答曰:数组中的数减去target的值然后找出绝对值最小的
即可
--
TA在交友中心
0 0 48
  @ME:   

21

主题

74

帖子

117

积分

注册会员

Rank: 2

积分
117
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.
--
TA在交友中心
0 0 33
  @ME:   

16

主题

94

帖子

118

积分

注册会员

Rank: 2

积分
118
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 华人娱乐论坛发布的内推面经 -问一个多次遇到的面试题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -问一个多次遇到的面试题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
1&1 Hosting

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

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

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

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