amazon OA2

1. Deep Copy

原题是https://leetcode.com/problems/copy-list-with-random-pointer/ 大致就是两次循环：

1. 第一次：创建所有的RandomListNode，但是这次只关注next。并且存HashMap，key是原来的点，value是新建的点
2. 第二次：从HashMap中取值来改变random

代码如下：

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode dummy_node = new RandomListNode(-1);
        RandomListNode cur = head;
        RandomListNode prev_node = dummy_node;
        HashMap<RandomListNode, RandomListNode> hmap = new HashMap<RandomListNode, RandomListNode>();
        while (cur != null) {
            RandomListNode new_node = new RandomListNode(cur.label);
            hmap.put(cur, new_node);
            prev_node.next = new_node;
            prev_node = new_node;
            cur = cur.next;
        }

        cur = head;
        RandomListNode cur_copy = dummy_node.next;
        while (cur != null) {
            cur_copy.random = hmap.get(cur.random);
            cur = cur.next;
            cur_copy = cur_copy.next;
        }
        return dummy_node.next;
    }
}

1. Longest Palindrome

public class Solution {
    public int longestPalindrome(String s) {
        int maxLen = 0;
        HashMap<Character, Integer> hmap = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            if (hmap.containsKey(s.charAt(i)) == false) {
                hmap.put(s.charAt(i), 1);
            }
            else {
                hmap.put(s.charAt(i), hmap.get(s.charAt(i)) + 1);
                if (hmap.get(s.charAt(i)) % 2 == 0) {
                    maxLen += 2;
                }
            }
        }
        return maxLen == s.length() ? maxLen : maxLen + 1;

    }
}

1. Rectangle Overlap

这个应该是Leetcode上面题的变种。。先上Leetcode解法：

public class Solution {
    public int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) {
        int ll = Math.max(A, E);
        int lr = Math.max(ll, Math.min(C, G));
        int hb = Math.max(B, F);
        int ht = Math.max(hb, Math.min(D, H));
        return (C - A) * (D - B) - (lr - ll) * (ht - hb) + (G - E) * (H - F);
    }
}

完整版：

public class Overlap {
    public static boolean check(Point l1, Point r1, Point l2, Point r2) {
        if (l1.x > r2.x || l2.x > r1.x) {
            return false;
        }
        if (l1.y < r2.y || l2.y < r1.y) {
            return false;
        }
        return true;
    }

    public class Point {
        double x;
        double y;
        public Point(double x, double y) {
            this.x = x;
            this.y = y;
        }
    }
}

1. Window Sum

public static List<Integer> getSum(List<Integer> window, int k) {
    List<Integer> res = new ArrayList<Integer>();
    if (window == null || window.size() < k || k <= 0) {
        return res;
    }
    int prev = 0;
    int summation = 0;
    for (int i = 0; i < k; ++i) {
        summation += window.get(i);
    }
    res.add(summation);
    for (int i = k; i < window.size(); ++i) {
        summation -= window.get(prev);
        summation += window.get(i);
        prev++;
        res.add(summation);
    }
    return res;
}

1. K nearest Point

public static Point[] findNearest2(Point[] array, int k) {
    if (k <= 0 || array == null || array.length == 0 || k > array.length) {
        return null;
    }
    Point[] pArr = new Point[k];
    Arrays.sort(array, new Comparator<Point>(){
        public int compare(Point p1, Point p2) {
            double delta = getDist(p1) - getDist(p2);
            if (delta < 0) {
                return -1;
            }
            else if (delta > 0) {
                return 1;
            }
            else {
                return 0;
            }
        }
    });

    for (int i = 0; i < k; ++i) {
        pArr[i] = array[i];
    }
    return pArr;
}

public static Point[] findNearest(Point[] array, int k) {
    Point[] pArr = new Point[k];
    if (array == null || array.length == 0 || array.length < k) {
        return pArr;
    }
    PriorityQueue<Point> heap = new PriorityQueue<Point>(k + 1, new Comparator<Point>(){
        public int compare(Point p1, Point p2) {
            double delta = getDist(p2) - getDist(p1);
            if (delta > 0) {
                return 1;
            }
            else if (delta < 0) {
                return -1;
            }
            return 0;

        }
    });

    for (int i = 0; i < array.length; ++i) {
        heap.offer(array[i]);
        if (heap.size() > k) {
            heap.poll();
        }
    }

    int index = k - 1;
    while (!heap.isEmpty() && k >= 0) {
        pArr[index--] = heap.poll();
    }
    return pArr;
}

private static double getDist(Point p) {
    return Math.sqrt(p.x * p.x + p.y * p.y);
}

1. High Five

public static Map<Integer, Double> findFiveScore(Result[] results) {
        Map<Integer, Double> res = new HashMap<Integer, Double>();
        Map<Integer, List<Integer>> hmap = new HashMap<Integer, List<Integer>>();
        if (results == null || results.length == 0) {
            return res;
        }

        for (int i = 0; i < results.length; ++i) {
            if (!hmap.containsKey(results[i].id)) {
                hmap.put(results[i].id, new ArrayList<Integer>());
            }
            hmap.get(results[i].id).add(results[i].value);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(5);
        for (Integer id : hmap.keySet()) {
            for (Integer score : hmap.get(id)) {
                heap.offer(score);
                if (heap.size() > 5) {
                    heap.poll();    // throw the smallest
                }
            }
            double total = 0;
            while (!heap.isEmpty()) {
                total += heap.poll();
            }
            res.put(id, (double)(total) / 5.0);
        }
        return res;
    }

1. Company Tree

public static Node getHighAve(Node root) {
    double[] globalMax = new double[1];
    globalMax[0] = Double.MIN_VALUE;
    if (root == null || root.children == null || root.children.size() == 0) {
        return null;
    }
    Node[] maxNode = new Node[1];
    recursion(root, globalMax, maxNode);
    printOut = globalMax[0];
    return maxNode[0];
}

private static SumCount recursion(Node root, double[] globalMax, Node[] maxNode) {
    if (root.children == null || root.children.size() == 0) {
        return new SumCount(root.val, 1);
    }
    SumCount sc = new SumCount(root.val, 1);
    for (Node node : root.children) {
        SumCount tmp = recursion(node, globalMax, maxNode);
        sc.cnt += tmp.cnt;
        sc.val += tmp.val;
    }
    double val = (double)(sc.val) / (double)(sc.cnt);
    if (val > globalMax[0]) {
        globalMax[0] = val;
        maxNode[0] = root;
    }
    return sc;
}

1. Longest Palindromic Substring

public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int maxLen = 0;
        String res = "";
        for (int i = 0; i < s.length(); ++i) {
            int left = i - 1;
            int right = i + 1;
            // condition 1
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            int l = right - left - 1;
            if (l > maxLen) {
                maxLen = l;
                res = s.substring(left + 1, right);
            }
            left = i;
            right = i + 1;

            // condition 2
            while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            l = right - left - 1;
            if (l > maxLen) {
                maxLen = l;
                res = s.substring(left + 1, right);
            }
        }
        return res;
    }
}

1. OD

import java.util.*;

class Order {
    String order = "";

    public Order (String order) {
        this.order = order;
    }
}

class OD {
    Order curr;
    Order pre;

    public OD (Order pre, Order curr) {
        this.curr = curr;
        this.pre = pre;
    }    
}

public class OrderDepend {
    public static List<Order> findOrder(List<OD> Orders) {
        Map<String, Integer> indegree = new HashMap<String, Integer>();
        Map<String, List<String>> graph = new HashMap<String, List<String>>();
        Set<String> orderSet = new HashSet<String>();

        // construct
        for (OD o : Orders) {
            String from = o.pre.order;
            String to = o.curr.order;

            orderSet.add(from);
            orderSet.add(to);

            if (!indegree.containsKey(from)) {
                indegree.put(from, 0);
            }
            if (!indegree.containsKey(to)) {
                indegree.put(to, 1);
            }
            else {
                indegree.put(to, indegree.get(to) + 1);
            }

            if (!graph.containsKey(from)) {
                graph.put(from, new ArrayList<String>());
            }
            graph.get(from).add(to);
        }

        // Initialize the Queue
        Queue<String> queue = new LinkedList<String>();
        for (String key : indegree.keySet()) {
            if (indegree.get(key) == 0) {
                queue.offer(key);
            }
        }

        List<Order> res = new ArrayList<Order>();
        while (!queue.isEmpty()) {
            String item = queue.poll();
            res.add(new Order(item));
            if (graph.containsKey(item)) {
                for (String o : graph.get(item)) {
                    indegree.put(o, indegree.get(o) - 1);
                    if (indegree.get(o) == 0) {
                        queue.offer(o);
                    }
                }
            }
        }
        return res.size() == indegree.size() ? res : null;
    }

    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");
        Order o6 = new Order("E");
        Order o7 = new Order("F");
        Order o8 = new Order("G");
        Order o9 = new Order("H");
        OD od1 = new OD(o1, o2);
        OD od2 = new OD(o2, o3);
        OD od3 = new OD(o3, o4);
        OD od4 = new OD(o4, o6);
        OD od5 = new OD(o7, o8);
        OD od6 = new OD(o9, o7);
        OD od7 = new OD(o4, o9);
        List<OD> list = new ArrayList<OD>();
        list.add(od1);
        list.add(od2);
        list.add(od3);
        list.add(od4);
        list.add(od5);
        list.add(od6);
        list.add(od7);

/*
        Order o1 = new Order("泡面");
        Order o2 = new Order("泡面");
        Order o3 = new Order("SF");
        Order o4 = new Order("租车");
        Order o5 = new Order("SF");
        Order o6 = new Order("泡面");
        Order o7 = new Order("租车");
        Order o8 = new Order("SF");
        Order o9 = new Order("爽(每个行为只输出了一次对吧)");
        OD od1 = new OD(o1, o3);
        OD od2 = new OD(o2, o7);
        OD od3 = new OD(o3, o9);
        OD od4 = new OD(o4, o3);
        OD od5 = new OD(o6, o9);
        OD od6 = new OD(o8, o9);
        OD od7 = new OD(o2, o5);

        List<OD> list = new ArrayList<>();
        list.add(od1);
        list.add(od2);
        list.add(od3);
        list.add(od4);
        list.add(od5);
        list.add(od6);
        list.add(od7);
        //最后输出就是这种形式
        * */

        List<Order> res = findOrder(list);
        for (int i = 0; i < res.size(); i++) {
            System.out.print(res.get(i).order);
            if (i+1 < res.size()){
                System.out.print(" -> ");
            }
        }
    }
}

1. MST

import java.util.*;

class Connection{ String node1; String node2; int cost; public Connection(String a, String b, int c){ node1 = a; node2 = b; cost = c; } }

public class MST { public static List findMST(List citylist) { if (citylist == null || citylist.size() == 0) { return null; } Set citySet = new HashSet(); // size of city Map unionMap = new HashMap(); Collections.sort(citylist, new Comparator() { public int compare(Connection c1, Connection c2) { return c1.cost - c2.cost; } });

    List<Connection> res = new ArrayList<Connection>();

    for (Connection conn : citylist) {
        String c1 = conn.node1;
        String c2 = conn.node2;
        citySet.add(c1);
        citySet.add(c2);
        unionMap.put(c1, c1);
        unionMap.put(c2, c2);
    }

    for (Connection conn : citylist) {
        String c1 = conn.node1;
        String c2 = conn.node2;
        if (union(c1, c2, unionMap)) {
            res.add(conn);
        }
    }

    Collections.sort(res, new Comparator<Connection>() {
        public int compare(Connection c1, Connection c2) {
            if (c1.node1.equals(c2.node1)) {
                return c1.node2.compareTo(c2.node2);
            }
            return c1.node1.compareTo(c2.node1);
        }
    });
    return (res.size() + 1) == citySet.size() ? res : null;
}

private static boolean union(String c1, String c2, Map<String, String> unionMap) {
    String parent1 = find(c1, unionMap);
    String parent2 = find(c2, unionMap);

    if (parent1.equals(parent2)) {
        return false;
    }
    else {
        unionMap.put(parent1, parent2);
        return true;
    }
}

private static String find(String city, Map<String, String> unionMap) {
    if (city.equals(unionMap.get(city))) {
        return city;
    }
    return find(unionMap.get(city), unionMap);
}

public static void main(String[] args) {
    /*
    // TODO Auto-generated method stub
    Connection[] citys = new Connection[10];
    citys[0] = new Connection("A","B",6);
    citys[1] = new Connection("A","D",1);
    citys[2] = new Connection("A","E",5);
    citys[3] = new Connection("B","C",3);
    citys[4] = new Connection("B","D",5);
    citys[5] = new Connection("C","D",6);
    citys[6] = new Connection("C","F",6);
    citys[7] = new Connection("D","F",4);
    citys[8] = new Connection("D","E",5);
    citys[9] = new Connection("R","E",1);

    List<Connection> list = new ArrayList<Connection>();
    for (Connection city : citys) {
        list.add(city);
    }
    * */

    ArrayList<Connection> connections = new ArrayList<>();
    //这里还是一个苯环形状，有化学出身的看到这里可以鼓掌了
    connections.add(new Connection("A","B",6));
    connections.add(new Connection("B","C",4));
    connections.add(new Connection("C","D",5));
    connections.add(new Connection("D","E",8));
    connections.add(new Connection("E","F",1));
    connections.add(new Connection("B","F",10));
    connections.add(new Connection("E","C",9));
    connections.add(new Connection("F","C",7));
    connections.add(new Connection("B","E",3));
    connections.add(new Connection("A","F",1));


    List<Connection> res = new ArrayList<Connection>();
    res = findMST(connections);
    for (Connection c : res){
        System.out.println(c.node1 + " -> " + c.node2 + " 需要花费大洋 : " + c.cost);
    }
}

}