ML EXPLAINED

Tag: Coding Interview

  • LeetCode 3371 – Identify The Largest Outlier In An Array (Python)

    The problem seems to be pretty popular with Amazon and Meta (formerly known as Facebook) in the past 3 months.

    At its core it’s a math problem and not a programming problem, so if you can figure out the mathematical trick, then this problem is pretty simple.

    We’ve been given an array where n-2 are special numbers and one of the two remaining numbers is the sum of the these special numbers and the other is the outlier. So how do you figure out the outlier?

    The trick is that if you remove the outlier then the array is simply 2S, where S = x_{1}+x_{2}+...+x_{n-2}. So if we take the total sum of the array minus the outlier then it has to be an even number and thus has to be divisible by 2.
    Another thing is that, since the sum of array minus the outlier is 2S, then there must exist a number S in the array. We can check this using a dictionary.

    Our algorithm will be to initialise an outlier variable and then check each number one by one, compute the total minus the number. Check if the total is divisible by 2 and if the half of this number exists in the array, aka, is there a count > 0 in our array. To check this in O(1) time, we maintain a counter of all the numbers in our array. If these conditions are satisfied, then this number could be a possible outlier and we update our outlier variable. If not, we reset the count of the number and our total.

    In the end we will return this outlier.

    from collections import Counter
class Solution:
    def getLargestOutlier(self, nums: List[int]) -> int:
        total_sum = sum(nums)
        counts = Counter(nums)
        outlier = float("-inf")

        for num in nums:
            counts[num]-=1
            total_sum-=num
            if total_sum%2==0 and counts[total_sum//2]>0:
                outlier = max(outlier,num)

            counts[num]+=1
            total_sum+=num
        return outlier

  • LeetCode 1650 – Lowest Common Ancestor of a Binary Tree III

    This question has been asked a lot by Meta (formerly known as Facebook) in the past 3 months.

    The question is categorised as a medium, but if you look at the class structure of the tree, you’ll realise that the answer is pretty straightforward. You could find the LCA by using previous approaches like searching through the entire tree and then getting the LCA, but here we’ve access to the parent node as well in the Node class. Also both, p and q exist in the tree.

    class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

    So all we’ve to do is to build a path set from either p or q to the root. Once this set is built, we then travel from the other node to the root of the binary tree. Once we find the node in the path set, that’s the LCA.

    In this example, our path set from p to root will be {5,3}. We then start at q and iterate towards the root, carefully examining each node along the way. We first check if 4 is in the path; if it is not found, then we move up to 2, and check again. We then move up to its parent 5. Here we find 5 in the path, so we return 5.

    class Solution:
    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
        path = set()
        while p:
            path.add(p)
            p = p.parent

        while True:
            if q in path:
                return q
            else:
                q = q.parent

    Here we built a path set from p to root. Then we initialise another while loop, and it’s set to run indefinitely as we know LCA will exist as both p and q are in the tree. At each step we take towards the root, we check if q exists in the path set, the moment we find it, that’s the LCA.

    Hope this was helpful and let me know in the comments if you want me to cover other LeetCode questions or machine learning topics.