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

 找回密码
 立即注册
  • 你知道麻、木吗?学问可大了
  • 中国第一颗卫星东方红一号:现在是太空垃圾吗?
  • 这种布能自动修复 再也不用担心划破衣服
  • 英国大狗重如小象:每月吃千元狗粮 还很瘦
  • 气象台主持人遭雷击:火花四溅 险些殉职
  • 中华神箭!长征五号火箭二次起航
  • 中国女游客南非突遭猎豹袭击:跪地尖叫
  • 公司被曝剽窃创意?黄磊:不清楚细节 有错会认
  • 台湾女孩6岁骑行千里丝路 9年来横越亚非、北美多国
  • 霸气!朱婷率瓦基弗夺留洋首冠 荣膺欧冠MVP
  • 在自动驾驶汽车技术的推动下,苹果更加强大
  • 标普500低于50日平均移动线,接下来将是横向盘整时期
  • 阿里巴巴增长超越市场预期,阿里云会进一步扩大
  • 今年5大股票支撑着市场
  • IBM:它会从小的事情重新开始
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3135|回复: 12

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

[复制链接]

13

主题

28

帖子

57

积分

新手上路

Rank: 1

积分
57
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
新浪微博官方账号】美国省钱快报FunInUSA : 每日滚动更新美国市场折扣资讯微商进货首选资讯渠道。
回复 百度谷歌雅虎搜狗搜搜有道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

主题

116

帖子

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。

--

35

主题

103

帖子

192

积分

注册会员

Rank: 2

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

主题

91

帖子

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

主题

94

帖子

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

主题

90

帖子

146

积分

注册会员

Rank: 2

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


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

23

主题

82

帖子

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

19

主题

102

帖子

141

积分

注册会员

Rank: 2

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

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

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