[Leetcode] Lowest Common Ancestor of a BST - Linkedin interview questions

class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        

        int pVal = p.val;

        int qVal = q.val;

        TreeNode node = root;

        while(node != null) {

            int parentVal = node.val;

            if(pVal > parentVal && qVal > parentVal) {

                node = node.right;

            } else if(pVal < parentVal && qVal < parentVal) {

                node = node.left;

            } else {

                return node;

            }

        }

        return null;

    }

    public TreeNode lowestCommonAncestorRecursive(TreeNode root, TreeNode p, TreeNode q) {

        int parentVal = root.val;

        int pVal = p.val;

        int qVal = q.val;

        if(pVal > parentVal && qVal > parentVal) {

            return lowestCommonAncestor(root.right, p , q);

        } else if(pVal < parentVal && qVal < parentVal) {

            return lowestCommonAncestor(root.left, p, q);

        } else {

            return root;

        }

    }

} 

[Leetcode] Power - Linkedin Interview Question

public class Solution {
    public double pow(double x, int n) {
        if(n == 0)
            return 1;
        if(n<0){
            n = -n;
            x = 1/x;
        }
        return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);
    } 

} 

[Leetcode] Random pick with weight

 class Solution {

    private int[] prefixSums;

    private int totalSum;

    public Solution(int[] w) {

        this.prefixSums = new int[w.length];

        int prefixSum = 0;

        for (int i = 0; i < w.length; ++i) {

            prefixSum += w[i];

            this.prefixSums[i] = prefixSum;

        }

        this.totalSum = prefixSum;

    }

    public int pickIndex() {

        double target = this.totalSum * Math.random();

        int i = 0;

        // run a linear search to find the target zone

        for (; i < this.prefixSums.length; ++i) {

            if (target < this.prefixSums[i])

                return i;

        }

        // to have a return statement, though this should never happen.

        return i - 1;

  }

} 

[Leetcode] Partition to K Equal Sum Subsets

BackTracking Approach

 class Solution {

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % k != 0 || maxNum > sum / k) {
            return false;
        }
        return canPartitionKSubsetsFrom(nums, k, new boolean[nums.length], sum / k, 0, 0);
    }
    
    private boolean canPartitionKSubsetsFrom(int[] nums, 
                                             int k,
                                             boolean[] visited, 
                                             int targetSubsetSum, 
                                             int curSubsetSum, 
                                             int nextIndexToCheck) {
        if (k == 0) {
            return true;
        }
        
        if (curSubsetSum == targetSubsetSum) {
            return canPartitionKSubsetsFrom(nums, 
                                            k - 1,
                                            visited,
                                            targetSubsetSum,
                                            0,
                                            0);
        }
        
        for (int i = nextIndexToCheck; i < nums.length; i++) {
            if (!visited[i] && curSubsetSum + nums[i] <= targetSubsetSum) {
                visited[i] = true;
                if (canPartitionKSubsetsFrom(nums, 
                                             k,
                                             visited,
                                             targetSubsetSum,
                                             curSubsetSum + nums[i],
                                             i + 1)) {
                    return true;
                }
                visited[i] = false;
            }
        }
        
        return false;
    }
}

[Leetcode] Accounts Merge

Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Solution 1:

Find the connected components in the graph

class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, String> emailToName = new HashMap();
        Map<String, ArrayList<String>> graph = new HashMap();
        for (List<String> account: accounts) {
            String name = "";
            for (String email: account) {

                // the first word is the email
                if (name == "") {
                    name = email;
                    continue;
                }

                // every email is getting connected with an edge to the first email in that list
                graph.computeIfAbsent(email, x-> new ArrayList<String>()).add(account.get(1));

                // the first email is also getting connected by an edge to all the other emails in the list
                graph.computeIfAbsent(account.get(1), x-> new ArrayList<String>()).add(email);
                emailToName.put(email, name);
            }
        }

        Set<String> seen = new HashSet();
        List<List<String>> ans = new ArrayList();
        for (String email: graph.keySet()) {
            if (!seen.contains(email)) {
                seen.add(email);
                Stack<String> stack = new Stack();
                stack.push(email);
                List<String> connectedComponent = new ArrayList();
                while (!stack.empty()) {

                    // once all the nodes in a connectedComponent are looked at, the stack becomes empty
                    String node = stack.pop();
                    connectedComponent.add(node);
                    for (String nei: graph.get(node)) {
                        if (!seen.contains(nei)) {
                            seen.add(nei);
                            stack.push(nei);
                        }
                    }
                }
                Collections.sort(connectedComponent);
                connectedComponent.add(0, emailToName.get(email));

                // add the name to the first element in the connectedComponents list
                ans.add(connectedComponent);
            }
        }
        return ans;
    }
}

[Leetcode] Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Solution :

1 2 3 4 5 6 7 8 9 10 11 12 13

public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if (root == null) return null; if (root.val <= p.val) { return inorderSuccessor(root.right, p); } else { TreeNode left = inorderSuccessor(root.left, p); return (left != null) ? left : root; } } }

[Leetcode] Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

    2
   / \
  1   3

Output:
1

Example 2: 

Input:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution : 

Most binary tree problems, in an interview setting can be solved by 5 kinds of traversals - inorder, postorder, preorder, BFS and DFS. I have decided to start a series of posts, where I shall be covering binary trees only. All the solutions, I provide will circle around these 5 traversal themes. My goal will be to establish a pattern which the readers can pick up. Hopefully, that will enable the readers in developing original thinking derived on these fundamentals for problems they may not have seen before.

In this particular problem, I will build up on the level order traversal (BFS) solution. This will use existing knowledge and help modify that code to come up with the new solution. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); // Queue for // level order BFS traversal List<List<Integer>> wrapList = new LinkedList<List<Integer>>(); // wrapList stores the reverse level order solution // index 0 has the lowest level from left to right // so the first element of wrap list is the solution to the problem if(root == null) return 0; queue.offer(root); while(!queue.isEmpty()){ int levelNum = queue.size(); List<Integer> subList = new LinkedList<Integer>(); for(int i=0; i<levelNum; i++) { if(queue.peek().left != null) queue.offer(queue.peek().left); if(queue.peek().right != null) queue.offer(queue.peek().right); subList.add(queue.poll().val); } wrapList.add(0, subList); } return wrapList.get(0).get(0); } }