Interview Questions And Answers 
-
This question was asked at Yahoo.
There are set of ip address set of the form
10.10.10.10 - 20.20.20.20 -> cable, USA
20.20.20.21 - 33.32.31.30 -> DSL, Germany
.
.
.
250.250.250.250 - 256.256.256.256 -> cable, FranceWhich indicates all ip addresses between 10.10.10.10 to 20.20.20.20 are of type ‘cable’ and belong to the country USA, similarly with other ip address set.
Question:
————
Arrange this data into a data structure in such a way that given an ip address (e.g. 21.21.21.21) retrieve the type of service (cable, DSL.. ) and country (USA, Getrmany..) in the fastest possible way.Note: the number of such ip address sets could be very large. Also for every ip address between the start(10.10.10.10) and end (256.256.256.256) there is a type and country associated.
8,110 Views |
(30 votes, avg: 4.27)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Assumption : all sets contains consecutive group of ips.
First for each set translate its start ip into a 32 bit unsigned number (set no). Also find its set size. (last ip’s no. - first ip’s no. + 1).
Now construct a BTree of set nos (one unsigned no for each set). so that it points to its type and country (data/value) ..
Given an ip gets it unsigned no. (i) Search the B Tree for largest no. (a)
Santosh’s idea is perfect and a minor improvement over it:
Since the data is static and are interested only in the search, just an array will suffice.
Worst case:
Every group has just 1 IP, so there are 2^32 entries (ignoring the 10000 addresses between 0.0.0.0 and 10.10.10.10).
Every entry is startIP(4)+endIP(4)+Type(10)+Country(2) = 20 bytes => 80GB of memory space required. You surely need a harddrive for this.
How do you organize this data for fast search?
1. Just sort the entries and use binary search. A search would take, in the worst case log(2^32) = 32 steps. Search time is 32 seek&read.
2. Construct a tree. Since the tree is written on hard drive you need to optimize read & seek access: continuous read is cheap, but seek will kill any hard drive.
You need to maximize the number of child nodes within every internal node minimizing the tree depth, but every node should fit in a disk block => 129-513 B-tree. The maximum depth is log(2^32) base (129-513) = 15-12. Search time is 12-15 seek&read.
You would also need extra space for leaf pointers: at least +8bytes per entry => +32GB of additional space.
The B-tree performs much better than binary search on disk stored arrays.
Improvement: Use a hash to order the tree such that most frequently searched groups are close to top. But perhaps a cache would be enough and much simpler to implement.
What if the list is small? (in reality it has ~100 000 entries)
100000 * 20B = 2MB that’s easy to fit in RAM.
All you have to do is: sort it, and use binary search in O(log(n)) time.
IMO: No tree structure performs better than binary search on RAM stored arrays.
so we can group the ips and store them into defferent files.
for example
0.0.0.0~0.0.0.256 (group 1) (file 1)
then create the index to map the range
convert ip into binary type for example
convert 0.0.0.20 to 0000 0000 0000 10100
every ip has 32bit and reference an int number
then create the index to map the type and country
for example
UAS — 0000L (you can modify accord the act)
Germany —-0001L
catch —– 0000L (you can modify accord the act)
DSL —- 0001L
store these two map into two files
so we now can compute the size of every ip file.
every element in the file contains 32bit + 4 bytes + 4bytes
this is easy seek for search time.
How to work:
Read the Type and country map file into the Ram and create a table. This table will point the rigtht position of ip rang file.
Read the ip rang map and create a table.
if you give a ip address 0.0.0.20, the programme will map the right ip file and seek the right position to get the information(eg.20 0001 0001).Then it will use 0001 and 0001 to search the Type table and country map to get the final infomation.
we can use the binary search
Assuming static data and highest priority is speed.
Use O(1) bucket sort for near instant retrieval.
Map out all the data so every possible IP address points at a node that points to the corresponding type (e.g. cable) and country (e.g. USA).
One way to do this would be to make an array size 256 where each element of the array points to an array of size 16777216.
The first array will represent the first segment in IPV4 (e.g. 123.###.###.### 123 would index into first array)
Next the remaining three numbers are converted into an integer to index into the pointed to array by the first step. This can be done by bit shifting. e.g. (###.Num1.Num2.Num3 the number could be calculated by
index2 = Num1
Assumption: The union of IP address ranges is the set of [0.0.0.0, 255.255.255.255], if not you can add dummy sets that don’t go anywhere in the holes for a max of O(n) extra entries in your data structure (which will not make the running time or memory usage any worse).
Solution: Using a patricia tree with an int32 as the key and the alphabet being {0,1}, insert all of the IP address ranges beginning address only, for the value insert the Type,Country.
To look up Type,Country given an IP in the range, simply try to match the IP as far as possible down the patricia tree as possible. If you hit a key, great, there’s your range.
Otherwise, find a key in the tree that is smaller than the IP you were trying to lookup, but is closer to the IP than any other key that is smaller. To do this, go up a level until you find a valid pointer on the left link to a 0. After that go through it and stay right-most as far as possible. Once you find the smaller-closest key, there is the Type,Range.
Running-time: O(1) since IPs are 32-bit.
Memory usage: O(n) where n=# of IP ranges given in the beginning.
There is no better running time/memory usage possible.
—-
Michael, your solution is similar to mine, as you’ve built what resembles a patricia tree. However your constant memory is very large and unwieldy for situations when n is very small.
To anyone who was wondering, the practical application of this solution is IP routing. Typically in an IP you will look at your routing table and forward the IP packet to whomever has the longest prefix. Obviously O(1) is very useful since it makes it much easier to give response guarantees regardless of how big your routing table gets.
Assumption, we have enough hard disk and RAM (Approximate 10 MB disk space and similar size RAM available)
each IP will map to an index of array of 2 byte data.
1 byte will be country code another will be device code)
country code will be another index for country name in a array.
device code will be similar.
Leave an Answer/Comment