[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;
    }
}