一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 785|回复: 11
收起左侧

[算法题] 一道面试题,Ip地址范围找到对应城市

[复制链接] |试试Instant~ |关注本帖
oneshot 发表于 2015-11-9 09:33:41 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
  给一个text file,里面是IP地址的范围,和对应的城市(ex, 192.168.1.0 --- 192.168.1.255,   Boston). 设计一个算法,输入一个具体的IP地址,返回对应的城市。如果IP地址不在任何range之内,返回null。  在一个面经里面看到的题,没有想到什么好方法,求助。
水逼一枚 发表于 2015-11-9 09:57:31 | 显示全部楼层
请问一下楼主这是哪个公司的面经呢?
回复 支持 反对

使用道具 举报

 楼主| oneshot 发表于 2015-11-9 11:27:55 | 显示全部楼层
水逼一枚 发表于 2015-11-9 09:57
请问一下楼主这是哪个公司的面经呢?

TripAdvisor的,这个要怎么做啊?
回复 支持 反对

使用道具 举报

daniel647 发表于 2015-11-9 11:31:00 | 显示全部楼层
oneshot 发表于 2015-11-9 11:27
TripAdvisor的,这个要怎么做啊?

问一下lz这是哪个position啊
回复 支持 反对

使用道具 举报

 楼主| oneshot 发表于 2015-11-9 12:34:29 | 显示全部楼层
daniel647 发表于 2015-11-9 11:31
问一下lz这是哪个position啊

不清楚啊 我也是看的面经合集里面的一道题。。。这个题要怎么做啊?
回复 支持 反对

使用道具 举报

sniperwrb 发表于 2015-11-9 14:31:57 | 显示全部楼层
我想想
建个数组排序完了二分
回复 支持 反对

使用道具 举报

readman 发表于 2015-11-9 14:38:29 | 显示全部楼层
3数一组做trie
回复 支持 反对

使用道具 举报

flashstar 发表于 2015-11-16 07:27:31 | 显示全部楼层
建立一个BST,叶子的节点储存 城市和IP地址的边界值,中间的节点只存IP边界值,拿到一个IP地址,按照BST方式搜索,找到2个叶子节点夹住的区间,所在的城市就是对应城市。要考虑一些边界情况。如果BST比较balance, 复杂度是logN
回复 支持 反对

使用道具 举报

flashstar 发表于 2015-11-16 13:01:46 | 显示全部楼层
flashstar 发表于 2015-11-16 07:27
建立一个BST,叶子的节点储存 城市和IP地址的边界值,中间的节点只存IP边界值,拿到一个IP地址,按照BST方 ...

不过从简单程度来说还是前面的数组最简单。
建立一个排序数组,里面存 IP边界值和相关的 城市,  然后二分法查找最容易。
回复 支持 反对

使用道具 举报

krrk 发表于 2015-11-16 13:20:37 | 显示全部楼层
b tree怎么样
回复 支持 反对

使用道具 举报

lidongmeng0213 发表于 2015-12-3 08:50:42 | 显示全部楼层
线段树应该可以吧,这种范围查询,用线段树是不是好一些~当然你得设置一个ip地址比较函数~
回复 支持 反对

使用道具 举报

quan1614 发表于 2015-12-20 16:31:18 | 显示全部楼层
ip address-> int   作索引-> 区间树国内好想去国外工作  
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 06:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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