Amazon OA2

• 选组方针
• 总结
• Leadership Principles
• Work Simulation
  • book api
  • amazon recommendation system
  • dealline与requirement
  • Log 问题
  • Testcase
• Window Sum
• Overlap Rectangle
• K Closest Points
• Longest Palindrome
• City Connected
• Company Tree 最大平均子节点
• Order Dependency
• Copy List with Random Pointer
• High Five
• Copy the Random List

11-13 周日 Bobst Library

11-17 周四 Bobst 第二次

选组方针

来amazon有2个原则：

1. 不要去成熟的知名组，oncall累死你，不会有像样的项目做。你要非进去学架构，我无话可说。
2. 要去新的service，用aws的组，越新越好。

我是有点经验，我觉得亚麻最有价值的就是AWS，只要不oncall，给你做新项目设计aws的核心，比如dynamo，kinesis等就一定要去。你说的vendor self service其实很无聊。不会提高你的身价。

总结

对于ineffective的选项直接打一分，然后其他effective的打分都是4到5分。 遵循的原则是客户>ddl>技术

和几个拿了video的朋友交流过，基本都写了注释，写了思路，因为是online test，也没有交流，所以我觉得这点会比较重要。

2016 重点九道题：

一二题： Rectangle Overlap, 有没有等于 K Closest Points, 不能用PQ，用Arrays.sort Window Sum,
Longest Palindrome Substring 要不要用O(n)的解法

第三题： Copy List with Random Pointer, 要不要用O(1)的解法(// skip the last one ) Order Dependency, hashmap 不要用order 作为key，要用OrderName Minimum Spanning Tree, Five Scores, Maximum Subtree 不能用全局变量

Leadership Principles

一个优秀的leaders往往是一个行动派。在商业中，速度是非常重要的。很多决策和行动往往是可纠正、可调节的。因此，并不需要太多的research来支撑。

Leaders应以客户为出发点，努力赢得和维护客户的信任。虽然Leaders应该关注竞争对手，但应该花更多时间在自己的用户身上。

Leaders同时也是公司的主人。他们会考虑长远的利益，而不会牺牲长远利益去追求眼前利益。他们以整个公司的利益为行动的出发点，而不是一个team的利益。他们不会用“that’s not my job” 去搪塞。

Work Simulation

一共21道题，中间穿插video，看log，找bug，推进项目走向

book api

第一问：让两人继续说，tell me more

第二问：图书馆的服务器有没有开放实体书的API

系统出现bug，该怎么办？ 看internal bug记录

amazon recommendation system

issue1: 总失败 因为username太长了

issue2: 显示德语 因为用proxy的name来决定语言

issue3: bug问题在哪儿 看error log

看log的问题 就要找相同错误的规律

dealline与requirement

只要坚持deadline最好不要拖，自己辛苦一点无所谓，多咨询manager，找其他有经验的人合作啥的，随机应变吧。

ShoppingCartClass两道题三短一长选最长

Log 问题

看log的也不难就是找相同出错原因问那几条的相同点就可以。

显示德语是因为proxy 第一问是为什么会出现德语，看report发现出现德语的共同点是locate都在德国，所以答案选的就是locate。

第二问是为什么有的是invalid，看report发现共同点都是username都很长，因此选的username很长。

database的那个field定义长度短了

Testcase

关于shopping的代码

第一问是某个method为什么不行? 答案选的performance issue。这个不太确定（其他几个选项更不合理）。

第二问是how to improve shoppingcart class。 我选的是add user.id to shoppingcart class.

第三问就是5个test case了。地里前辈说过很多了，应该是1，3，5跑不过。 第一个是getdefualtpayment会返回null。 第三个是user并没有初始化email，所以getemail会出错。 第五个是setprice的method 返回的是integer，而testcase set的是double。

Window Sum

求一个滑动窗口大小为k的subarray的和，return 所有的window sum.

public List<Integer> windowSum(int[] array, int k) {
    if(array == null || array.length == 0, k <= 0) {
        return new ArrayList<>();
    }

    List<Integer> result = new ArrayList<>();
    int sum = 0;
    for(int i = 0; i < array.length; i++) {
        if(i < k) {
            sum += array[i];
            if(i == k - 1) {
                result.add(sum);
            }
        } else {
            sum += array[i];
            sum -= array[i - k];
            result.add(sum);
        }
    }

    return result;
}

Overlap Rectangle

题目 给定两个长方形左下角和右上角的坐标，判断是否有重叠，返回true或者false。

This problem can be converted as a overlap internal problem. On the x-axis, there are (A,C) and (E,G); on the y-axis, there are (F,H) and (B,D). If they do not have overlap, the total area is the sum of 2 rectangle areas. If they have overlap, the total area should minus the overlap area.

public class Overlap {
    public static class Node {
        double x;
        double y;
        public Node(double x, double y) {
            this.x = x;
            this.y = y; 
        }
    }

    public static boolean check(Node topLeftA, Node topLeftB, Node bottomRightA, Node bottomRightB) {
        // one above the other one
        if(bottomRightA.y > topLeftB.y || bottomRightB.y > topLeftA.y) {
            return false;
        }
        // one on the left side of the other one
        if(bottomRightA.x < topLeftB.x || bottomRightB.x < topLeftA.x) {
            return false;
        }

        return true;
    }
}

K Closest Points

题目 Find the K closest points to the origin in a 2D plane, given an array containing N points.

原点附近最近的K个点

K closest point那道题是距离相同的object要保持相同的顺序

public static class Point { 
    double x;
    double y; 
    public Point(double a, double b) {
        x = a;
        y = b;
    }
}

public Point[] findKClosestPoint(Point[] array, Point origin, int k) {
    // max heap
    PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>(){
        @Override
        public int compare(Point a, Point b) {
            return (int) (getDistance(b, origin) - getDistance(a, origin));
        }
    });

    for(int i = 0; i < array.length; i++) {
        if(pq.size() >= k &&  (getDistance(pq.peek(), origin) > getDistance(array[i], origin)) ) {
            pq.poll();
            pq.offer(array[i]);
        } else {
            pq.offer(array[i]);
        }
    }

    Point[] result = new Point[k];
    int index = k - 1;
    while(!pq.isEmpty()) {
        result[index--] = pq.poll();
    }
    return result;
}

private double getDistance(Point a, Point b) {
    return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

做法二：

private double getDis(Point p1, Point p2) {
        return Math.sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
    }


public Point[] SolutionII(Point[] array, Point origin, int k) {
    if (array == null || array.length <= k) {
        return array;
    }
    Arrays.sort(array, new Comparator<Point>() {
        @Override
        public int compare(Point p1, Point p2) {
            return Double.compare(getDis(P1, origin), getDis(P2, origin));
        }
    });
    Point[] res = new Point[k];
    for (int i = 0; i < k; i++) {
        res[i] = array[i];
    }
    return res;
}

Longest Palindrome

给一个字符串，问可能组成的最长的palindrome string的长度

Idea:

统计词频，偶数个的字符就都用上，奇数个的字符就n - 1.最后只取一个奇数的字符在中间

public int longestPalindrome(String s) {
    if(s == null || s.length() == 0) {
        return 0;
    }

    HashMap<Character, Integer> map = new HashMap<>();

    for(char c : s.toCharArray()) {
        if(!map.containsKey(c)) {
            map.put(c, 1);
        } else {
            map.put(c, map.get(c) + 1);
        }
    }

    int odd = false;
    int count = 0;

    for(int i : map.values()) {
        if(i % 2 == 0) {
            count += i;
        } else {
            count += i - 1;
            odd = true;
        }
    }

    return odd ? count + 1 : count;
}

City Connected

给十几个城市供电，连接不同城市的花费不同，让花费最小同时连到所有的边。给出一系列connection类，里面是edge两端的城市名和它们之间的一个cost，找出要你挑一些边，把所有城市连接起来并且总花费最小。不能有环，最后所以城市要连成一个连通块。

输入:

{"Acity","Bcity",1} {"Acity","Ccity",2} {"Bcity","Ccity",3}

输出：

("Acity","Bcity",1} ("Acity","Ccity",2}

思路：

无向图的Minimum Spanning Tree的问题，用Kruskal的Union-Find做法，把所有的边先排序，然后按照从小到大逐个把不成环的边加入一个set里面，直到所有的点都可达。

public class Solution {
    public static class Connection {
        String a;
        String b;
        int cost;
        public Connection(String a, String b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }
    }

    public static class UnionFind {
        private HashMap<String, String> map;
        public UnionFind() {
            map = new HashMap<>();
        }

        public String find(String s) {
            int tmp = s;
            while (map.containsKey(s) && map.get(s) != s) {
                tmp = map.get(s);
            }
            return tmp;
        }

        public void union(String a, String b) {
            String fa_a = find(a);
            String fa_b = find(b);
            if(fa_a != fa_b) {
                map.put(fa_a, fa_b);
            }
        }

        public boolean isAllConnected(String s) {
            String dest = find(s);
            for(String city : map.keySet()) {
                if(find(city) != dest) return fasle;
            }
            return true;
        }
    }

    public static List<Connection> getLowestCost(List<Connection> connections) {
        List<Connection> result = new ArrayList<>();
        if(connections == null || connections.size() == 0) {
            return result;
        }

        // Kruskal's Minimum spanning tree algorithm
        // sort the edges by cost in increasing order
        Collections.sort(connections, new Comparator<Connection>() {
            @Override
            public int compare(Connection conn1, Connection conn2) {
                return conn1.cost - conn2.cost;
            }
        });

        // add the edge to union find from lowest cost to most cost
        UnionFind uf = new UnionFind();
        for(Connection edge : connections) {
            String city1 = uf.find(edge.a);
            String city2 = uf.find(edge.b);
            if(city1 != city2) {
                uf.union(city1, city2);
                result.add(edge);
            }
        }

        // check if all cities are connected
        String city = result.get(0).a;
        // MST题目里说如果没有这样的解，就返回空表，其实需要返回null，才能过一个隐藏的case
        if(!uf.isAllConnected(city)) return null;

        // sort output based on name
        Collections.sort(result, new Comparator<Connections>() {
            @Override
            public int compare(Connection c1, Connection c2) {
                if(c1.a.equals(c2.a)) {
                    return c1.b.compareTo(c2.b);
                } else {
                    return c1.a.compareTo(c2.a);
                }
            }
        }); 
        return result;
    }

    public static void main(String[] args) {
        List<Connection> connections = new ArrayList<>(Arrays.asList(
            new Connection("A", "B", 6),
            new Connection("B", "C", 4),
            new Connection("A", "C", 3),
            new Connection("C", "D", 5),
            new Connection("E", "F", 2),
            new Connection("E", "A", 2)  
        ));

        for(Connection conn : getLowestCost(connections)) {
            System.out.printf("%s <-> %s (%d) \n", conn.a, conn.b, conn.cost);
        }
    }
}

Company Tree 最大平均子节点

题目： 就是给一棵多叉树，表示公司内部的上下级关系。每个节点表示一个员工，节点包含的成员是他工作了几个月(int)，以及一个下属数组(ArrayList)。

目标就是找到一棵子树，满足：这棵子树所有节点的工作月数的平均数是所有子树中最大的。 最后返回这棵子树的根节点。

这题补充一点，返回的不能是叶子节点(因为叶子节点没有下属)，一定要是一个有子节点的节点。

Idea:

这题就是一道postorder traverse的题

public class CompanyTree {
    static class Node {
        int val;
        List<Node> children;
        public Node(int val) {
            this.val = val;
            children = new ArrayList<>();
        }
    }

    static Node result;
    static double maxAverage = Double.MIN_VALUE;

    static class Wrapper {
        int count, sum;
        public Wrapper(int sum, int count) {
            this.count = count;
            this.sum = sum;
        }
    }

    public static Node getMaxAverageSubtree(Node root) {
        if(root == null) return null;
        dfs(root);
        return result;
    }

    public static Wrapper dfs(Node root) {
        if(root.children == null || root.children.size() == 0) {
            return new Wrapper(root.val, 1);
        }

        int subtreeSum = root.val;
        int subtreeCount = 1;

        // post-order traverse

        for(Node node : root.children) {
            Wrapper w = dfs(node);
            subtreeSum += w.sum;
            subtreeCount += w.count;
        }

        // 别忘了cast!!
        double subtreeAverage = (double) subtreeSum / subtreeCount;

        if(subtreeAverage > maxAverage) {
            maxAverage = subtreeAverage;
            result = root;
        }

        return new Wrapper(subtreeSum, subtreeCount);
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        Node l1 = new Node(2);
        Node l11 = new Node(3);
        Node l12 = new Node(4);
        Node l13 = new Node(5);
        Node l14 = new Node(6);
        Node l2 = new Node(7);
        Node l22 = new Node(8);
        Node l23 = new Node(9);
        Node l231 = new Node(1);
        Node l232 = new Node(2);
        Node l3 = new Node(3);
        Node l31 = new Node(4);
        Node l32 = new Node(5);

        root.children.add(l1);
        root.children.add(l2);
        root.children.add(l3);

        l1.children.add(l11);
        l1.children.add(l12);
        l1.children.add(l13);
        l1.children.add(l14);

        l2.children.add(l22);
        l2.children.add(l23);

        l23.children.add(l231);
        l23.children.add(l232);

        l3.children.add(l31);
        l3.children.add(l32);
//        Node root = new Node(1);
//        Node l21 = new Node(2);
//        Node l22 = new Node(3);
//        Node l23 = new Node(4);
//        Node l31 = new Node(5);
//        Node l32 = new Node(5);
//        Node l33 = new Node(5);
//        Node l34 = new Node(5);
//        Node l35 = new Node(5);
//        Node l36 = new Node(5);
//
//        l21.children.add(l31);
//        l21.children.add(l32);
//
//        l22.children.add(l33);
//        l22.children.add(l34);
//
//        l23.children.add(l35);
//        l23.children.add(l36);
//
//        root.children.add(l21);
//        root.children.add(l22);
//        root.children.add(l23);
        Node result = getMaxAverageSubtree(root);
        System.out.println(result.val + " " + maxAverage);
    }
}

Order Dependency

输入的是一群OrderDependency的object，输出是Order的List。类似于这样[(A, B), (A, C), (B, C)]，意思每一对里，A的生产依赖于B，B就必须得先造出来，最后让你返回顺序[C, B ,A]。

Order里面就一个String类型的内容，而且这题据说test case一共就4个。

有向图的topological，bfs

public class Solution {

    static class Order{
        String order = "";
        public Order(String string){
            this.order = string;
        }
    }
    static class OrderDependency{
        Order cur;
        Order pre;
        public OrderDependency(Order o1, Order o2){
            cur = o1;
            pre = o2;
        }
    }

    public static List<Order> getOrder(List<OrderDependency> orderDependencies){
        List<Order> result = new ArrayList<>();
        if(orderDependencies == null || orderDependencies.size() == 0) {
            return result;
        }

        HashMap<Order, List<Order>> map = new HashMap<>();
        HashMap<Order, Integer> indegree = new HashMap<>();

        // HashSet<Order> set = new HashSet<>();

        // convert the edge list to adjacent lists and calcualte the indegree
        for(OrderDependency o : orderDependencies) {
            // skip invalid input
            if(o.pre.order.equals(o.cur.order)) continue;

            // set.add(o.cur);
            // set.add(o.pre);
            if(!map.containsKey(o.pre)) {
                map.put(o.pre, new ArrayList<>());
            }
            if(!map.containsKey(o.cur)) {
                map.put(o.cur, new ArrayList<>());
            }

            map.get(o.pre).add(o.cur);

            // keep the start point
            if(!indegree.containsKey(o.pre)) {
                indegree.put(o.pre, 0);
            }
            if(!indegree.containsKey(o.cur)) {
                indegree.put(o.cur, 1);
            } else {
                indegree.put(o.cur, indegree.get(o.cur) + 1);
            }


        }

        // BFS, find the start point
        Queue<Order> q = new LinkedList<>();
        for(Order o : indegree.keySet()) {
            // Add to result list if no incoming edges
            if(indegree.get(o) == 0) {
                q.offer(o);
            }
        }

        while(!q.isEmpty()) {
            Order order = q.poll();
            // add to result list
            result.add(order);

            for(Order child : map.get(order)) {
                // Remove this incoming edge.
                indegree.put(child, indegree.get(child) - 1);
                if(indegree.get(child) == 0) {
                // Add to queue if no incoming edges
                    q.offer(child);
                }
            }
        }
        // Check if there's a cycle by checking remaining incoming edges for each node
        // if(result.size() != set.size()) return new ArrayList<Order>();
        for(int count : indegree.values()) {
            if(count > 0) {
                System.out.println("There isn't exist topological order");
                return new ArrayList<>();
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Order o1 = new Order("A");
        Order o2 = new Order("B");
        Order o3 = new Order("C");
        Order o4 = new Order("D");
        OrderDependency od1 = new OrderDependency(o1, o2);
        OrderDependency od2 = new OrderDependency(o2, o3);
        //成环的情况就是把o4，改成o2，看看输出。
        OrderDependency od3 = new OrderDependency(o3, o4);
        List<OrderDependency> list = new ArrayList<>();
        list.add(od1);
        list.add(od2);
        list.add(od3);

        for (Order o : getOrder(list)){
            System.out.println(o.order);
        }
    }
}

Copy List with Random Pointer

LeetCode 138题 原题。。。

class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
}

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) {
            return null;
        }

        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();

        // deep copy each node
        RandomListNode cur = head;
        while(cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }

        // copy the next and random pointer
        cur = head;

        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }

        return map.get(head);
    }
}

High Five

题目是输入是一堆节点，节点里面有两个属性学生id和分数，保证每个学生至少会有5个分数，求每个人最高的5个分数的平均分。

返回的是Map, key是id，value是每个人最高5个分数的平均分double是平均分。

class Result{
    int id;
    int value;
    public Result(int id, int value){
        this.id = id;
        this.value = value;
    }
}

public class HighFive {
    public static Map<Integer, Double> getHighFive(Result[] results){
        if(results == null || results.length == 0) {
            return new HashMap<>();
        }

        HashMap<Integer, List<Integer>> scores = new HashMap<>();
        HashMap<Integer, Double> highFive = new HashMap<>();

        // put the result value to hashmap
        for(Result res : results) {
            if(!scores.containsKey(res.id)) {
                scores.put(res.id, new ArrayList<>());
            }
            scores.get(res.id).add(res.value);
        }

        for(int id : scores.keySet()) {
            double sum = 0.0;
            List<Integer> list = scores.get(id);
            // sort the list descending
            Collections.sort(list, Collections.reverseOrder());
            // calculate the averget of highest five scores
            for(int i = 0; i < 5; i++) {
                sum += list.get(i);
            }
            highFive.put(id, sum / 5.0);
        }

        return highFive;

    }

    public static void main(String[] args) {
        Result r1 = new Result(1, 95);
        Result r2 = new Result(1, 95);
        Result r3 = new Result(1, 91);
        Result r4 = new Result(1, 91);
        Result r5 = new Result(1, 93);
        Result r6 = new Result(1, 105);

        Result r7 = new Result(2, 6);
        Result r8 = new Result(2, 6);
        Result r9 = new Result(2, 7);
        Result r10 = new Result(2, 6);
        Result r11 = new Result(2, 6);
        Result[] arr = {r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11};
        Map<Integer, Double> res = getHighFive(arr);

        System.out.println(res.get(1) + " " +res.get(2));
    }
}

Copy the Random List

public class CopyRandomList {
    public static RandomListNode copy(RandomListNode head) {
        if(head == null) {
            return null;
        }

        copyNext(head);
        copyRandom(head);
        return split(head);
    }

    public static void copyNext(RandomListNode head) {
        while(head != null) {
            RandomListNode newHead = new RandomListNode(head.label);
            newHead.next = head.next;
            newHead.random = head.random;
            head.next = newHead;
            head = head.next;
        }
    }

    public static void copyRandom(RandomListNode head) {
        while(head != null) {
            RandomListNode newHead = head.next;
            if (newHead.random != null) {
                newHead.random = newHead.random.next;
            }
            head = head.next;
        }
    }

    public static RandomListNode split(RandomListNode head) {
        RandomListNode newHead = head.next;
        while(head != null){
            RandomListNode newNode = head.next;
            head.next = head.next.next;
            // skip the last one 
            if (newNode.next != null) {
                newNode.next = newNode.next.next;
            }
            head = head.next;
        }
        return newHead;
    }

}