Monthly Archives: February 2022

Interview Questions

RLE compress string (Leetcode 19)

OK, a sequel!

I like:

  1. We have two views of the same array.
  2. We can start at 1 in the for-loop
  3. Opportunity for invariants to help our loop-based reasoning.
  4. Things get much simpler with the helper function (i.e., I made a lot of bugs until I decided to use a helper function).

I don’t think I’m biased to say this one requires a bit of careful thought!

class Solution(object):
    def commitLetter(self, chars, c, i, count):
        assert(count > 0)
        chars[i] = c
        i += 1
        if count > 1:
            w = str(count)
            for t in w:
                chars[i] = t
                i += 1
        return i
            
    def compress(self, chars):
        if len(chars) == 0: return []
        
        count = 1
        j = 0
        lastChar = chars[0]
        
        for i in range(1, len(chars)):
            if chars[i] == lastChar:
                count += 1
            else:
                j = self.commitLetter(chars, lastChar, j, count)
                lastChar = chars[i]
                count = 1
        j = self.commitLetter(chars, lastChar, j, count)
        return j
Interview Questions

Decompress RLE (Leetcode 18)

Another experiment: can leetcode-esque problems provide a useful way to learn computer science topics?

This problem is about run-length-encoding. Still pretty algorithmic, but a bit more applied. Though, as I did it, it really did feel more like understanding the description more than solving the problem. On the other hand, I think this is a great “fundamentals” problem.

class Solution(object):
    def decompressRLElist(self, nums):
        res = []
        for i in range(0, len(nums), 2):
            freq = nums[i]
            val = nums[i+1]
            res += freq*[val]
        return res