Subarray with Given Sum

You are given an array of numbers (non-negative). Find a continuous subarray of the list which adds up to a given sum.

import jovian

jovian.commit()

window.require && require(["base/js/namespace"],function(Jupyter){Jupyter.notebook.save_checkpoint()})

[jovian] Attempting to save notebook..

Minimum Edit Distance

The following interview was asked during a coding interview at Google:

Given two strings A and B, find the minimum number of steps required to convert A to B. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word:

Insert a character

Delete a character

Replace a character

Here's a visual representation (source: iDeserve)

# Solve the problem here

# Test the solution here

import jovian

jovian.commit()

window.require && require(["base/js/namespace"],function(Jupyter){Jupyter.notebook.save_checkpoint()})

[jovian] Attempting to save notebook..

Brute force (recursion - exponential):

def min_edit_distance(str1, str2, i1=0, i2=0):
    if i1 == len(str1):
        return len(str2) - i2
    if i2 == len(str2):
        return len(str1) - i1
    if str1[i1] == str2[i2]:
        return min_edit_distance(str1, str2, i1+1, i2+1)
    return 1 + min(min_edit_distance(str1, str2, i1, i2+1), # Insert at beginning of str1
                   min_edit_distance(str1, str2, i1+1, i2), # Remove from beginning of str1
                   min_edit_distance(str1, str2, i1+1, i2+1)) # Swap first character of str1

min_edit_distance('wednesday', 'thursday')

min_edit_distance('intention', 'execution')

Improved (memoization - $O(n_1*n_2)$):

def min_edit_distance2(str1, str2):
    memo = {}
    def recurse(i1, i2):
        key = (i1, i2)
        if key in memo:
            return memo[key]
        elif i1 == len(str1):
            memo[key] = len(str2) - i2
        elif i2 == len(str2):
            memo[key] = len(str1) - i1
        elif str1[i1] == str2[i2]:
            memo[key] = recurse(i1+1, i2+1)
        else:
            memo[key] = 1 + min(recurse(i1, i2+1), 
                                recurse(i1+1, i2), 
                                recurse(i1+1, i2+1))
        return memo[key]
    return recurse(0, 0)

min_edit_distance2('intention', 'execution')

Best (Dynamic programming - $O(n_1*n_2)$):

# left as an exercise