Mock Interview: Facebook

1027. Longest Arithmetic Subsequence

class Solution {
    public int longestArithSeqLength(int[] nums) {
        int length = 1;
        
        int curlength = 1;
        int prev = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > prev) {
                curlength++;
                prev = nums[i];
                length = Math.max(length, curlength);
            } else {
                curlength = 1;
                prev = nums[i];
            }
        }
        return length;
    }
}

13 / 62 test cases passed.
문제를 잘못 읽었어요..^^
그래도 어느 정도 됐네요

class Solution {
    public int longestArithSeqLength(int[] nums) {
        
        int result = 1;
        int prev = nums[0];
        
        Queue<Integer> q = new LinkedList<Integer>();
        
        q.add(prev);
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > q.peek()) {
                q.add(nums[i]);
                result = Math.max(q.size(), result);
            } else {
                while (q.peek() < nums[i]) {
                    q.poll();
                }
                q.add(nums[i]);
            }
        }
        
        return result;
        
    }
}

1 / 62 test cases passed.

Queue를 써서 해보려고 했는데
풀다가 시간이 끝나버렸어요..

루션이

class Solution {
    public int longestArithSeqLength(int[] A) {
        if (A.length <= 1) return A.length;
       
        int longest = 0;
        
        // Declare a dp array that is an array of hashmaps.
        // The map for each index maintains an element of the form-
        //   (difference, length of max chain ending at that index with that difference).        
        HashMap<Integer, Integer>[] dp = new HashMap[A.length];
        
        for (int i = 0; i < A.length; ++i) {
            // Initialize the map.
            dp[i] = new HashMap<Integer, Integer>();
        }
        
        for (int i = 1; i < A.length; ++i) {
            int x = A[i];
            // Iterate over values to the left of i.
            for (int j = 0; j < i; ++j) {
                int y = A[j];
                int d = x - y;
                
                // We at least have a minimum chain length of 2 now,
                // given that (A[j], A[i]) with the difference d, 
                // by default forms a chain of length 2.
                int len = 2;  
                
                if (dp[j].containsKey(d)) {
                    // At index j, if we had already seen a difference d,
                    // then potentially, we can add A[i] to the same chain
                    // and extend it by length 1.
                    len = dp[j].get(d) + 1;
                }
                
                // Obtain the maximum chain length already seen so far at index i 
                // for the given differene d;
                int curr = dp[i].getOrDefault(d, 0);
                
                // Update the max chain length for difference d at index i.
                dp[i].put(d, Math.max(curr, len));
                
                // Update the global max.
                longest = Math.max(longest, dp[i].get(d));
            }
        }
        
        return longest;
    }
}

Runtime: 643 ms, faster than 34.01% of Java online submissions for Longest Arithmetic Subsequence.
Memory Usage: 58.7 MB, less than 64.52% of Java online submissions for Longest Arithmetic Subsequence.

HashMap<Integer, Integer>[] dp = new HashMap[A.length]
array of 쉬맵이
....까지만 이해돼요ㅠ
전씨를 믿어봅니다^^

/**
 * 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 isCompleteTree(TreeNode root) {
        Queue<TreeNode> tree = new LinkedList<TreeNode>();
        if (root == null) return true;
        
        tree.add(root);
        
        boolean fin = false; 
        while (! tree.isEmpty()) {
            TreeNode t = tree.poll();
            if (t == null) {
                fin = true;
            } else {
                if (fin) {
                    return false;
                }
                tree.add(t.left);
                tree.add(t.right);
            }
        }
        
        return true; 
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Check Completeness of a Binary Tree.
Memory Usage: 38.4 MB, less than 50.12% of Java online submissions for Check Completeness of a Binary Tree.

이번에도 BFS 이용!!
처음에는 complete binary tree가 아닌 그냥 binary tree인지만 확인해서 틀렸는데 boolean fin을 넣어줘서 해결했읍니다