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

 找回密码
 立即注册
  • Rain金泰希五年恋爱长跑修正果 鸟叔唱婚礼祝歌
  • 少时徐贤发个人专辑 望展现专属的音乐风韵和品味
  • baby香港顺利生子
  • 为了挽回佟丽娅 陈思诚把头像换成了这张照片
  • 赵薇刘烨素颜合影 两人似乎都喝醉了
  • Angelababy香港顺产生子 黄晓明全程陪护
  • 真敬业!孙俪晒海量剧本 台词标记密密麻麻
  • Baby顺利产子 老公黄晓明曾贴心探班当大厨
  • 欧阳娜娜母亲回应女儿恋上房祖名:大家都疯了
  • 杨紫被偶像赵薇"翻牌" 激动感慨:让我哭会儿先
  • 2008年以来英镑对美元的最佳战绩
  • 特朗普的不确定性带来银行股票最糟糕的一天
  • 谷歌曾反对特朗普,现在想找到共处的方法
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3127|回复: 12

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

[复制链接]

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

举报

24

主题

92

帖子

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

28

主题

103

帖子

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。

--

33

主题

98

帖子

183

积分

注册会员

Rank: 2

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



--

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?

24

主题

87

帖子

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

17

主题

77

帖子

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.



--

23

主题

83

帖子

137

积分

注册会员

Rank: 2

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


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

21

主题

75

帖子

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

16

主题

95

帖子

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

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

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

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

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