昨天的JAVA面试题，感觉挺难大家帮忙看看！

昨天的JAVA面试题，感觉挺难大家帮忙看看！新手第一次发帖！
2.1  下图是电话机键盘

从图中，我们可以发现26个字母分布在2-9这8个数字键上。某人的电话号码是65967427，观察单词“olympics”，可以发现：字母o位于数字键6上，字母l位于数字键5上，… 字母s 位于数字键7上。此时，我们说olympics是65967427对应的一个字母组合。65967427还可以对应其它很多种字母组合，例如：mjwmpgap也是其中之一。以C语言编写函数 ：int transfer(int number)。该函数的输入为一个电话号码（允许输入为3位到11位的十进制数），在屏幕上输出该数字对应的所有字母组合，并返回组合的总数。如果数字中包含1或者0，由于没有与之对应的字母，则直接返回0。当数字小于3位或者大于11位时，亦没有对应字母组合，返回0。

2.2  求解：有一个文本文件，记录了某个学校所有人的姓名、出生日期（假设没有人重名，该校大约有2万人）。记录格式如下：
。。。。。。
张三    19800120
李四    19810321
王五    19800122
赵六    19830321
。。。。。。
    现在需要在某天举办一场生日晚会，邀请生日在当天的人员参加。如果期望这场生日晚会参加的人员尽可能多，那么应该选择在哪一天？在解答时，需要注意代码的效率、质量。当不能给出完整代码时，可以描述解题思路。


2.3求解：在一份文本文件中，查找其中所有的anagram。例如，如果这份文件中包含了stop、tops、pots这样三个单词，这三个词就是一组anagram，这三个单词都是由s、t、o、p这四个字母组成的。这份文件中可能存在多组anagram，大小写视为同样字符。在解答时，需要注意代码的效率、质量。当不能给出完整代码时，可以描述解题思路。

评论

61 楼 bookong 2008-04-25  

GreenForest 写道

253620236 写道

昨天的JAVA面试题，感觉挺难大家帮忙看看！新手第一次发帖！
2.3求解：在一份文本文件中，查找其中所有的anagram。例如，如果这份文件中包含了stop、tops、pots这样三个单词，这三个词就是一组anagram，这三个单词都是由s、t、o、p这四个字母组成的。这份文件中可能存在多组anagram，大小写视为同样字符。在解答时，需要注意代码的效率、质量。当不能给出完整代码时，可以描述解题思路。

按我的理解，字母相同(不分大小写)且各字母个数也相同的单词，就是一组anagram，比如说abcd和bcda也算是一组anagram,而不是单指stop、tops和pots这三个单词。
我这样理解错了么？怎么很多人都认为只有stop、tops和pots这三个单词才算是一组anagram。

我觉得你说的是对的。这道题要的结果应该不是 stop,tops,pots...而应该是类似 stop,list,img...因为它说“查找其中所有的anagram”而不是“某个anagram对应的所有单词”

60 楼 GreenForest 2008-04-25  

253620236 写道

昨天的JAVA面试题，感觉挺难大家帮忙看看！新手第一次发帖！
2.3求解：在一份文本文件中，查找其中所有的anagram。例如，如果这份文件中包含了stop、tops、pots这样三个单词，这三个词就是一组anagram，这三个单词都是由s、t、o、p这四个字母组成的。这份文件中可能存在多组anagram，大小写视为同样字符。在解答时，需要注意代码的效率、质量。当不能给出完整代码时，可以描述解题思路。

按我的理解，字母相同(不分大小写)且各字母个数也相同的单词，就是一组anagram，比如说abcd和bcda也算是一组anagram,而不是单指stop、tops和pots这三个单词。
我这样理解错了么？怎么很多人都认为只有stop、tops和pots这三个单词才算是一组anagram。

59 楼 阳光晒晒 2008-04-25  

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * 2.3求解：在一份文本文件中，查找其中所有的anagram。
 * 例如，如果这份文件中包含了stop、tops、pots这样三个单词，
 * 这三个词就是一组 anagram，
 * 这三个单词都是由s、t、o、p这四个字母组成的。
 * 这份文件中可能存在多组anagram，大小写视为同样字符。
 * 在解答时，需要注意代码的效率、质量。当不能给出完整代码时，
 * 可以描述解题思路。
 * @author maodajun327
 *
 */
public class AnagramWords {
		Map map= new HashMap();
		String[] strArray = new String[]{  
		            "stop","tops","pots"
		         };  
		public static void main(String arg[]){
			AnagramWords D2 = new AnagramWords();
			for(int i = 0 ; i < D2.strArray.length ; i++ ){
				D2.getTheWord(D2.strArray[i]);
			}
			List list  = D2.flashMap();
			System.out.println(list);
			
		}
		public void getTheWord(String str){
			str= str.toLowerCase();
			char[] arr=str.toCharArray();
			Arrays.sort(arr);
			String key =String.valueOf(arr);
			if(arr.length<=2){//字数为2当然不用了。
				return;
			}
			if(map.get(key)==null){
				Set set = new TreeSet();
				set.add(str);
				map.put(key, set);		
			}else{
				Set set = (Set) map.get(key);
				if(!set.contains(str)){//重的不要
					set.add(str);
				}
			}
			
		}
		public List flashMap(){
			List list = new ArrayList();
			Set set= map.entrySet();
			Iterator<Map.Entry> it=set.iterator();
			while(it.hasNext()){
				Map.Entry<String, Set> tmp= it.next();
				if(tmp.getValue().size()>=3){//小于3的不要。
					list.add(tmp.getValue());
				}
			}
			return list;			
		}
	
}

58 楼 yujianqiu 2008-04-25  

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

import org.junit.After;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public class PhoneNumber {

	private Map<Character, char[]> keymap;

	@Before
	public void setUp() throws Exception {
		keymap = new HashMap<Character, char[]>(10);
		keymap.put('0', new char[] { '0' });
		keymap.put('1', new char[] { '0' });
		keymap.put('2', new char[] { 'a', 'b', 'c' });
		keymap.put('3', new char[] { 'd', 'e', 'f' });
		keymap.put('4', new char[] { 'g', 'h', 'i' });
		keymap.put('5', new char[] { 'j', 'k', 'l' });
		keymap.put('6', new char[] { 'm', 'n', 'o' });
		keymap.put('7', new char[] { 'p', 'q', 'r', 's' });
		keymap.put('8', new char[] { 't', 'u', 'v' });
		keymap.put('9', new char[] { 'w', 'x', 'y', 'z' });
	}

	@After
	public void tearDown() throws Exception {
	}

	@Test
	public void testCheckNumber() {
		String number = "137689563";
		try {
			checkNumber(number);
		} catch (IllegalArgumentException e) {
			Assert.fail(e.getMessage());
		}
		number = "133";
		try {
			checkNumber(number);
		} catch (IllegalArgumentException e) {
			Assert.fail("Equals 3");
		}
		number = "13312341234";
		try {
			checkNumber(number);
		} catch (IllegalArgumentException e) {
			Assert.fail("Equals 11");
		}
		number = "13";
		try {
			checkNumber(number);
			Assert.fail("Shorter then 3");
		} catch (IllegalArgumentException e) {
		}
		number = "1376118956312";
		try {
			checkNumber(number);
			Assert.fail("Longer then 11");
		} catch (IllegalArgumentException e) {
		}
		number = "13761189B5";
		try {
			checkNumber(number);
			Assert.fail("Invalid char.");
		} catch (IllegalArgumentException e) {
		}
	}

	@Test
	public void testEnumerate() {
		String number = "65967427";
		Set<String> enums = enumerate(number);
		for (String element : enums) {
			System.out.println(element);
		}
		System.out.println("Total: " + enums.size());
	}

	/**
	 * @param number
	 */
	private void checkNumber(String number) {
		if (!number.matches("[0-9]{3,11}")) {
			throw new IllegalArgumentException("Invalid phone number.");
		}
	}

	private Set<String> enumerate(Set<String> base, char[] chars) {
		Set<String> result = new TreeSet<String>();
		if (base.isEmpty()) {
			for (char element : chars) {
				String s = new String(new char[] { element });
				result.add(s);
			}
		} else {
			for (String baseString : base) {
				for (char element : chars) {
					result.add(baseString + element);
				}
			}
		}
		return result;
	}

	/**
	 * @param number
	 * @return
	 */
	private Set<String> enumerate(String number) {
		checkNumber(number);
		char[] chars = number.toCharArray();
		Set<String> result = new HashSet<String>();
		for (char element : chars) {
			result = enumerate(result, keymap.get(element));
		}
		return result;
	}

}

这个比较有趣，写一个看看我家电话号码值钱不。

57 楼 aniude 2008-04-25  

第一题应该不难吧
第二题可以用list 和 set ，然后把set的东西再遍历一下？
第三题可以用正则的话应该不难吧

56 楼 GreenForest 2008-04-23  

Joo 写道

manbearpig1 写道

第三题，26个字母对应2开始的26个质数，对每个词求乘积，结果一样的认为是等价的
前提：不考虑乘法溢出，复杂度上界O(line_of_file * max_word_len)

这个很不错.但问题是每个字母都要转换一边是否高效?
数字不会很大怎么会溢出的?

呵呵,这么一说倒是想起来了,如果再在题目上加上对于空间或者时间的要求,可能就更难一层了
忘记曾经是哪个公司的题目中作此要求

发生溢出的可能性还是很小的，毕竟很少会有很长的单词。
我觉得问题是乘积的结果会很大，最小的8个质数的乘积为9699690。

55 楼 leon_a 2008-04-23  

metaphy 写道

GreenForest 写道

第2题

1、int birthday[12][31]。
2、将数组中所有元素初始化为0。
3、循环遍历所有人，如果当前人n月m日生日，则birthday[n-1][m-1]++。
4、找出数组中最大的值。

这个应该是最省空间和最快的，这个比定义arr[1231]大小的数组要机智的多；其次应该是用HashMap来做

拿空间换时间，主意不错。

54 楼 leon_a 2008-04-23  

sqhe18 写道

7thbyte 写道

nmvr2600 写道

第一个题和论坛ruby版里那个“容易记的电话号码”有些类似
第二个，就是统计生日最多的哪一天，但是生日里面的年可以直接忽略掉，需要的就只有月日。月和日不要一起统计，先算月。先把生日最多的那个月份找到，再去统去到底是哪一天。呵呵，这样最后需要计算个数的人就少了很多了吧。直接去算每天出现的人数还是有点笨。如果数据量再多的话，可以借用下数理统计的知识。
第三个，使用正则表达式\b(?i)[s|t|o|p]{4}\b，搞定~~

“先把生日最多的那个月份找到”的时候，怎么都得遍历一次吧。。
再统计天的话，又部分遍历一次。。哪里减小了运算量啊。。

把月和日当成一个整体作为key，遍历一次就可以了。。

这个正则表达式可以吗。。似乎"tttt"这种字符串也能匹配上

把月和日当成一个整体作为key的话，需要遍历365个元素。
而将月和日分开的话，只需要遍历12+31个元素。
但是后一种方法需要同时在两个collection里插入，可能有点得不尝失

这么算不对的哦，比如有30个人是3月1～30号出生的
另外有20个人是2月10号出生

53 楼 Joo 2008-04-23  

GreenForest 写道

第3题

设times= 26;

a 为 0*times + 0;
b 为 1*times + 1;
c 为 2*times + 2;
d 为 3*times + 3;
.
.
.
z 为 26*times + 26;

对于一个单词，如stop，它的值为s+t+o+p

根据需要调整times的大小。
当times>26的时候，冲突的情况应该很少了。

这个方法前面有兄弟提到过类似的,不过是把字母对应承相应的2以上的质数

52 楼 GreenForest 2008-04-23  

Joo 写道

lsk 写道

likeblood 写道

GreenForest 写道

第2题

1、int birthday[12][31]。
2、将数组中所有元素初始化为0。
3、循环遍历所有人，如果当前人n月m日生日，则birthday[n-1][m-1]++。
4、找出数组中最大的值。

这才是正解！看看编程珠玑的前言吧
当然最好再加个int month  int day 随时记录最多的日子，这样最后就不用再遍历了

不知道是二维数组快点 .还是Map 快点?

静态数组不需要在申请内存自然会快一些
主要是我不太知道申明一个12*31的二维数组和申明一个365的一维数组在效率上有什么优势，大约是在进行++操作的时候遍历速度上吧？

我想你是想说372大小的一维数组吧。
我认为优势不在于效率上，而在于写代码时的可读性上。
若是372大小的一维数组，则可以birthday[(month-1)*31+day-1]++ 或者birthday[month<<5-month-31 + day -1]++;
若是366大小的一维数组，则会有些麻烦，比如说有一个人于8月5日生日，那他在这个366大小的数组中对应哪一个元素呢？
也许可以定义一个数组int monthdays[12]={0,31,60,91. . . . . }, 然后birthday[monthdays[month-1]+day-1]++，但是写出来的代码不如12*31的二维数组或372的一维数组来得简洁。
若是365大小的一维数组，则存在2月29日问题。

51 楼 GreenForest 2008-04-23  

第3题

设times= 26;

a 为 0*times + 0;
b 为 1*times + 1;
c 为 2*times + 2;
d 为 3*times + 3;
.
.
.
z 为 26*times + 26;

对于一个单词，如stop，它的值为s+t+o+p

根据需要调整times的大小。
当times>26的时候，冲突的情况应该很少了。

50 楼 Joo 2008-04-23  

还是你更好 写道

1.电话的，可以用进制搞定。比如输入2345,那么可能的数值是0001,也就是在2键上取第0个字母，在3键上取0,4键上取第0个字母,5键上取第1字母，这是一个组合。再将数加1,变成0002，0003，（进位）0010，0011....但要注意，这个加1进位可能是3进制，也可能是4进制。
2.生日那题其实是要从生日最小的单位找比较快：取日的个位，找到个位相同个数最多的那个，也有可能多个，不过数量绝对减少，再在这些结果中找日的十位，以此类推，直到年的十位，最多的就是了。
3.算字母的乘的积，如a*b*c与a*c*b与c*a*b等是一样的，当然要转成统一的大小写。

是吗？
会不会a*b=c*d?

49 楼 metaphy 2008-04-23  

GreenForest 写道

第2题

1、int birthday[12][31]。
2、将数组中所有元素初始化为0。
3、循环遍历所有人，如果当前人n月m日生日，则birthday[n-1][m-1]++。
4、找出数组中最大的值。

这个应该是最省空间和最快的，这个比定义arr[1231]大小的数组要机智的多；其次应该是用HashMap来做

48 楼 还是你更好 2008-04-23  

1.电话的，可以用进制搞定。比如输入2345,那么可能的数值是0001,也就是在2键上取第0个字母，在3键上取0,4键上取第0个字母,5键上取第1字母，这是一个组合。再将数加1,变成0002，0003，（进位）0010，0011....但要注意，这个加1进位可能是3进制，也可能是4进制。
2.生日那题其实是要从生日最小的单位找比较快：取日的个位，找到个位相同个数最多的那个，也有可能多个，不过数量绝对减少，再在这些结果中找日的十位，以此类推，直到年的十位，最多的就是了。
3.算字母的乘的积，如a*b*c与a*c*b与c*a*b等是一样的，当然要转成统一的大小写。
ASCII码值上，从95(a)开始，可以保证在个数一样时，a*b*c*d!=i*j*k*l

47 楼 YRHYRH 2008-04-23  

这年头只考数据结构和算法的公司只会招到呆子。永远搞不到有创造性的人才。

46 楼 YRHYRH 2008-04-23  

你确定他们是招JAVA的？

45 楼 bonny 2008-04-23  

1,的解法我没什么想法
2，直接导入数据库，执行sql更快更有效率
3，使用split分词，然后按每个词的字数分组，然后对组内进行匹配

44 楼 lsk 2008-04-23  

etongg 写道

第二题：
考虑选Hashmap还是数组时，要把字符串转化为数字的效率考虑在内。

用个范型.不用转换.

43 楼 etongg 2008-04-23  

第二题：
考虑选Hashmap还是数组时，要把字符串转化为数字的效率考虑在内。

42 楼 OFat 2008-04-23  

第二题：  维护一个365(366)长度的数组

第三题：   A=0(25个)1  二进制