Binary Search in Array
Recently CodeAbbey got functionality to determine user's country by IP. Each IP is in its core a kind of
imprecise internet address from which user's connection is coming to our server. All which is important to know - the
IP could be represented as
32-bit integer (from
(please do not worry about privacy and conspiracy - you always can change the country to anything including
in your profile settings if you really want to)
This feature uses a list of IP-ranges, sorted in ascending order - and for each range of addresses some country is assigned. This originally looks as following:
range start range end country code ------------- --------------- ------------ 0.0.0.0 0.255.255.255 US 18.104.22.168 22.214.171.124 AU 126.96.36.199 188.8.131.52 CN ... 184.108.40.206 220.127.116.11 AU 18.104.22.168 255.255.255.255 US
Here IP-s are given in special ip format with
4 numbers for each byte (consisting of
When we have some unknown IP, like
22.214.171.124 (currently this is mine - and you can check yours with
special tool) - we may use the following algorithm over this list:
Kat which range-start is less or equal to given IP, while at line
K+1range-start is strictly greater;
K-th line and output the country code for this line (otherwise report the country is unknown).
For those curious such (not very precise) lists could be found on internet freely (while more exact ones are to be purchased, usually). I've downloaded one from db-ip.com.
You are given few thousands of IPs and you should return country codes for them. You will have only
1 minute to
submit the answer, so probably it is better to use binary search rather than iterate through the list.
You may click it with the right mouse button and choose "Save As". Note that the file has unix-style line ends, so some editors in windows could show it incorrectly, but you will anyway easily read separate lines programmatically.
The file has the slightly different format:
0 9zldr US 9zlds 73 AU 9zlkw lb CN ... 1q5gzcw 2db AU 1q5h1q8 8vn08v US
The integers of the first two columns are given in the numeral system with base 36 (just to make them shorter) - so that for example in Python you may use something like this to convert them to ints:
s = '9zlkw' n = int(s, 36)
The first integer in the line is the range-start itself. The second is the offset of range-end:
range_end = range_start + offset
For example in the second line offset is
73 which, converted to decimal, gives
255 - and you can check above that
this line really cares about IPs from
Of course you may preprocess this file after downloading (for example, converting values to decimals if you like etc) - but it is not necessary.
Input data will provide the amount of IPs to be processed in the first line.
Next lines will contain single IP each, also in
Answer should give country codes for these IPs, as two-letter tokens separated by spaces.
input data: 10 1keei5f bixots 1mmfpia dwaviz q0a5p9 l600w7 it4w75 ht85qa 1gvvigc hg8y3f answer: AU BJ TW IN GB GE US CA EC PT