First bad Version

Problem description:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution:

This is solved using binary search since we can see the list of versions as an array of 0’s and 1’s in sorted order having zeroes as good versions and ones as bad versions, so our task is to find the first occurrence of 1, so how can we find the first occurrence of a number on a sorted array?… Binary search!!
So we basically…

1.- Create to pointers, one pointing to the beginning of the list (start = 0) and another one to the end of the list (end = n)
1.- Check if the middle element (middle = start + end / 2) is a correct version
2.- If it is a correct version we now know we don’t need the second half of the list so we go left (end = middle-1), otherwise we go right (start = middle+1)
3.- Repeat steps 1 and 2 until there is no more elements to check (while start <= end)

    def firstBadVersion(self, n):
        start = 1
        end = n
        middle = 0
        
        while(start <= end):
            middle = (start + end) / 2
            if isBadVersion(middle):
                end = middle - 1
            else:
                start = middle + 1
                
        if isBadVersion(middle):
            return middle
        else:
            return middle + 1

Runtime complexity: O(log n) since we cut the array in half at every step, so for an array of size 10 we just need log(10) = 3 operations to find the first bad version 🙂

Number of distinct binary trees

Problem statement:

Given n nodes, how many binary trees can be formed?

example.

for n = 3 there are 5 different binary trees that can be formed:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Solution:

If we have n nodes 1, 2, 3, …, n we know that in some point every node is gonna be the root, and we also know that every node has two sub-trees, the left sub-tree and the right sub-tree, the key here is RECURSION, we can split this problem into different sub problems, let’s see it with an example:

for n = 1 we have ONE possible tree.
for n = 2 we have TWO possible trees:

   1         1 
    \       /  
     2     2

for n = 3 we have the following options:
A) zero nodes at the left sub-tree and two nodes at the right sub-tree
B) one node at left and one node at right
C) zero nodes at the right sub-tree and two nodes at the left sub-tree

          root                     root                      root
         /    \                  /       \                 /     \
numTrees(0)  numTrees(2)   numTrees(1) numTrees(1)  numTrees(2) numTrees(0)
    1      *     2       +      1     *    1      +     2      *    1       =   5 different trees

So it’s clear we are going to solve this problem recursively:

def numTrees(self, n):
    if n <= 1:
        return 1
    res = 0
    for i in range(n):
        res += self.numTrees(i) * self.numTrees(n - i - 1)
    return res

Edit Distance

Problem description:

Given two strings A and B, find the minimum number of operations needed to transform A into B, there are only three valid operations:

-Replace a character
-Delete a character
-Insert a character

Examples:

A = “hello”
B = “hola”
result = 3, the operations were:
1.- replace ‘e’ with ‘o’   -> “hollo”
2.- replace ‘l’ with ‘a’   -> “holao”
3.- remove ‘o’             -> “hola”

Solution:

So for this problem we have two strings A and B, let’s work with the following example:

A = "abc"
     i
B = "cba"
     j

Remember that we want to transform A into B, any operation has to be done over A.

We are gonna use indexes i and j to loop through the strings and compare them character by character so that at every step we have the following options:

First index i and index j are both at position 0, so we have ‘a’ and ‘c’, since they are different we have three options here:
1.- remove ‘a’ (i + 1,  j)               -> “bc”
2.- insert ‘c’ into A (i, j + 1)         -> “cabc”
3.- replace ‘a’ with ‘c’ (i + 1, j + 1) -> “cbc”

Why don’t we just try them all?

int minDistance(String word1, String word2) {
    int dp[][] = new int[word1.length() + 1][word2.length() + 1];
    for(int i = 0; i <= word1.length(); ++i)
        for(int j = 0; j <= word2.length(); ++j)
            dp[i][j] = -1;
    return getDistance(word1, word2, word1.length(), word2.length(), dp);
}
int getDistance(String word1, String word2, int i, int j, int [][]dp) {
    if(i == 0) return j;
    if(j == 0) return i;
    if(dp[i][j] >= 0) return dp[i][j];

    if(word1.charAt(i - 1) == word2.charAt(j - 1))
        return dp[i][j] = getDistance(word1, word2, i - 1, j - 1, dp);
    else
        return dp[i][j] = 1 + Math.min(getDistance(word1, word2, i - 1, j - 1, dp),
        Math.min(getDistance(word1, word2, i - 1, j, dp), getDistance(word1, word2, i, j - 1, dp)));
 }

The dp table is very important in this problem, it is used to avoid a sub task to be computed more than once, otherwise our program would run very very slow.