admin 管理员组文章数量: 1087652
小米2014年校园招聘笔试题目（排队问题）
2014年9月25日，下午两点，去参加了小米的笔试，在这里分享一下最后一道编程题目。
这道题目的意思大概是：小米有几千位员工，现在要将所有的员工排成一队，但每个人可能会提出特定的要求：要站在某些人的后面，要站在某些人的前面。当然也可以没有要求。现在给出所有员工的要求，问是否存在一种排队方式，能满足所有员工提出的排队要求。若存在，则返回一种排队方式；若不存在，则返回null。
题目给出了两个类：
类Rule的对象是一条规则，targetName是此条规则对应的那个人，isFront代表规则要求站在他的前面还是后面。
class Rule
{public String targetName; // 规则中的那个人public boolean isFront; // 要求排在这个人前面为true;要求排在这个人后面为false
}类Rules刻画了一个人提出的一些规则，name是提出规则的那个人的名字，ArrayList中是这个人提出的规则。
class Rules
{public String name; // 提出规则的那个人ArrayList<Rule> theRules; // 该人提出的规则
}
我将这个问题转化为有向图是否存在有向回路的问题。
首先，构造一个有向图，将每个员工看作图中的一个结点，若员工A要求站在员工B的前面，则有一条有向边由A指向B；若员工A要求站在员工C的后面，则有一条边从C指向A。
然后，对图进行深度优先周游，判断是否存在有向回路。
如果存在，则不可能有满足所有规则的排队方式；
如果不存在有向回路，则有满足所有规则的排队方式，这时只需从“没有要求站在他前面”的那些结点遍历该图，按结点完成遍历的顺序加入到一个栈中，待完成整个图的遍历之后，从栈中取出结点的顺序就是一种可能的排队方式。
我写的代码如下：
package xiaomi;//2014.9.25小米笔试，排队问题
//小米公司共有N名员工，现在要对这N名员工排序，每个员工可能有一些排序要求，如必须站在某些人后面，或必须站在某些人前面
//给出所有人的要求，问是否有一种排序，能满足所有员工的要求。若有，则返回这种排序；若没有则返回null。import java.util.ArrayList;
import java.util.HashMap;//排队的规则
class Rule
{public String targetName; // 规则中的那个人public boolean isFront; // 要求排在这个人前面为true;要求排在这个人后面为false
}class Rules
{public String name; // 提出规则的那个人ArrayList<Rule> theRules; // 该人提出的规则
}public class XiaoMi
{// 内部类，定义结点class MemNode{String memName;boolean isFrontNode = true; // 记录该人是否为最前面的人，即是否要求站在某人后面，或被要求站在某人后面ArrayList<String> afterMemName; // 记录那些要求站在memName后面的人String color = "white"; // 记录结点在图遍历时候的状态// int nodeIndex = 0; //记录node在排队中的位置，初始为0public MemNode(String memName, ArrayList<String> afterMemName){this.memName = memName;this.afterMemName = afterMemName;}}// memNodes存储结点的列表ArrayList<MemNode> memNodes = new ArrayList<>();// nameMap是结点的名字到其在memNodes下标的映射HashMap<String, Integer> nameMap = new HashMap<>();// doneNode是按照结点遍历顺序存储结点的列表ArrayList<MemNode> doneNodes = new ArrayList<>();// isQueue代表是否有满足所有规则的结果，默认是存在的，如果在图的遍历中发现有向回路，则该成falseboolean isQueue = true;// 建图void buildGraph(ArrayList<String> allMember, ArrayList<Rules> allRules){for (int i = 0; i < allMember.size(); i++){MemNode memNode = new MemNode(allMember.get(i), new ArrayList<String>());memNodes.add(memNode);nameMap.put(allMember.get(i), i);}for (int j = 0; j < allRules.size(); j++){for (int k = 0; k < allRules.get(j).theRules.size(); k++){if (allRules.get(j).theRules.get(k).isFront == true){// 说明该人要站在某人的前面memNodes.get(nameMap.get(allRules.get(j).name)).afterMemName.add(allRules.get(j).theRules.get(k).targetName);memNodes.get(nameMap.get(allRules.get(j).theRules.get(k).targetName)).isFrontNode = false;} else if (allRules.get(j).theRules.get(k).isFront == false){// 说明该人要站在某人后面memNodes.get(nameMap.get(allRules.get(j).name)).isFrontNode = false;memNodes.get(nameMap.get(allRules.get(j).theRules.get(k).targetName)).afterMemName.add(allRules.get(j).name);}}}}// 图的深度优先遍历void dfs(ArrayList<MemNode> nodes, MemNode cur){// nodes是所有的结点数组，cur是当前结点cur.color = "gray";for (int i = 0; i < cur.afterMemName.size(); i++){if (nodes.get(nameMap.get(cur.afterMemName.get(i))).color.equals("gray")){isQueue = false;} else if (nodes.get(nameMap.get(cur.afterMemName.get(i))).color.equals("white")){dfs(nodes, nodes.get(nameMap.get(cur.afterMemName.get(i))));}}cur.color = "black";doneNodes.add(cur);}String findQueue(ArrayList<String> allMember, ArrayList<Rules> allRules){buildGraph(allMember, allRules);for (int i = 0; i < allMember.size(); i++){if (memNodes.get(i).color == "white"&& memNodes.get(i).isFrontNode == true){dfs(memNodes, memNodes.get(i));}}if (isQueue == true){String res = " ";for (int i = doneNodes.size() - 1; i >= 0; i--){res = res + doneNodes.get(i).memName + " ";}return res;} else{return null;}}public static void main(String[] args){ArrayList<String> allmember = new ArrayList<>();allmember.add("Node-1");allmember.add("Node-2");allmember.add("Node-3");allmember.add("Node-4");Rule rule11 = new Rule();rule11.targetName = "Node-1";rule11.isFront = true;Rule rule12 = new Rule();rule12.targetName = "Node-3";rule12.isFront = true;Rule rule13 = new Rule();rule13.targetName = "Node-4";rule13.isFront = true;Rule rule21 = new Rule();rule21.targetName = "Node-1";rule21.isFront = true;Rule rule22 = new Rule();rule22.targetName = "Node-4";rule22.isFront = false;Rules rules1 = new Rules();ArrayList<Rule> therules1 = new ArrayList<>();rules1.theRules = therules1;rules1.name = "Node-2";rules1.theRules.add(rule11);rules1.theRules.add(rule12);rules1.theRules.add(rule13);Rules rules2 = new Rules();ArrayList<Rule> therules2 = new ArrayList<>();rules2.theRules = therules2;rules2.name = "Node-3";rules2.theRules.add(rule21);rules2.theRules.add(rule22);ArrayList<Rules> allrules = new ArrayList<>();allrules.add(rules1);allrules.add(rules2);XiaoMi xiaoMi = new XiaoMi();System.out.println(xiaoMi.findQueue(allmember, allrules));}
}
本文标签： 小米2014年校园招聘笔试题目（排队问题）
版权声明：本文标题：小米2014年校园招聘笔试题目（排队问题） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700324400a397196.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论