Category Archives: Strings

Greedy Algorithm, Interview Questions, Strings

Decimal to Roman Numerals (Leetcode)

A sequel to our previous effort, this time going the other way. That the greedy algorithm works here is not too surprising, but maybe there’s a way of concocting a variant of roman numerals where the greedy algorithm wouldn’t work? It’s basically the change-making algorithm. That it works is intuitive, perhaps, but it feels a bit unstable. If somehow we had to do something like this for production, I’d want to really spend out the time characterizing exactly why this works—why we can recast the whole subtractive thing as just a pile of coins. It’s sort of interesting, I guess…

def trySingleString(num, result, symbol, amount):
    if num >= amount:
        return num - amount, result + symbol
    return num, result


def tryRepeatedString(num, result, symbol, amount):
    while True:
        num2, result2 = trySingleString(num, result, symbol, amount)
        if num2 == num:
            return num, result
        num, result = num2, result2


class Solution:
    def intToRoman(self, num: int) -> str:
        assert num >= 0
        result = ""
        num, result = tryRepeatedString(num, result, "M", 1000)
        num, result = tryRepeatedString(num, result, "CM", 900)
        num, result = tryRepeatedString(num, result, "D", 500)
        num, result = tryRepeatedString(num, result, "CD", 400)
        num, result = tryRepeatedString(num, result, "C", 100)
        num, result = tryRepeatedString(num, result, "XC", 90)
        num, result = tryRepeatedString(num, result, "L", 50)
        num, result = tryRepeatedString(num, result, "XL", 40)
        num, result = tryRepeatedString(num, result, "X", 10)
        num, result = tryRepeatedString(num, result, "IX", 9)
        num, result = tryRepeatedString(num, result, "V", 5)
        num, result = tryRepeatedString(num, result, "IV", 4)
        num, result = tryRepeatedString(num, result, "I", 1)
        return result
Interview Questions, Introductory, Strings

Roman Numerals to Decimal (Leetcode)

This is apparently a popular question. It seems OK, it’s very easy. I think I already knew the rule of subtraction. I suppose questions that prompt the learner to consider “doing the work” of writing out a map is nice.

Maybe there’s something to it with the loop being backwards. What if I did it forwards? Seems like it’d end up in the same place: the condition in the if statement would be a bit different, that’s all.

MAP = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}

class Solution:
    def romanToInt(self, s: str) -> int:
        val = 0
        prevC = None
        for c in reversed(s):
            if prevC is not None and MAP[c] < MAP[prevC]:
                val -= MAP[c]
            else:
                val += MAP[c]
            prevC = c
        return val
Interview Questions, Strings

Unique Morse Code Words (Leetcode)

Another from the archives. I had too much fun with this python approach. A nice introductory string question.

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        mapping = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        def mapIndex(c):
            return ord(c) - ord('a')
        def mapWord(w):
            return ''.join(map(lambda c: mapping[mapIndex(c)], w))
        return len(set(list(map(mapWord, words))))

This is a fine introductory interview question. The exact motivation isn’t great, but “process this data and count unique ones” is fine. More strings — a popular request from my students — here.

Interview Questions, Strings

Longest Substring Without Repeating Characters (Leetcode)

Another from the archives. In my old notes I tried a few different approaches. Ultimately this one feels a little “brute-force-y”, here is what I got:

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            for (int l = std::max(res, 1); l + i <= s.size(); l++) {
                std::bitset<256> seen;
                bool bad = false;
                for (int j = i; j < i + l; j++) {
                    if (seen.test(s[j])) {
                        bad = true;
                        break;
                    }
                    seen.set(s[j]);
                }
                if (!bad) {
                    res = std::max(res, l);
                } else {
                    // i i our starting point, a longer l won't help here.
                    break;
                }
            }
        }
        return res;
    }
};

Thoughts

  1. The “length” iteration (how i, l, j indexes interact) is pretty interesting. Comes up rarely, but in thinking about many collections of substrings.
  2. The final “break” (with the comment above it) is necessary.
  3. I wanted to port this to Python—my old archives are in C++. But it lacks a bitset class, and its range loops aren’t amenable to the length-based iteration (or at least, I don’t know how to adapt them).

I doubt my solution is the right one. What is the official Leetcode solution? Oh I like it! Does this make the cut as an interview question? I don’t know, I am skeptical. More string questions here.

Interview Questions, Strings

To Lower Case (Leetcode)

From the archives. A challenge with this is (I think?) Javascript overloads their tolower equivalent to take either strings or characters. This is more testing familiarity with language features (do you do this, or do you use ASCII tables — which I guess isn’t unicode-friendly — or something else?) than anything else. Not a terrible question, just a correct answer doesn’t say much about the candidate/student.

class Solution {
public:
    string toLowerCase(string str) {
        string v;
        for (auto&& c : str) {
            v.push_back(std::tolower(c));
        }
        return v;
        // Maybe this is an excuse for some sanity checking, as well as destroying the input parameter,
        // etc.
    }
};

Nevertheless, it’s a string question, so it lives here.

Interview Questions, Strings

Jewels and Stones (Leetcode)

The hardest part of this question for me was the phrasing. However, I do sort of like this question: hopefully the student will realize they need to repeatedly check the string (set) of jewels, as they iterate over their stones. I don’t know how I feel about the fact that we’re using strings as sets, basically. It does happen in the real world.

Again, from the archives. This is me having too much fun with C++-isms. You can see my inline notes about other approaches.

class Solution {
public:
    int numJewelsInStones(string J, string S) {
        // let's do this very simply, no helper objects.
        int jewelCount = 0;
        for (auto&& stone : S) {
            if (std::find(std::begin(J), std::end(J), stone) != std::end(J))
            {
                jewelCount++;
            }
        }
        // We can do lots of things, really. We should cache J into a set, perhaps, and
        // then can just do a fancier std::algorithms (for_each) sort of thing, if that
        // strikes our fancy. filter etc.
        return jewelCount;
    }
};

We may even be able to collapse the outer for-loop into a count_if call or something… but that’s probably too clever. Who knows.

I guess this is a strings question? Even though it’s really treating strings as a set.

Interview Questions, Strings

Isomorphic Strings (Leetcode 28)

I like this one a lot! Also from the archives. This one is listed as easy, I would say it’s on the harder side of easy. The word “isomorphism” is a bit gnarly, but you can ignore that. I’d rather this be introduced as a Caesar cipher, but maybe that’s also confusing, or makes the possible answer too clear. But if the question is “are you comfortable talking about isomorphism”, well, that’s not a very good question. So I suppose I’d phrase this as a Caesar cipher.

The interesting challenge is, well, distinguish an isomorphism from a homomorphism. Vaguely, the idea of distinguishing this “uniqueness” (invertibility) property is nice. Maybe to enable something like dictionary encoding? I’m trying to brainstorm how to motivate this question and give it some application-justification. In any case…

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # Easy cases
        if len(s) != len(t):
            return False
        
        mapping = {}
        mapped = set([])
        for i in range(len(s)):
            sc = s[i]
            tc = t[i]
            if sc in mapping:
                if mapping[sc] != tc:
                    return False
            elif tc in mapped:
                # uniqueness condition
                return False
            else:
                mapping[sc] = tc
                mapped.add(tc)
        return True
Interview Questions, Strings

Group Anagrams (Leetcode 27)

Another from the archive. This is a nice warm-up or introductory interview question. It is a bit contrived, but I think it exercises a few common tools you’d want to use. You want to group things together that share a common property, and so you want to compare the property but group the things-actual.

Here I use defaultdict, but that’s just out of convenience. I don’t like how to create a sorted string in Python, I wonder if there’s a better way.

from collections import defaultdict
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        
        d = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            d[key].append(s)
            
        res = []
        for k in d:
            res.append(d[k])
        return res
Interview Questions, Strings

Highest-Scoring Word (Code Wars 10)

Leave a comment

Map letters to numbers, map words to a “score” (presumably defined by the sum of numbers from the per-letter mapping), find the highest-scoring word.

I actually like this one a lot as a set of loop exercises. It’s sort of a couple compound ones. Solution is “merely” an exercise in being fluent in loop writing. It’s a very nice junior test, I think.

def high(x):
    score_map = {}
    for i, letter in enumerate("abcdefghijklmnopqrstuvwxyz"):
        score_map[letter] = i + 1
    def score(w):
        return sum([score_map[c] for c in w])
    words = x.split(' ')
    
    maxScore = 0
    maxWord = ""
    
    for w in words:
        if score(w) > maxScore:
            maxScore = score(w)
            maxWord = w
            
    return maxWord

Strings are a popular topic for practice interviews for newcomers to the field. I list the string questions here.

Interview Questions, Strings

Replace with Alphabet Position (Code Wars 7)

Leave a comment

An interesting application of maps (or transforms?) or something.

I think it’s always interesting when a question motivates some precomputed data. In this case we want to encode, well, the alphabet. Other examples are various bit-manipulation stuff, or Roman numeral stuff, and probably many more. Otherwise we’re doing a pretty straightforward mapping. A “normal” for loop this time.

def alphabet_position(text):
    # This can all be computed statically,
    # compute it dynamically for now
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    alphabetPositions = {}
    for i in range(len(alphabet)):
        alphabetPositions[alphabet[i]] = str(i+1)
    
    result = []
    for s in text:
        s = s.lower()
        if s in alphabetPositions:
            result.append(alphabetPositions[s])
    return " ".join(result)

No real interesting notes for this one, I’m afraid. A few little bits of trickiness with types (see the str on line 7), off-by-ones (also on line 7), and some comfort with joins and other tricks. Oh, and lower().

I suppose it’s a nice exercise on building and using a map. Yes, I like that, that’s true. Overall I’d say it’s a string-related question, and other string questions can be found here.