airbnb面试题汇总
给出一个ipv4的range，找出最少的cidr可以覆盖这个range内的所有ip。
参考：
背景介绍https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing
这个是个online转化工具http://www.ipaddressguide.com/cidr
大概的思路是group as much IPs as you can.
描述起来还真的麻烦呢，建议跑几个case，就理解了
背景介绍https://en.wikipedia.org/wiki/Classless_Inter-Domain_Routing
这个是个online转化工具http://www.ipaddressguide.com/cidr
大概的思路是group as much IPs as you can.
描述起来还真的麻烦呢，建议跑几个case，就理解了
解释： ——代表end-start能覆盖到的二进制位
start：xxxxxxx100000
end： xxxxxx——-这种情况下，先找出可以覆盖住xxxxxxx100000~xxxxxxx111111的cidr，start变为xxxxxxx100000 + 100000
end： xxxxxxxxx—-这种情况下，先找出可以覆盖住xxxxxxx100000~xxxxxxx101111的cidr，start变为xxxxxxx100000 + 10000
def ipToVal(ip):
ip = ip.split(".")
val = 0
for x in ip:
val = (val << 8) + int(x)
return val
def ValToIp(val):
ip, i = ["0"] * 4, 3
while val:
ip[i] = str(val % (1 << 8))
val /= (1 << 8)
i -= 1
return ".".join(ip)
def range2cidr(start, end):
if not start or not end or start.count('.') != 3 or end.count('.') != 3:
return None
start, end = ipToVal(start), ipToVal(end)
if start > end:
return None
ans = []
while start <= end:
firstOne = start & (-start)
maxMask = 32 - int(log(firstOne, 2))
maxDiff = 32 - int(floor(log(end - start + 1, 2)))
maxMask = max(maxMask, maxDiff)
ip = ValToIp(start)
ans.append(ip + "/" + str(maxMask))
start += 2 ** (32 - maxMask)
return ans
//C++
long ipToVal(string ip) {
long val = 0;
int i = 0;
for (int j = 0; i < 4 && j < ip.length(); ++i) {
auto nx = ip.find('.', j);
if (nx == ip.npos) {
val = (val << 8) + atoi(ip.substr(j).c_str());
++i;
break;
}
val = (val << 8) + atoi(ip.substr(j, nx - j).c_str());
j = nx + 1;
}
if (i != 4) throw "The ip is incorrect";
return val;
}
string valToIp(long val) {
string ip = "";
for (int i = 0; i < 4; ++i) {
ip = to_string(val % 256) + "." + ip;
val /= 256;
}
ip.pop_back();
return ip;
}
vector<string> range2cidr(string start, string end) {
// try...catch
long st = ipToVal(start), ed = ipToVal(end);
vector<string> ans;
while (st <= ed) {
int lastOne = st & (-st);
int maxMask = 32 - int((log(lastOne)/log(2)));
int maxDiff = 32 - int(floor(log(ed - st + 1)/log(2)));
maxMask = max(maxMask, maxDiff);
string ip = valToIp(st);
ans.push_back(ip + "/" + to_string(maxMask));
st += int(pow(2, 32 - maxMask));
}
return ans;
}
-- not work
public static List<String> range2cidrlist( String startIp, String endIp ) {
// check parameters
if (startIp == null || startIp.length() < 8 ||
endIp == null || endIp.length() < 8) return null;
long start = ipToLong(startIp);
long end = ipToLong(endIp);
// check parameters
if (start > end) return null;
List<String> result = new ArrayList<String>();
while (start <= end) {
// identify the location of first 1's from lower bit to higher bit of start IP
// e.g. 00000001.00000001.00000001.01101100, return 4 (100)
long locOfFirstOne = start & (-start);
int maxMask = 32 - (int) (Math.log(locOfFirstOne) / Math.log(2));
// calculate how many IP addresses between the start and end
// e.g. between 1.1.1.111 and 1.1.1.120, there are 10 IP address
// 3 bits to represent 8 IPs, from 1.1.1.112 to 1.1.1.119 (119 - 112 + 1 = 8)
double curRange = Math.log(end - start + 1) / Math.log(2);
int maxDiff = 32 - (int) Math.floor(curRange);
// why max?
// if the maxDiff is larger than maxMask
// which means the numbers of IPs from start to end is smaller than mask range
// so we can't use as many as bits we want to mask the start IP to avoid exceed the end IP
// Otherwise, if maxDiff is smaller than maxMask, which means number of IPs is larger than mask range
// in this case we can use maxMask to mask as many as IPs from start we want.
maxMask = Math.max(maxDiff, maxMask);
// Add to results
String ip = longToIP(start);
result.add(ip + "/" + maxMask);
// We have already included 2^(32 - maxMask) numbers of IP into result
// So the next round start must add that number
start += Math.pow(2, (32 - maxMask));
}
return result;
}
private static long ipToLong(String strIP) {
String[] ipSegs = strIP.split("\\.");
long res = 0;
for (int i = 0; i < 4; i++) {
res += Long.valueOf(ipSegs[i]) << (8 * (3 - i));
}
return res;
}
private static String longToIP(long longIP) {
StringBuffer sb = new StringBuffer();
sb.append(longIP >>> 24).append(".")
.append((longIP & 0x00FFFFFF) >>> 16).append(".")
.append(String.valueOf((longIP & 0x0000FFFF) >>> 8)).append(".")
.append(String.valueOf(longIP & 0x000000FF));
return sb.toString();
}public static List<String> range2cidrlist( String startIp, String endIp ) { long start = ipToLong(startIp); long end = ipToLong(endIp); ArrayList<String> pairs = new ArrayList<String>(); while ( end >= start ) { byte maxsize = 32; while ( maxsize > 0) { long mask = CIDR2MASK[ maxsize -1 ]; long maskedBase = start & mask; if ( maskedBase != start ) { break; } maxsize--; } double x = Math.log( end - start + 1) / Math.log( 2 ); byte maxdiff = (byte)( 32 - Math.floor( x ) ); if ( maxsize < maxdiff) { maxsize = maxdiff; } String ip = longToIP(start); pairs.add( ip+ "/" +maxsize ); start += Math.pow( 2, (32 - maxsize) ); } return pairs; } public static final int[] CIDR2MASK = new int[] { 0x00000000, 0x80000000, 0xC0000000, 0xE0000000, 0xF0000000, 0xF8000000, 0xFC000000, 0xFE000000, 0xFF000000, 0xFF800000, 0xFFC00000, 0xFFE00000, 0xFFF00000, 0xFFF80000, 0xFFFC0000, 0xFFFE0000, 0xFFFF0000, 0xFFFF8000, 0xFFFFC000, 0xFFFFE000, 0xFFFFF000, 0xFFFFF800, 0xFFFFFC00, 0xFFFFFE00, 0xFFFFFF00, 0xFFFFFF80, 0xFFFFFFC0, 0xFFFFFFE0, 0xFFFFFFF0, 0xFFFFFFF8, 0xFFFFFFFC, 0xFFFFFFFE, 0xFFFFFFFF }; private static long ipToLong(String strIP) { long[] ip = new long[4]; String[] ipSec = strIP.split("\\."); for (int k = 0; k < 4; k++) { ip[k] = Long.valueOf(ipSec[k]); } return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3]; } private static String longToIP(long longIP) { StringBuffer sb = new StringBuffer(""); sb.append(String.valueOf(longIP >>> 24)); sb.append("."); sb.append(String.valueOf((longIP & 0x00FFFFFF) >>> 16)); sb.append("."); sb.append(String.valueOf((longIP & 0x0000FFFF) >>> 8)); sb.append("."); sb.append(String.valueOf(longIP & 0x000000FF)); sb.append("."); return sb.toString(); }
For example: (using http://ip2cidr.com/)
Input 1: 5.10.64.0
Input 2: 5.10.127.255
Result: 5.10.64.0/18
Given an IPv4 IP address p and an integer n, return a list of CIDR strings that most succinctly represents the range of IP addresses from p to (p + n).
public static String cidr(String ip, int num) {
String[] ipSeg = ip.split("\\.");
int total = 0;
int segNum = 1;
for (int i = ipSeg.length - 1; i >= 0; i--) {
int seg = Integer.parseInt(ipSeg[i]);
// find the highest 1 of the seg
int end = seg + num / segNum;
if (end <= 255) {
int times = 128;
while ((seg & times) == (end & times)) {
total++;
times >>= 1;
}
total += 8 * i;
break;
} else {
num = end;
}
segNum = 256;
}
return ip + "/" + total;
}
public static void main(String[] args) {
System.out.println(cidr("1.1.1.1", 400));
}
Classless Inter-Domain Routing (CIDR, /ˈsaɪdər/ or /ˈsɪdər/) is a method for allocating IP addresses and IP routing.\
一个IP地址包含两部分：标识网络的前缀和紧接着的在这个网络内的主机地址。在之前的分类网络中，IP地址的分配把IP地址的32位按每8位为一段分开。这使得前缀必须为8，16或者24位。因此，可分配的最小的地址块有256（24位前缀，8位主机地址，28=256）个地址，而这对大多数企业来说太少了。大一点的地址块包含65536（16位前缀，16位主机，216=65536）个地址，而这对大公司来说都太多了。这导致不能充分使用IP地址和在路由上的不便，因为大量的需要单独路由的小型网络（C类网络）因在地域上分得很开而很难进行聚合路由，于是给路由设备增加了很多负担。
无类别域间路由是基于可变长子网掩码（VLSM）来进行任意长度的前缀的分配的。在RFC 950（1985）中有关于可变长子网掩码的说明。CIDR包括：
- 指定任意长度的前缀的可变长子网掩码技术。遵从CIDR规则的地址有一个后缀说明前缀的位数，例如：192.168.0.0/16。这使得对日益缺乏的IPv4地址的使用更加有效。
- 将多个连续的前缀聚合成超网，以及，在互联网中，只要有可能，就显示为一个聚合的网络，因此在总体上可以减少路由表的表项数目。聚合使得互联网的路由表不用分为多级，并通过VLSM逆转“划分子网”的过程。
- 根据机构的实际需要和短期预期需要而不是分类网络中所限定的过大或过小的地址块来管理IP地址的分配的过程。
因为在IPv6中也使用了IPv4的用后缀指示前缀长度的CIDR，所以IPv4中的分类在IPv6中已不再使用。
