onsite面试问题一道 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

onsite面试问题一道

onsite面试问题一道# JobHunting - 待字闺中

c*y2013-05-17 07:05

1 楼

给定一个文件，里面包括n个IP/Mask的entry（例如10.1.1.0/24)。给出k个子网掩码，
例如10.1.0.0/16。对于每一个子网掩码，从文件找出所有符合这个子网掩码的entry。
例如对于子网掩码10.1.0.0/16，10.1.1.0/24是一个符合条件的，但是10.2.1.0/24就
不是。
允许可以用任何数据结构preprocess这n个entry，要求对于每个子网掩码，返回一个
linkList，里面包含所有符合entry。
Preprocessing的memory和computation开销不算，但是通过使用这个数据结构，对于每
个子网掩码的查找操作(即返回这个linklist)要求是O(1)。

R*12013-05-17 07:05

2 楼

BST? node value is 0 or 1, and the level indicates the bit index.
给定一个mask，就是从MSB开始从root下来，找到对应的level，这个subtree就包含所
有符合条件的entries.
search for subtree's root is O(1) since there are at most 24 levels. But
preparing the linked list needs to traverse the subtree, which takes O(N), N
is the size of the returned linked list.
不知道这样对不对？

【在 c**y 的大作中提到】

: 给定一个文件，里面包括n个IP/Mask的entry（例如10.1.1.0/24)。给出k个子网掩码，
: 例如10.1.0.0/16。对于每一个子网掩码，从文件找出所有符合这个子网掩码的entry。
: 例如对于子网掩码10.1.0.0/16，10.1.1.0/24是一个符合条件的，但是10.2.1.0/24就
: 不是。
: 允许可以用任何数据结构preprocess这n个entry，要求对于每个子网掩码，返回一个
: linkList，里面包含所有符合entry。
: Preprocessing的memory和computation开销不算，但是通过使用这个数据结构，对于每
: 个子网掩码的查找操作(即返回这个linklist)要求是O(1)。

c*y2013-05-17 07:05

3 楼

又见牛人，好像就是这个解法。

s*x2013-05-17 07:05

4 楼

mark

N
★ 发自iPhone App: ChineseWeb 7.8

【在 R******1 的大作中提到】

: BST? node value is 0 or 1, and the level indicates the bit index.
: 给定一个mask，就是从MSB开始从root下来，找到对应的level，这个subtree就包含所
: 有符合条件的entries.
: search for subtree's root is O(1) since there are at most 24 levels. But
: preparing the linked list needs to traverse the subtree, which takes O(N), N
: is the size of the returned linked list.
: 不知道这样对不对？

R*12013-05-17 07:05

5 楼

仔细想想，说的不太准确。大致意思是对的，但是应该是binary tire, 而不是BST。

【在 c**y 的大作中提到】

: 又见牛人，好像就是这个解法。