Mock Interview: Facebook #5

이북이가 배신했어요..

349. Intersection of Two Arrays

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> s = new HashSet<Integer>();
        Set<Integer> s2 = new HashSet<Integer>();
        for (int i = 0; i < nums1.length; i++) {
            s.add(nums1[i]);
        }

        for (int j = 0; j < nums2.length; j++) {
            if (s.contains(nums2[j])) {
                s2.add(nums2[j]);
            }
        }
        
        Integer[] result = new Integer[s2.size()];
        
        result = s2.toArray(result);
        int[] result2 = Arrays.stream(result).mapToInt(Integer::intValue).toArray();
        
        return result2;
    }
}

Runtime: 4 ms, faster than 32.06% of Java online submissions for Intersection of Two Arrays.
Memory Usage: 38.9 MB, less than 76.47% of Java online submissions for Intersection of Two Arrays.

Integer[]에서 int[]로 변환하는데 애먹었네요ㅠ

This is a Facebook interview question.
They ask for the intersection, which has a trivial solution using a hash or a set.

Then they ask you to solve it under these constraints:
O(n) time and O(1) space (the resulting array of intersections is not taken into consideration).
You are told the lists are sorted.

Cases to take into consideration include:
duplicates, negative values, single value lists, 0's, and empty list arguments.
Other considerations might include
sparse arrays.

function intersections(l1, l2) {
    l1.sort((a, b) => a - b) // assume sorted
    l2.sort((a, b) => a - b) // assume sorted
    const intersections = []
    let l = 0, r = 0;
    while ((l2[l] && l1[r]) !== undefined) {
       const left = l1[r], right = l2[l];
        if (right === left) {
            intersections.push(right)
            while (left === l1[r]) r++;
            while (right === l2[l]) l++;
            continue;
        }
        if (right > left) while (left === l1[r]) r++;
         else while (right === l2[l]) l++;
        
    }
    return intersections;
}

이북이 장난 아니네요^^

865. Smallest Subtree with all the Deepest Nodes

class Solution {
    Map<TreeNode, Integer> depth;
    int max_depth;
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        depth = new HashMap();
        depth.put(null, -1);
        dfs(root, null);
        max_depth = -1;
        for (Integer d: depth.values())
            max_depth = Math.max(max_depth, d);

        return answer(root);
    }

    public void dfs(TreeNode node, TreeNode parent) {
        if (node != null) {
            depth.put(node, depth.get(parent) + 1);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }

    public TreeNode answer(TreeNode node) {
        if (node == null || depth.get(node) == max_depth)
            return node;
        TreeNode L = answer(node.left),
                 R = answer(node.right);
        if (L != null && R != null) return node;
        if (L != null) return L;
        if (R != null) return R;
        return null;
    }
}

Runtime: 1 ms, faster than 32.10% of Java online submissions for Smallest Subtree with all the Deepest Nodes.
Memory Usage: 38.3 MB, less than 33.98% of Java online submissions for Smallest Subtree with all the Deepest Nodes.

class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        return dfs(root).node;
    }

    // Return the result of the subtree at this node.
    public Result dfs(TreeNode node) {
        if (node == null) return new Result(null, 0);
        Result L = dfs(node.left),
               R = dfs(node.right);
        if (L.dist > R.dist) return new Result(L.node, L.dist + 1);
        if (L.dist < R.dist) return new Result(R.node, R.dist + 1);
        return new Result(node, L.dist + 1);
    }
}

/**
 * The result of a subtree is:
 *       Result.node: the largest depth node that is equal to or
 *                    an ancestor of all the deepest nodes of this subtree.
 *       Result.dist: the number of nodes in the path from the root
 *                    of this subtree, to the deepest node in this subtree.
 */
class Result {
    TreeNode node;
    int dist;
    Result(TreeNode n, int d) {
        node = n;
        dist = d;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Smallest Subtree with all the Deepest Nodes.
Memory Usage: 38.5 MB, less than 27.12% of Java online submissions for Smallest Subtree with all the Deepest Nodes.

이게 훨씬 빠르긴 한데... class까지 만들 여유가...^_^