Amazon OA2 12/18 due

原帖地址:一亩三分地

昨天刚做的OA2

第一部分:work simulation
一共21道,requirement 和 deadline 之间的选择,开放性题目, 随意选。
error log 第一题:proxy在德国, 第二题: proxy连接问题
error rate chart: service 1 有问题, 但还要看其他report确认
shopping cart: 第一题: O(n^2) 第二题:把购物车放到user类下面 第三题: 1 3 5 fail, 2 4 pass

第二部分:coding
第一题:bst 最短路径
public static int minSum(TreeNode root){ if(root == null){ return 0; } if(root.left == null root.right == null){ return root.val; } if(root.left != null root.right == null){ return minSum(root.left) + root.val; } if(root.left == null root.right != null){ return minSum(root.right) + root.val; } return Math.min(minSum(root.left), minSum(root.right)) + root.val; }
节点的每种情况都要写出来, 稳健

第二题: round robin
public static float waitingTimeRobin(int[] arrival, int[] run, int q) { if (arrival == null || run == null || arrival.length != run.length) { return 0; } int waitTime = 0; int curTime = 0; int index = 0; int len = run.length; LinkedList queue = new LinkedList(); while (!queue.isEmpty() || index < len) { if (!queue.isEmpty()) { Proccess curProccess = queue.poll(); waitTime += curTime - curProccess.arrTime; curTime += Math.min(q, curProccess.runTime); while (index < len arrival[index] <= curTime) { queue.offer(new Proccess(arrival[index], run[index])); index++; } if (curProccess.runTime > q) {queue.offer(new Proccess(curTime, curProccess.runTime – q)); } } else { queue.offer(new Proccess(arrival[index], run[index])); curTime = arrival[index++]; } } return (float) waitTime / len; }
private static class Proccess { int arrTime; int runTime;
public Proccess(int arrTime, int runTime) { this.arrTime = arrTime; this.runTime = runTime; } }注意arrival[index] <= curTime 不是< ,否则test case过不了