一个大型互联网公司高级技术的远程面试题目和解答过程以及源代码

package com.fa.taskdispatch;

import java.util.ArrayList;
import java.util.HashMap;

public class App {
	public static void main(String[] args) {
		
		if (args.length < 2) {
			System.out.println("Usage : 需要两个运行参数，第一个是任务列表的文件路径，第二个是计算资源的文件路径");
			System.exit(1);
		} 
		
		AnalyticalResource ar = new AnalyticalResource(args[0], args[1]);
		HashMap<String, Task> taskMap = new HashMap<String, Task>();
		if (!ar.resolveTaskListFile(taskMap)) {
			System.out.println("解析任务列表的YAML文件失败，系统退出.");
			System.exit(1);
		}

		ArrayList<ComputeResource> computeResourceList = new ArrayList<ComputeResource>();
		if (!ar.resolveComputeResourceFile(computeResourceList)) {
			System.out.println("解析计算资源文件失败，系统退出.");
			System.exit(1);
		}
		
		TaskDispatch td = new TaskDispatch(taskMap, computeResourceList);
		ArrayList<String> dispatchResult = new ArrayList<String>();
		if (td.dispatch(dispatchResult)) {
			System.out.println("任务调度成功,调度结果如下: ");
			for (String name : dispatchResult) {
				System.out.println(name);
			}
		} else {
			System.out.println("任务调度失败.");
		}
	}
}

package com.fa.taskdispatch;

public class ComputeResource {
	private String name;
	private int cores;
	
	public ComputeResource(String name, int cores) {
		this.name = name;
		this.cores = cores;
	}
	
	public void subCores(int number) {
		cores = cores - number;
	}
	
	public void addCores(int number) {
		cores = cores + number;
	}
	
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getCores() {
		return cores;
	}
	public void setCores(int cores) {
		this.cores = cores;
	}
	
}

package com.fa.taskdispatch;

import java.util.ArrayList;

public class Task {

	private String name;
	
	private int coresRequired;
	
	private int executionTime;
	
	private ArrayList<String> parentTasks;
	
	public Task(String name, int coresRequired, int executionTime) {
		this(name, coresRequired, executionTime, new ArrayList<String>());
	}
	
	public Task(String name, int coresRequired, int executionTime, ArrayList<String> parentTasks) {
		this.name = name;
		this.coresRequired = coresRequired;
		this.executionTime = executionTime;
		this.parentTasks = parentTasks;
	}

	public boolean isDependMyself() {
		boolean result = false;
		for (String p : parentTasks) {
			if (p.equals(name)) {
				result = true;
			}
		}
		
		return result;
	}
	
	public boolean parentTasksIsEmpty() {
		return parentTasks == null || parentTasks.isEmpty();
	}
	
	//删除依赖任务中的一个
	public void deleteOneParentTasks(String name) {
		parentTasks.remove(name);
	}
	
	public void subExecutionTime(int number) {
		executionTime = executionTime - number;
	}
	
	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public int getCoresRequired() {
		return coresRequired;
	}

	public void setCoresRequired(int coresRequired) {
		this.coresRequired = coresRequired;
	}

	public int getExecutionTime() {
		return executionTime;
	}

	public void setExecutionTime(int executionTime) {
		this.executionTime = executionTime;
	}

	public ArrayList<String> getParentTasks() {
		return parentTasks;
	}

	public void setParentTasks(ArrayList<String> parentTasks) {
		this.parentTasks = parentTasks;
	}
	
}

package com.fa.taskdispatch;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Properties;

import org.yaml.snakeyaml.Yaml;

public class AnalyticalResource {

	private String taskListFile = "";
	private String computeResource = "";

	public AnalyticalResource(String taskListFile, String computeResource) {
		this.taskListFile = taskListFile;
		this.computeResource = computeResource;
	}

	public boolean resolveTaskListFile(HashMap<String, Task> tasks) {
		boolean result = true;
		
		if (tasks == null) {
			tasks = new HashMap<String, Task>();
		}
		
		Yaml y = new Yaml();
		File f = new File(taskListFile);

		try {
			HashMap tasksMap = (HashMap) y.load(new FileInputStream(f));
			for (Object taskName : tasksMap.keySet()) {
				HashMap taskMap = (HashMap)tasksMap.get(taskName);
				
				int coresRequired = (Integer)taskMap.get("cores_required");
				int executionTime = (Integer)taskMap.get("execution_time");

				String parentTasks = (String)taskMap.get("parent_tasks");
				String name = (String)taskName;
				if (parentTasks != null && !parentTasks.isEmpty()) {
					String parents[] = parentTasks.split(",");
					ArrayList<String> parentList = new ArrayList<String>();
					for (String parent : parents) {
						parentList.add(parent.trim());
					}
					Task t = new Task(name.trim(), coresRequired, executionTime, parentList);
					tasks.put(name.trim(), t);
				} else {
					Task t = new Task(name.trim(), coresRequired, executionTime);
					tasks.put(name.trim(), t);
				}
			}

		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			result = false;
			e.printStackTrace();
		}

		return result;
	}

	public boolean resolveComputeResourceFile(ArrayList<ComputeResource> computeResourceList){
		boolean result = true;
		
		if (computeResourceList == null) {
			computeResourceList = new ArrayList<ComputeResource>();
		}
		
		try {
			Properties pt = new Properties();
			pt.load(new FileInputStream(computeResource));
			
			if (pt.isEmpty()) {
				result = false;
				System.out.println("没有计算资源，没有办法进行调度，也算失败，需要退出.");
			}
			
			for (Map.Entry<Object, Object> entry : pt.entrySet()) {
				String name = (String)entry.getKey();
				int cores = Integer.parseInt(entry.getValue().toString().trim());
				ComputeResource cr = new ComputeResource(name.trim(), cores);
				computeResourceList.add(cr);
			}
			
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			result = false;
			e.printStackTrace();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			result = false;
			e.printStackTrace();
		}

		return result;
	}
}

package com.fa.taskdispatch;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;

public class TaskDispatch {

	private HashMap<String, Task> taskMap;
	
	private ArrayList<ComputeResource> computeResourceList;
	
	public TaskDispatch(HashMap<String, Task> taskMap, ArrayList<ComputeResource> computeResourceList) {
		this.taskMap = taskMap;
		this.computeResourceList = computeResourceList;
	}
	
	//检查从某一个任务开始是否存在循环依赖
	public boolean checkOneTaskCycleTaskDepend(Task t) {
		//检查循环依赖就是循环的检查parent_tasks是否会到达任务本身
		//这个是需要改变的，所有单独copy一份出来
		ArrayList<String> parentList = new ArrayList<String>(t.getParentTasks());
		String checkTaskName = t.getName();
		
		while (parentList != null && !parentList.isEmpty()) {
			ArrayList<String> newParentList = new ArrayList<String>();
			for (String parent : parentList) {
				 if (parent.equals(checkTaskName)) {
					 System.out.println("任务["+ checkTaskName + "]存在了循环依赖，不能完成调度.");
					 return true;
				 }
				 
				 Task dependTask = taskMap.get(parent);
				 if (dependTask.isDependMyself()) {
					 System.out.println("任务["+ dependTask.getName() + "]存在自己依赖自己的循环依赖，不能完成调度.");
					 return true;
				 }
				 
				 if (dependTask!= null && !dependTask.parentTasksIsEmpty()) {
					 newParentList.addAll(dependTask.getParentTasks());
				 }
			}
			parentList = newParentList;
		}
		
		return false;
	}
	
	//检查任务是否存在循环依赖，如果存在也是不能调度
	public boolean checkCycleTaskDepend() {
		boolean result = false;
		
		for (String taskName : taskMap.keySet()) {
			Task t = taskMap.get(taskName);
			if (t.parentTasksIsEmpty()) {
				continue;
			}

			if (checkOneTaskCycleTaskDepend(t)) {
				result = true;
			}
			
			if (result) {
				break;
			}
		}
		
		return result;
	}

	public boolean dispatch(ArrayList<String> dispatchResults) {
		//1.验证可调度，如果有一个任务需要的cores_required超过了所有计算机的资源就不能调度
		//(1)找出所有任务中需要最大cores_required
		boolean result = true;
		int maxCoresRequired = 0;
		for (String taskName : taskMap.keySet()) {
			Task t = taskMap.get(taskName);
			if (t.getCoresRequired() > maxCoresRequired) {
				maxCoresRequired = t.getCoresRequired();
			}
		}
		
		//(2)找出计算资源的最大值
		int maxComputeResource = 0;
		for (ComputeResource cr : computeResourceList) {
			if (cr.getCores() > maxComputeResource) {
				maxComputeResource = cr.getCores();
			}
		}
		
		//(3)比较
		if (maxCoresRequired > maxComputeResource) {
			System.out.println("单个任务需要的计算资源大于了任何一台计算机能够提供的资源，所以不能完成这个任务");
			return false;
		}
		
		//2.验证是否有循环依赖
		if (checkCycleTaskDepend()) {
			System.out.println("任务列表里面存在这个循环依赖，不能完成任务调度");
			return false;
		}
		
		//3.调度任务：首先需要做任务的编排（因为任务之间有依赖）
		//（1）首先找出本次可以调度的所有任务（对于第一次当然就是没有任何依赖的任务）；
		//（2）然后有一个以上的任务完成以后在查找依赖这些以完成任务的任务是否可以进行调度了；
		//（3）每次调度都需要有资源的情况下进行；
		//（4）最终形成一个可调用的任务和可使用的计算资源进行匹配；
		
		if (dispatchResults == null) {
			dispatchResults = new ArrayList<String>();
		}
		ArrayList<Task> readyTask = new ArrayList<Task>();
		HashMap<String, Task> runningTask = new HashMap<String, Task>();
		while (!taskMap.isEmpty()) {//直到所有任务都分配计算资源以后结束调度
			for (String taskName : taskMap.keySet()) {
				Task t = taskMap.get(taskName);
				if (t.parentTasksIsEmpty() && !readyTask.contains(t)) {
					readyTask.add(t);
					
				}
			}

			//根据可调度的任务和可以使用的资源进行一次调度，调度之前先对任务和资源进行排序
			
			//1.把可以调度的任务按照时间从短到长排序
			Comparator<Task> taskComparator = new Comparator<Task>(){  
				   public int compare(Task t1, Task t2) {  
					 return  t1.getExecutionTime() -  t2.getExecutionTime();
				   }
			};
			Collections.sort(readyTask, taskComparator);
			//2.把可以利用的计算资源排序
			Comparator<ComputeResource> computeComparator = new Comparator<ComputeResource>(){  
				   public int compare(ComputeResource c1, ComputeResource c2) {  
					 return  c1.getCores() -  c2.getCores();
				   }
			};
			
			Collections.sort(computeResourceList, computeComparator);
			
			oneDispatchTask(dispatchResults, runningTask, readyTask, computeResourceList);
			//调度完成一次，需要把时间最短（可能有多个）的任务结束掉，从可调度的任务里面删除掉，并且重新计算可调度的任务，并且恢复资源
			int minTime = readyTask.get(0).getExecutionTime();
			ArrayList<Task> deleteTaskName = new ArrayList<Task>();
			for (Task t : readyTask) {
				if (minTime >=  t.getExecutionTime()) {//删除掉已经完成的任务，就是时间最小的
					System.out.println("删除任务 ：" + t.getName());
					deleteTaskName.add(t);//记住删除了那些任务，后面用于更新readyTask
					runningTask.remove(t.getName());
					taskMap.remove(t.getName());
					//恢复资源
					for (String name : dispatchResults) {
						if (name.contains(t.getName())) {
							String arr[] = name.split(":");
							String computeName = arr[1];
							for (ComputeResource cr : computeResourceList) {
								if (cr.getName().equals(computeName)) {
									System.out.println(computeName + "恢复资源 ： " + t.getCoresRequired());
									cr.addCores(t.getCoresRequired());
								}
							}
						}
					}
					//继续删除其他任务依赖这个任务的依赖任务
					for (String taskName : taskMap.keySet()) {
						Task task = taskMap.get(taskName);
						if (task.getParentTasks().contains(t.getName())) {
							task.deleteOneParentTasks(t.getName());
							System.out.println("删除任务[" + task.getName() + "]的依赖任务 : [" + t.getName()  + "]" );
						}
					}
				} 
			}
			
			 //其他已经在调度的任务需要减去这个时间
			for (String taskName : runningTask.keySet()) {
				Task t = runningTask.get(taskName);
				t.subExecutionTime(minTime);
			}
			
			//删除可调度任务里面的已经完成的任务
			for (Task t : deleteTaskName) {
				readyTask.remove(t);
			}
		}
		
		return result;
	}
	
	//调度算法：每次调度的时候选择按照从时间从短到长的排序，优先调度时间短的，并且找一个资源能够满足调度任务的最小的计算资源分配
	public void oneDispatchTask(ArrayList<String> dispatchResult, HashMap<String, Task> runningTask,
			ArrayList<Task> readyTask, ArrayList<ComputeResource> availableResources) {
		for (Task t : readyTask) {
			//如果任务已经在运行就不需要在继续分配资源调度了
			if (runningTask.containsKey(t.getName())) {
				continue;
			}
			
			for (ComputeResource cr : availableResources) {
				//如果满足资源需求，就分配这个任务到这一个计算资源了
				if (t.getCoresRequired() <= cr.getCores()) {
					dispatchResult.add(t.getName() +  ":" + cr.getName());
					runningTask.put(t.getName(), t);
					System.out.println("开始调度任务 : [" + t.getName() + "]到计算资源" + cr.getName()); 
					//减去这个计算资源已经使用的cores
					cr.subCores(t.getCoresRequired());
					break;
				}
			}
		}
	}
	
}