Tag Archives: strings

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.

Interview Questions, Strings

Pairify Strings (Code Wars 6)

Leave a comment

This one’s a quick exercise in slices, if you’re comfortable with those in Python. I like that (to me) the solution suggests an interesting loop, one that isn’t a ready for-loop.

It also suggests an interesting question of memory usage, maybe. What’s going on with s, and how is it shrinking (or not?). Are we changing the original input string? Other sort of “basic” questions that may test the applicant’s familiarity with runtime environments.

def solution(s):
    res = []
    while len(s) > 1:
        p, s = s[:2], s[2:]
        res.append(p)
    if len(s) == 1:
        res.append(s+'_')
    return res

Would be curious to see this without slices. I like this, though, that it motivates slices and an “interesting” for loop. More exercises on strings can be found here.

Real-World Application

I don’t think there’s a ready real-world application for this. However, taking a single stream of data, and digesting it into smaller chunks and feeding those into a later collection: that happens all the time. I think the skills exercised by this particular problem are pretty tactical (slices, for-loop wrangling) but the discussion about resource usage or other larger design questions can invite consideration of real-world analogs.

Bit Manipulation, Interview Questions

Displaying Sum in Binary (Code Wars 3)

1 Comment

Here is the next codewars problem. It’s a bit strange: you get two “normal” numbers, and then you need to return their sum as a binary string. Adding two numbers is pretty straightforward in this case: you use the +, to be humorous about this.

Already you can see we have another case of bitwise manipulation! We can use the same trick, again, to iterate through all the bits in our sum and add them to a string.

I had a bug! First, here is the (validated) solution:

def add_binary(a,b):
    assert(a >= 0 and b >= 0)
    s = a + b
    result = []
    while s > 0:
        oldS = s
        result.append(str(s % 2))
        s = s // 2
    result = ''.join(reversed(result))
    return result

Let’s focus on the positives.

  1. The assert on line 2 is my own sanity-checking. Things can get funny in this question if a or b can be negative.
  2. You can barely see where the sum happens in this question: line 3. After that, you can see we completely ignore a, b.
  3. This has a fun combination of the previous 2 questions we talked about. We build up our string as a list of strings (each element in that list is either the string “0” or “1”) and join that list over the empty string. Just as we saw ‘ ‘.join(…) in the previous question, how it combined all the elements into a string, separating each element by ‘ ‘, this combines all elements in our list as a string, separated by ”, i.e., separated by nothing.
  4. We determine the “next” bit of s with s % 2, just like before. A big change (and this is where the bug is) is on line 8. Previously, we did s = int(s/2), and my initial implementation had that as well. In tests with extremely large integers, that method failed. Let’s discussion why.

The Bug

This is a somewhat advanced bug. Truth be told, if a beginner programmer (esp. from a bootcamp) hit this issue, I’m not sure if they’d have the context to address it. Here’s what happens:

  1. Python distinguishes between integers, which are whole numbers, and floats, which are numbers that can have a decimal point. Adding two integers always gives you the answer you’d expect, so integers are simple. Floating point numbers ultimately have to round (similar to how, with 0.333333333…, eventually you have to decide when to stop writing 3s!).
  2. In our code, s is an integer, except when it’s being divided by 2. Python will automatically convert it into a float. That is why we immediately turn it back into an integer, with int(s/2). This gives the effect of “chopping off” anything after the decimal point, which is what we want. (We’d expect the decimal to either be .0, when s was previously even, or 0.5, when s was previously odd.)
  3. However, that rounding that we have to do with floating-point-numbers doesn’t just happen after the decimal point. For very large numbers, the rounding can happen in the thousandth’s place, or similar (so rather than a big number ending with 124,325.0, it would look like 124,000.0). This truncation is too aggressive!
  4. So the bug manifested that we were outputting a binary number with just a long string of 0s at the end, when it should have been a mix of 0s and 1s.
  5. The fix was me searching around online until I found out how to do truncating-integer-division in Python. That avoids converting the integer into a double, and therefore we never introduce that inadvertent rounding, and we get the right answer!
Interview Questions, Strings

Capitalizing Words (Code Wars 2)

Leave a comment

Here is a small string exercise. The tools it asks the student to exercise are common and worth learning. The teasing nature of the question, however light-hearted, is not something I recommend.

Let’s see if we can iteratively digest a plain-English description of what we want to do into computer code.

Clarified Instructions

  1. We want to capitalize every word in that sentence.
  2. We want to take a sentence, go through every word, capitalize it, and return the result.
  3. Given a sentence, for each word in that sentence, capitalize that word, and return the result.

We can continue to “massage” the description in this way, but I think we’re at a point where we can consider psuedocode.

def to_jaden_case(string):
    result = ""
    for each word in string:
        capWord = capitalized(word)
        result += capWord
    return result

This won’t work, but it gets us closer. What’s missing?

Psuedocode to Real Code

  1. Line 4 isn’t real python. How do we “say” the equivalent of “for each word in string“?
  2. The function capitalized doesn’t exist. What should we do there?
  3. The subtlest issue is that we are adding words back into result, but we aren’t adding any whitespace. As it’s written this suggests our result will be like HowCanMirrors…, which is not right.

We can address each of these in turn.

  1. A very common string method is to split a string, or sometimes it’s called tokenizing a string. It breaks a string up into an array of strings, usually over whitespace. So, we can write “for word in string.split()”, and that’ll be what we want!
  2. We can write the function capitalized! Languages typically provide a way of capitalizing a single character. How to build or change strings varies a lot based on language, so that can vary, but in a human-conversation interview I think it’d be reasonable to leave that as an unimplemented helper function (at least, lower-to-upper for a single character).
  3. Lastly, there are a few options to recombine the words while still keeping (or regenerating) the right whitespace. I’ll present the one you should hope to use, but you may need to do an old-fashioned one involving lower-level operations like string concatenation.

def capitalized(word):
    word0 = word[0].upper()
    return word0 + word[1:]
def to_jaden_case(string):
    result = []
    for word in string.split():
        result.append(capitalized(word))
    return ' '.join(result)

Conclusion

We changed result from a string in our psuedocode into a list. Why is that? A common string tool is the join method. Just as we split a string into an array of words using split, we can join an array of words back into a string with the join method. The object join is called with, in this case the whitespace string ‘ ‘, is the value that will go between each word.

While this question is very different from the previous one, it has the same skeleton: we iterate through a value (a number, or a string) in a somewhat unusual way (by-bit, by-word), do something with it (add it if it’s 1, capitalize it and add it to our result), and return that sort of “summary” value. This sort of skeleton is extremely common. Some may say the first problem’s solution was very different because it used a while loop. I would disagree!

This question was a nice exercise in lots of useful “vocabulary” for manipulating strings. All the solved string questions on this site are collected here.