ip2cidr - Airbnb


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,就理解了
解释: ——代表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
 * 输入一个ip,和一个count来表示一组ip, e.g.   7.7.7.7和3表示 7.7.7.7, 7.7.7.8, 7.7.7.9, 
 * 输出这组ip的CIDR形式.CIDR表达是: ip地址/掩码位数 表示一个区间
 * 比如 0.0.0.8 / 30 就是以0.0.0.8为准,前30位不能变--》0.0.0.(0000 10 00)--0.0.0.(0000 10 11) 
 * 然后给你一个起始ip,和数量。用最少的cidr表示这个区间
 public static void main(String[] args) {
  String ip = "7.7.7.7";
  int count = 3;
  CIDR cidr = new CIDR();
  String binaryIP = cidr.decimalToBinary(ip);
  List<String> cidrs = new LinkedList<>();
  cidr.getCIDRS(binaryIP, count, cidrs);
  for (String cidrIP : cidrs) {
   System.out.println(cidrIP);
  }
 }
 
 public void getCIDRS(String binaryIP, int count, List<String> res) {
  while (count > 0) {
   int zero = 0, last = binaryIP.length() - 1;
   while (last >= 0 && binaryIP.charAt(last) == '0') {
    if (count - (int) Math.pow(2, zero + 1) >= 0) {
     zero++;
     last--;
    } else {
     break;
    }
   }
   String cidrIP = binaryToDecimal(binaryIP) + "/" + (32 - zero);
   System.out.println("Found one CIDR " + cidrIP);
   res.add(cidrIP);
   count -= (int) Math.pow(2, zero);
   binaryIP = getNextBinaryIP(binaryIP, zero);
  }
  
 }
 
 public String getNextBinaryIP(String prevIp, int lastZero) {
  System.out.println("prevIP " + prevIp);
  int one = 32 - 1 - lastZero;
  while (one >= 0 && prevIp.charAt(one) == '1') {
   one--;
  }
  StringBuilder res = new StringBuilder(prevIp.substring(0, one));
  res.append("1");
  while (res.length() < 32) {
   res.append("0");
  }
  return res.toString();
 }
 
 public String binaryToDecimal(String binaryIP) {
  StringBuilder sb = new StringBuilder();
  for (int i = 0; i < binaryIP.length(); i += 8) {
   String subBinary;
   if (i < 24) {
    subBinary = binaryIP.substring(i, i + 8);
   } else {
    subBinary = binaryIP.substring(i);
   }
    
   Integer sub = Integer.parseInt(subBinary, 2);
   sb.append(sub);
   if (i < 24) {
    sb.append(".");
   }
  }
  System.out.println("convert " + binaryIP + " to " + sb.toString());
  return sb.toString();
 }
 
 public String decimalToBinary(String decimalIP) {
  StringBuilder sb = new StringBuilder();
  String[] ips = decimalIP.split("\\.");
  for (int i = 0; i < ips.length; i++) {
   Integer sub = Integer.parseInt(ips[i]);
   String binarySub = Integer.toBinaryString(sub);
   int missingDigit = 8 - binarySub.length();
   String zeros = "";
   while (missingDigit > 0) {
    zeros += "0";
    missingDigit--;
   }
   sb.append(zeros + binarySub);
  }
  System.out.println("convert " + decimalIP + " to " + sb.toString());
  return sb.toString();
 }

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/ˈsdər/ or /ˈsɪdər/) is a method for allocating IP addresses and IP routing.\

无类别域间路由(Classless Inter-Domain Routing、CIDR)是一个用于给用户分配IP地址以及在互联网上有效地路由IP数据包的对IP地址进行归类的方法。
一个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中已不再使用。





Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts