Mock Interview: Amazon #5

Rank Trees

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        if (arr.length < 1) return new int[0];
        
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        
        int[] sorted = arr.clone();
        Arrays.sort(sorted);
        
        int rank = 1;
        int prev = sorted[0];
        m.put(prev, rank);
        for (int i = 1; i < sorted.length; i++) {
            if (! m.containsKey(sorted[i])) {
                rank++;
                m.put(sorted[i], rank);
            }
        }
        
        int[] result = new int[arr.length];
        for (int j = 0; j < arr.length; j++) {
            result[j] = m.get(arr[j]);
        }
        
        return result; 
    }
}

Runtime: 22 ms, faster than 92.03% of Java online submissions for Rank Transform of an Array.
Memory Usage: 55.9 MB, less than 44.18% of Java online submissions for Rank Transform of an Array.

제 사랑 쉬맵이...rg?^^

Two Sum BSTs

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        if (root1 == null || root2 == null) return false;
        
        TreeNode cur = root1;
        
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        exploreAll(root1, list);
        
        for (int i = 0; i < list.size(); i++) {
            if (contains(root2, target - list.get(i))) {
                return true;
            } else {
                continue; 
            }
        }
        
        return false; 
    }
    
    private void exploreAll(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        
        list.add(root.val);
        
        if (root.left != null) {
            exploreAll(root.left, list);
        }
        
        if (root.right != null) {
            exploreAll(root.right, list);
        }
    }
    
    
    private boolean contains(TreeNode root, int target) {
        int val = root.val;
        
        while (root != null) {
            if (root.val == target) {
                return true;
            }
            
            if (root.val < target) {
                contains(root.right, target);
            } else {
                contains(root.left, target); 
            }
        }
        
        return false; 
    }
}

Time Limit Exceeded
처음엔 재귀를 2번 돌렸다가.... 이건 아니다 아차^^ 했죠

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private Set<Integer> list1 = new HashSet<Integer>();
    private ArrayList<Integer> list2 = new ArrayList<Integer>();
    public boolean twoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        if (root1 == null || root2 == null) return false;
        
        TreeNode cur = root1;
        
        exploreAll(root1);
        exploreAll2(root2);
        
        for (int i = 0; i < list2.size(); i++) {
            if (list1.contains(target - list2.get(i))) {
                return true;
            } 
        }
        
        return false; 
    }
    
    private void exploreAll(TreeNode root) {
        if (root == null) {
            return;
        }

        exploreAll(root.left);
        
        list1.add(root.val);
        
        exploreAll(root.right);
    }
    
    private void exploreAll2(TreeNode root) {
        if (root == null) {
            return;
        }

        exploreAll2(root.left);
        
        list2.add(root.val);
        
        exploreAll2(root.right);
    }
    
}

Runtime: 3 ms, faster than 57.56% of Java online submissions for Two Sum BSTs.
Memory Usage: 39.8 MB, less than 56.79% of Java online submissions for Two Sum BSTs.

inorder로 root1과 root2를 정렬해주고 하나는 쉬셋이, 하나는 arraylist에 넣어줘서 arraylist를 탐구하면서 쉬셋이에 영혼의 짝꿍이 있는지 찾아줬읍니다