One more fairly standard tech interview problem (for better or for worse, you’re likely to see one of these if you go for a programming job):

Given a linked list and an element x. Partition the list so that all elements less than x are before elements greater than or equal to x, but do not otherwise change the order of the elements.

read more...

Another LeetCode problem.

Given an MxN matrix of numbers, find the longest path of strictly increasing numbers.

So for example in this matrix:

You can start with the 1 in the bottom center, go left to the two, then up to the 6, and 9. That’s the longest path, so return a 4.

In this 3x3 case, it’s really easy to just brute force. Calculate all possible paths. An upper bound would be visiting every node exactly once, so \sum_{i=1}^9 \binom{9}{i} = 511 (choose n elements for each of 1 to 9 cases). Not so bad. But if you have a 10x10 matrix, that’s already 1e30–which is freaking gigantic. So we need to do better.

read more...

Okay, let’s take this one step further. Rather than generating just phone words, let’s actually generate phone words. Someone has provided a list of words in English as a package, so we’ll add a filter to add that to our comprehension:

from english_words import english_words_set

def letterCombinations(self, digits: str) -> List[str]:
    if not digits:
        return []

    letters = {
        '1': '',
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
        '0': ' ',
    }

    return [
        word
        for product in itertools.product(*[
            letters[digit] for digit in digits
        ])
        if ((word := ''.join(product)) in english_word_set)
    ]

I think I like the Walrus/assignment operator (:=), but it still is a bit bizarre at times. Basically, what it does is assign a call to a value (word = ''.join(product) in this case), but also returns it and can be used as an expression, which = cannot. So we can immediately check if it is in english_words. Since that’s a set, it should be pretty fast.

read more...

Working through a few problems on LeetCode. I haven’t quite decided what I think of the site, but it’s a fun way to play with simple algorithms. Figured I might as well write up any I find interesting.

First interesting problem:

Given a standard lettered keypad, generate all words from a given phone number.

read more...