Snapchat - IPFilter

https://warmland.gitbooks.io/algorithm/content/interview/snapchat_-_ipfilter.html

首先说一下IP，二进制表示的IP有32位，一般8位一分隔，转换成十进制，就是0.0.0.0 ~ 255.255.255.255

给你一些IP的规则，比如"7.7.7.7/8","123.2.67.3/8"，这个代表着比如7.7.7.7所对应的32位的表示，00000111*4，8表示取前8位，把所有以00000111开头的ip地址都看成一组，如果在这组内就被filter掉。

所以思路是：

1. 建立ipRule的trie，提供搜索的功能
2. 搜索

分析& 代码

public List<String> filter(List<String> rules, List<String> IPs) {
    if(rules == null || rules.size() == 0 || IPs == null || IPs.size() == 0) {
        return IPs;
    }
    Trie ruleTrie = new Trie();
    prepareRule(ruleTrie, rules);
    List<String> res = new ArrayList<String>();
    filterIPs(IPs, ruleTrie, res);
    return res;
}


private void prepareRule(Trie ruleTrie, List<String> rules) {
    for(String rule: rules) {
        StringBuilder sb = new StringBuilder();
        String[] parts = rule.split("/");
        int bits = Integer.parseInt(parts[1]);
        String[] ipBlocks = parts[0].split("\\.");
        for(String block: ipBlocks) {
            String blockStr = Integer.toBinaryString(Integer.parseInt(block));
            int leadingZeros = 8 - blockStr.length();
            while(leadingZeros-- > 0) {
                sb.append("0");
            }
            sb.append(blockStr);
        }
        String curRule = sb.toString().substring(0, bits);
        ruleTrie.insert(curRule);
    }
}

private void filterIPs(List<String> IPs, Trie ruleTrie, List<String> res) {
    for(String ip: IPs) {
        StringBuilder sb = new StringBuilder();
        String[] ipBlocks = ip.split("\\.");
        for(String block: ipBlocks) {
            String blockStr = Integer.toBinaryString(Integer.parseInt(block));
            int leadingZeros = 8 - blockStr.length();
            while(leadingZeros-- > 0) {
                sb.append("0");
            }
            sb.append(blockStr);
        }
        String binaryIP = sb.toString();
        if(!ruleTrie.startsWith(binaryIP)) {
            res.add(ip);
        }
    }
}


class TrieNode {
    char c;
    boolean isLeaf;
    TrieNode[] children;

    public TrieNode() {
        children = new TrieNode[2];
        isLeaf = false;
    }
}

class Trie {
    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String s) {
        if(s == null || s.length() == 0) {
            return;
        }
        TrieNode cur = root;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - '0';
            if(cur.children[index] == null) {
                cur.children[index] = new TrieNode();
            }
            cur.children[index].c = c;
            cur = cur.children[index];
        }
        cur.isLeaf = true;
    }

    public boolean startsWith(String s) {
        TrieNode cur = root;
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int index = c - '0';
            if(cur.isLeaf == true) {
                return true;
            }
            if(cur.children[index] == null) {
                return false;
            }
            cur = cur.children[index];
        }
        return cur.isLeaf;
    }
}

public static void main(String[] args) {
    IPFilter sample = new IPFilter();
    List<String> rules = new ArrayList<String>(Arrays.asList("7.7.7.7/8","123.2.67.3/8"));
    List<String> IPs = new ArrayList<String>(Arrays.asList("23.2.4.1","7.3.4.1","5.1.2.3","123.2.67.3"));
    List<String> res = sample.filter(rules, IPs);
    System.out.println(res);
}

https://en.wikipedia.org/wiki/Subnetwork