Snap面经题目:IP Filter

0002505492

题目:

提供一些ip mask和一个ip address 寻找 最长的匹配。

思路:

显然是Trie。

代码:

 

class TrieNode
{
	String mask;
	TrieNode[] next;
	public TrieNode()
	{
		next = new TrieNode[2];
	}
}
public class Solution {
	static TrieNode root;
	public static void main(String[] args)
	{
		int i = 255;
//		System.out.println(Integer.toString(i, 2));
		String[] mask = {"4.0.0.0/8", "201.10.6.0/23", "201.10.0.0/21", "126.255.103.0/24"};
		String output = IPfilter("201.10.6.17", mask);
		System.out.println(output);
	}
	
	

	private static String IPfilter(String string, String[] mask) {
		// TODO Auto-generated method stub
		root = new TrieNode();
		buildTrie(mask, root);
		return find(root, string);
	}



	private static String find(TrieNode root, String string) {
		// TODO Auto-generated method stub
		String ans = null;
		String base2Add = convert(string);
		TrieNode cur = root;
		for(int i = 0; i < 32; i++)
		{
			int k = base2Add.charAt(i) - '0';
			cur = cur.next[k];
			if(cur == null) break;
			if(cur.mask != null) ans = cur.mask;
		}
		return ans;
	}



	private static void buildTrie(String[] mask, TrieNode root) {
		// TODO Auto-generated method stub
		for(String m: mask)
		{
			TrieNode cur = root;
			String[] split = m.split("/");
			String base2Add = convert(split[0]);
			int prefix = Integer.parseInt(split[1]);
			for(int i = 0; i < prefix; i++)
			{
				int k = base2Add.charAt(i) - '0';
				if(cur.next[k] == null) cur.next[k] = new TrieNode();
				cur = cur.next[k];
			}
			cur.mask = m;
		}
	}



	private static String convert(String string) {
		// TODO Auto-generated method stub
		StringBuilder sb = new StringBuilder();
		String[] split = string.split("\\.");
		for(String s: split)
		{
			int tmp = Integer.parseInt(s);
			sb.append(String.format("%8s", Integer.toBinaryString(tmp)).replace(" ", "0"));
		}
		return sb.toString();
	}
}




输出:

201.10.6.0/23

393total visits,1visits today