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

 找回密码
 立即注册
  • 美国男子因抑郁症吞枪自杀脸全毁 10年后重获新脸
  • 世界上最致命的毒物是什么?
  • 神奇!做到这两件事死亡率下降30%:效果不输天天健身
  • 巨大家猫下水后 网友:原来是真胖
  • 在太空中捏爆气球会怎样?
  • 腰果、蔓越莓、开心果…这些植物你都见过吗?
  • 兽医疑惑收下“泥土块” 洗干净才发现是它
  • 颠覆常识:熬夜又赖床的人其实更聪明
  • 情侣亲热注意!国内电影院有360度无死角夜视摄像头
  • 为什么我们感觉不到地球的转动?
  • 机器人会导致失业,我们需要提前做准备
  • 星巴克:零售渠道发展
  • 大多退休职工仍在继续工作
  • AMD“Ryzen”:试图占据更多市场份额
  • Square股票超出预期,上涨44%
  • 美国各地雇员加入“无移民”抗议活动而被解雇
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3131|回复: 12

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

[复制链接]

11

主题

24

帖子

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【中国海淘拼单总群】36382164
回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

24

主题

96

帖子

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

31

主题

107

帖子

176

积分

注册会员

Rank: 2

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

主题

99

帖子

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.



--

18

主题

86

帖子

128

积分

注册会员

Rank: 2

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

27

主题

91

帖子

145

积分

注册会员

Rank: 2

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

主题

78

帖子

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.



--

24

主题

85

帖子

141

积分

注册会员

Rank: 2

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


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

21

主题

79

帖子

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

17

主题

98

帖子

132

积分

注册会员

Rank: 2

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

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

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