面试题

ruijin5566

浏览: 4542 次
性别:
来自: 北京

最近访客更多访客>>

追求卓绝

woodding2008

jadechenfei

wenming6688

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

笔试面试

高德多线程题

1.主线程里创建N个子线程，等待N个子线程全部执行完后，打印每个子线程执行的时间。

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * 主线程里创建N个子线程，等待N个子线程全部执行完后，打印每个子线程执行的时间。
 * 一种可行的方法
 */
public class MainThread {
	
	public static void main(String[] args) throws InterruptedException {
		int threadNum = 5;
		CountDownLatch latch = new CountDownLatch(threadNum);
		Map<String, Long> map = new ConcurrentHashMap<String, Long>(threadNum);
		ExecutorService pool = Executors.newFixedThreadPool(threadNum);
		for (int i=0; i < threadNum; i++) {
			pool.submit(new SubThread(latch, map));
		}
		latch.await(); //计数减到0时一直等待
		
		for (Map.Entry<String, Long> entry : map.entrySet()) {
			System.out.println(entry.getKey() + "执行耗时：" + entry.getValue() + "毫秒");
		}
		
		pool.shutdown(); // Disable new tasks from being submitted
		try {
		     // Wait a while for existing tasks to terminate
		     if (!pool.awaitTermination(1, TimeUnit.SECONDS)) {
		    	 pool.shutdownNow(); // Cancel currently executing tasks
		    	 // Wait a while for tasks to respond to being cancelled
		    	 if (!pool.awaitTermination(1, TimeUnit.SECONDS)) {
		    		 System.err.println("Pool did not terminate");
		    	 }
		     }
		} catch (InterruptedException ie) {
			// (Re-)Cancel if current thread also interrupted
		    pool.shutdownNow();
		    // Preserve interrupt status
		    Thread.currentThread().interrupt();
		}
	}
	
}

class SubThread implements Runnable {
	private CountDownLatch latch;
	private Map<String, Long> map;
	
	public SubThread(CountDownLatch latch, Map<String, Long> map) {
		this.latch = latch;
		this.map = map;
	}
	
	@Override
	public void run() {
		long start = System.currentTimeMillis();
		System.out.println(Thread.currentThread() + "开始执行...");
		try {
			Thread.sleep(1000); //模拟执行操作
			latch.countDown();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
		long end = System.currentTimeMillis();
		System.out.println(Thread.currentThread() + "执行完毕");
		map.put(Thread.currentThread().toString(), end-start);
	}
	
}

2.一个大数据题，一个500G的文件里存的是url，有些是重复的，要求打印出重复的url。

去哪儿

1.假设字母"a-z"的序列中，后面的字母大于它前面字母任意个数的乘积，如：b > N * a，并且大于所有它前面字符的乘积之和，比如：d > 2a + 3b + 5c,则“qunaer”的最大子序列是“ur”，编程求最大子序列。意思就是说依次找出最大的那个字母，后面的字母没有比它大的，然后找出第二大的字母，依次类推，直到结束。

要求完成函数 char[] maxSub(char[] src, char[] sub)。

public class Test {
	
	public static void main(String[] args) {
		char[] src = new char[]{'q', 'u', 'n', 'a', 'e', 'r'};
		char[] sub = new char[src.length];
		sub = maxSub(src, sub);
		System.out.println(sub);
	}
	
	public static char[] maxSub(char[] src, char[] sub) {
		int k = 0;
		for (int i=0; i<src.length; i++) {
			for (int j=i+1; j<src.length; j++) {
				if (src[i] < src[j]) { 
					i = j; //每次找出最大的那个字母，用i记录最大字母的下标
				}
			}
			sub[k++] = src[i];
		}
		return sub;
	}
}

做完后面试官问你它的时间复杂度，是O(n的平方)，然后问你有没有用O(n)的时间复杂度可以解决的方法，他说用动态规划很好解决，不过我不知道动态规划，这就是我最后的结果了，感觉算法真是可以看出一个人的水平。关于动态规划的文章可以参考：通过金矿模型介绍动态规划 http://www.cnblogs.com/sdjl/articles/1274312.html。

2.有字符串a和字符串b，编程求出字符串a是否包含字符串b中的所有字符，如果字符串b中有5个字符'z'，那么字符串a的’z'个数必须大于等于5个。

public class Test {
	
	public static void main(String[] args) {
		String a = "aabeabecacad";
		String b = "aaaaabccde";
		boolean contain = isContain(a, b);
		System.out.println("字符串a包含字符串b:" + contain);
	}
	
	public static boolean isContain(String a, String b) {
		Map<String, Integer> aMap = stringToMap(a);
		Map<String, Integer> bMap = stringToMap(b);
		
		for (Map.Entry<String, Integer> entry : bMap.entrySet()) {
			String key = entry.getKey();
			Integer count = entry.getValue();
			if (!aMap.containsKey(key) || aMap.get(key) < count) {
				return false;
			}
		}
		return true;
	}
	
	public static Map<String, Integer> stringToMap(String str) {
		Map<String, Integer> map = new HashMap<String, Integer>(str.length());
		for (char c : str.toCharArray()) {
			String key = String.valueOf(c);
			if (map.containsKey(key)) {
				map.put(key, map.get(key) + 1);
			} else {
				map.put(key, 1);
			}
		}
		return map;
	}
}

3.一个1T的文件存的是long型的字符串，给文件中的long型字符串排序。

正确的解题思路就是分而治之，比如说读1T的文件，每次读1G到内存里，在内存里对这1G数据排序，排完后写到1024个不同的文件里，这样读1次，写1024次，数据分散到1024个不同的小文件，每个文件1G，而且是有序的。然后同时读1024个文件做多路归并排序，排完序之后再写回一个大文件里。（思路可以参考2个有序数组的归并排序，比如每个文件先读取一行，找出1024个数中最小的，写入文件，再读取最小的那个文件的下一行，继续排序写入）这个题的瓶颈在于IO，应该尽量减少IO次数，而在内存排序是很快的。

4.还问了多线程之间的同步，具体的BlockingQueue是怎么加锁同步的，比如说LinkedBlockingQueue

5.Memcached数据失效或宕机了之后有很多并发访问数据库怎么办

应对Memcached缓存失效，导致高并发查询DB的四种思路：http://blog.csdn.net/hengyunabc/article/details/20735701

搜狗的部分面试题

1.在数据库中有表MarkList，表中有下列数据，用一条sql语句查询出“每门”课程都大于80分的学生姓名。

Name Course Mark

张三数学 75

张三语文 81

李四数学 90

李四语文 76

王五数学 81

王五语文 100