java二道面试题 - ITeye问答

0 0

java二道面试题5

2个问题

1.有一个邮箱，有一千万条黑名单用户，怎么判断收件箱是不是黑名单用户。
据说和字典什么的是属于同一个经典问题。。

2.求一个字符串中最长的颠倒字符串。。
比如 a123ghfuhg321asd131.(就是a123,321a.)

Java

2014年8月21日 13:34

lyy3323
3
0 1 6

采纳的答案

1.有一个邮箱，有一千万条黑名单用户，怎么判断收件箱是不是黑名单用户。
据说和字典什么的是属于同一个经典问题。。

这个肯定是用布隆过滤算法,楼主可以网上去找找算法. 用map的瓶颈就是内存.
优点:对比用MAP来存储,内存需要量急剧减少.检索速度超快.
缺点:会有一定的误判,会把不是黑名单的判断成黑名单.但是不会漏判断.

2.求一个字符串中最长的颠倒字符串。。
比如 a123ghfuhg321asd131.(就是a123,321a.)
这个问题不是几句话能搞明白,楼主可以看看这个博客.里面有大量的算法分析.
http://blog.csdn.net/v_july_v

http://blog.csdn.net/v_july_v/article/details/7041827

2014年8月22日 08:50

flyfoxs
63
0 0 5

1条评论

0 0

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		String a = "jha123ghfs343uhg321asd131";
		String str1 = null, str2 = null, tmpstr1 = null, tmpstr2 = null, maxstr1 = null, maxstr2 = null;

		for (int i = 0; i < a.length() - 2; i++) {

			for (int j = 2 + i; j < a.length() - 1; j++) {
				if (j > i) {
					str1 = a.substring(i, j);
					if (str1 != null && !str1.equals("") && str1.length() > 1) {
						str2 = (new StringBuilder(str1)).reverse().toString();
						if (a.indexOf(str2) == -1) {
							if (tmpstr1 != null && (maxstr1 == null || tmpstr1.length() > maxstr1.length())) {
								maxstr1 = tmpstr1;
								maxstr2 = tmpstr2;
							}
							break;
						} else {
							tmpstr1 = str1;
							tmpstr2 = str2;
						}
					}
				}
			}
		}

		System.out.println("字符串中最长的颠倒字符串:"+maxstr1 + "," + maxstr2);
	}

}

运行输出，字符串中最长的颠倒字符串:a123gh,hg321a

2014年8月23日 22:26

sundoctor
30
0 0 1

1条评论

0 0

第二道题code
package com.test1;

/**
* 最大长颠倒字符串它的长度应该小于等于整个字符串（长度为L）的的一半
* 从假设最大颠倒长度为整个的1/2L 然后查这个长度的颠倒字符串是否存在存在就返回，不存在，则继续往下找1/2L-1,以此类推1/2L-1....一直到0。如果为0说明没有
*
*/
public class ResStrLong {
public static void main(String[] args) {
String string="a123ghfuhg321asd131";
    String revString=getLongString(string);
}
    public static String getLongString(String string)
    { int maxStr=string.length()/2;
      int len=string.length();
      String revString=null;
      boolean flag=false;
      for(int i=maxStr;i>=0;i--){
    for (int j = 0; j <len; j++) {
        if((j+i+1)>(len-1))continue;
String subString=string.substring(j,j+i+1);
         revString=new StringBuffer(subString).reverse().toString();
int flag1=string.indexOf(revString);
if(flag1!=-1){flag=true;System.out.println(subString+":"+revString+";"+i);break;}
}
        if(flag)break;
      }
      return revString;
    }
}

2014年8月21日 22:01

探索者_技术
28
0 0 6

1条评论

0 0

第一个问题，用hash，把字符串转为数字去比对，数据的存储和查找都会比较快。
第二个问题，回文问题，上网找吧！

2014年8月21日 21:34

freezingsky
159
1 1 16

添加评论

0 0

第一个问题应该是考，怎么存这一千万条数据，使判断是不是黑名单用户的耗时最少。
这也是分词器字典需要使用的数据结构。之前看IK分词的词典是使用树结构存储的；父节点使用hashmap存储子节点对象；每个节点的值是一个char。
http://blog.csdn.net/guwenwu285/article/details/9617057

第二个http://blog.csdn.net/hopeztm/article/details/7932245的思路二的方法：

package snippet;

public class Solution {
	private static int[] next;

	private static void GetNext(String s)// KMP求next数组
	{
		int i, j;

		i = 0;
		j = -1;

		next[0] = -1;

		while (i < s.length()) {
			if (j == -1 || s.charAt(i) == s.charAt(j)) {
				i++;
				j++;
				next[i] = j;
			} else {
				j = next[j];
			}
		}
	}

	private static int compare(String pattern, String s) // 用KMP算法做求出最长的前缀匹配
	{
		int i, j;

		i = 0;
		j = 0;

		int maxLen = 0;
		while (i < s.length()) {
			if (j == -1 || pattern.charAt(j) == s.charAt(i)) {
				i++;
				j++;
			} else {
				j = next[j];
			}
			if (j > maxLen) {
				maxLen = j;
			}
			if (j == pattern.length()) {
				return maxLen;
			}
		}
		return maxLen;
	}

	public static String longestPalindrome(String s) //
	{
		// Start typing your Java solution below
		// DO NOT write main() function
		String reverString = new StringBuilder(s).reverse().toString(); // 求得到
																		// 输入string
																		// 的reverse
		next = new int[s.length() + 1];

		String maxPal = "";
		int maxLen = 0;
		int len;
		for (int i = 0; i < s.length(); i++) // 枚举所有后缀
		{
			String suffix = reverString.substring(i);
			if (suffix.length() < maxLen) {
				break;
			}
			GetNext(suffix);
			len = compare(suffix, s);
			if (len > maxLen) {
				maxPal = suffix.substring(0, len);
				maxLen = len;
			}

		}
		return maxPal;

	}

	public static void main(String[] args) {
		System.out.println(longestPalindrome("a123ghfuhg321asd131"));
		System.out.println(longestPalindrome("a123ghuhg321asd131"));
	}
}

2014年8月21日 15:15