Amazon Interview Experience | Set 199 (On-Campus for Internship) 题解

1. 给个数组, 已经排序了, 找到第一个比n大的数. 如果没有, 返回-1.

二分搜索一下就可以, 注意一下返回-1的条件.

  public static int fixBox(int[] nums, int product) {
        int n = nums.length;
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < product)
                l = mid + 1;
            else
                r = mid - 1;
        }
        if (r + 1 >= nums.length)
            return -1;
        return nums[r + 1];
    }

2.给一个二叉树, 找到最长的path. 如果最长不只一个, 返回字典序第一个最长.

这个需要点技巧, 我们自底向上,对树进行递归, 把path 放到一个stack里, 然后如果找到了一个更长的path(stack的size) 就更新一下. 因为最长的path不一定在root的同一侧, 所以最后我们还需要比较一下当前节点左右哪边有最长path.

public static Stack<TreeNode> longestPath(TreeNode root) {
        if (root == null)
            return new Stack<TreeNode>();
        Stack<TreeNode> left = longestPath(root.left);
        Stack<TreeNode> right = longestPath(root.right);
        if (left.size() + right.size()> max) {
            max = left.size() + right.size();
            Stack<TreeNode> tmp = new Stack<>();
            tmp.addAll(left);
            tmp.addAll(right);
            tmp.push(root);
            path = tmp;
        }
        left.push(root);
        right.push(root);
        return left.size() > right.size() ? left : right;
    }

3. 给一个二叉树, 求任意两个node的path长.

这个是个靠综合概念的题, 首先我们要知道这2个节点并不一定在root的同一侧. 所以我们需要找到两个节点的lca. 其次, 我们要知道root到两个节点分别的长度, 和root到lca的长度, 然后用d_node1 + d_node2 – 2*d_lca就是他们之间的长度.为什么呢? 试想一下, LCA的定义就是最短的两个节点的交点. 那么我们可以证明, 他们之间的path毕竟经过lca, 所以我们通过这个公式计算这两个节点之间的path的长度是可行的.

  static int max = Integer.MIN_VALUE;
    static Stack<TreeNode> path = new Stack<>();


    public static int lengthBetweenNodes(TreeNode p, TreeNode q, TreeNode root){
        TreeNode lca = lca(root, p, q);
        int d1 = distance(root, p, 0);
        int d2 = distance(root, q, 0);
        int dlca = distance(root, lca,0);
        return d1+d2-2*dlca;
    }
    public static int distance(TreeNode root, TreeNode p, int k) {
        if (root == null)
            return 0;
        if (root == p)
            return k;
        return distance(root.left,p,k+1)+distance(root.right,p,k+1);
    }
    public static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q)
            return root;
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);
        if (left != null && right != null)
            return root;
        else
            return left != null ? left : right;
    }

4. 给一个数组, 数字之间最大的差的绝对值是1, 让你找到一个数字n的第一次出现的坐标, 没有就返回-1

很简单, 我们可以证明, 在开始时, 数字n可能出现的地方, 就是n-nums[0], 如果没有, 就是n-nums[1]…..一直找就可以了.

 public static int absoluteDifference(int[] nums, int n) {
        int i = 0;
        while (i <= nums.length-1){
            if (nums[i] == n)
                return i;
            int diff = nums[i] - n;
            i+=diff;
        }
        return -1;
    }

5. 判断一个list是不是回文. Leetcode原题.

public static boolean palindromeList(ListNode head) {
        ListNode tmp = head;
        ListNode p = head;
        ListNode q = tmp;
        while (p != null){
            q = new ListNode(head.val);
            p = p.next;
            q = q.next;
        }
        ListNode rev = reverse(head);
        while (tmp != null) {
            if (tmp.val!=rev.val){
                return false;
            }
            rev = rev.next;
            tmp = tmp.next;
        }
        return true;
    }
    public static ListNode reverse(ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead  = head;
            head = next;
        }
        return newHead;
    }