Category: Coding Interview

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.
March 23, 2025
LeetCode 2594 – Minimum Time To Repair Cars
Although this problem is not frequently asked by companies, it offers an interesting perspective. Initially, this problem may seem to require a complex solution, but it can be efficiently solved using binary search.

Binary Search Approach

The key is to frame the problem as finding the minimum time required to repair all cars, within a range from 1 to the maximum possible time. The maximum possible time is determined by the minimum rank multiplied by the square of the number of cars. Since the number of cars is always greater than 0, the theoretical minimum possible time is 1, and the solution lies within this range.

Therefore, the problem is transformed into a binary search, where at each iteration, we check if all cars can be repaired within a given time. If yes, we search the left half for a potentially lower time; otherwise, we search the right half.

We know that a mechanic with rank ‘r’ takes $r*n^{2}$ time to repair ‘n’ cars, so within time ‘t’, they can repair sqrt(t/r) cars. We need to create a helper function that returns a boolean indicating whether all cars can be repaired within a given time ‘t’. We have to take the floor and then we sum the values to determine number of cars that can be repaired in time t. If this value is greater than or equal to the desired number of cars, we will return True.
```
def can_repair(self, t,n,ranks):
        n_each_mech = [int((t/r)**0.5) for r in ranks]
        return sum(n_each_mech)>=n
```
The solution to the problem.
```
class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        min_rank = min(ranks)
        low = 1
        high = min_rank*cars*cars

        min_time = None

        while low <= high:
            mid = (high+low)//2

            if self.can_repair(mid,cars,ranks):
                min_time = mid
                high = mid-1

            else:
                low = mid+1
        
        return min_time

    def can_repair(self, t,n,ranks):
        n_each_mech = [int((t/r)**0.5) for r in ranks]
        return sum(n_each_mech)>=n
```
Complexity Analysis

The time complexity is O(N log(C)), where N is the number of mechanics and C is the range of possible times. The binary search contributes a factor of O(log(C)), and the can_repair function contributes a factor of O(N). The space complexity is O(1) as we are only using constant extra space.

Let me know if you would like to cover any additional aspects or if you have any further questions.
March 16, 2025
Pandas Essentials – Transform and Qcut
Suppose you want to calculate aggregated count features and add them to your data frame as a feature. What you would typically do is, create a grouped data frame and then do a join. What if you can do all that in just one single line of code. Here you can use the transform functionality in pandas.
```
import numpy as np
import pandas as pd
import seaborn as sns
df = sns.load_dataset('titanic')
df.head()
```
Using df['cnt_class_town'] = df.groupby(['class', 'embark_town']).transform('size') we can directly get our desired feature in the data frame.

Again, if you want to create any sort of binned features based on the quantiles, usually first you would create a function and then use pandas apply to add that bucket to your data. Here again, you can directly use qcut functionality from pandas, pandas.qcut(x, q, labels=None, retbins=False, precision=3, duplicates='raise') to create the buckets in just one line of code.

Let’s take an example where we want to bin the age column into 4 categories, we can do so by running this one line of code –

df['age_bucket'] = pd.qcut(df['age'], q = [0,0.25,0.5,0.75, 1], labels = ["A", "B", "C", "D"])

Do note that the labels have to be 1 less than your quantiles (q). The explanation as to why I have explained in the Youtube video (see above).

Hopefully, this clears up some pandas concepts and lets you write faster and neater code.
January 24, 2023