All posts by Aaron

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.

Bit Manipulation, Interview Questions

Bit Counting (Code Wars 1)

1 Comment

Sometimes it can be useful to think about numbers as an array of bits. This question asks us to consider a number in that way, and then count the number of elements in that array that are “1”. The link.

The first key realization is really considering how a number is an array-of-bits. That has a lot of follow-on implications. In particular, it suggests that maybe we can write code like the following:

def count_bits(n):
    counter = 0
    for bit in n:
        if bit == 1:
            counter += 1
    return counter

This code is a solution! We would count all the bits that are 1. The issue is that key line, “for bit in n“, doesn’t really exist. How might we address this? Fortunately, I’ve seen this problem many times, or similar-enough ones, and I’ll present a solution and discuss it.

def count_bits(n):
    counter = 0
    while n > 1:
        if n % 2 == 1:
            counter += 1
        n = int(n/2)
    return counter

That was quick!

Approach

  1. The if on line 4 of our solution is essentially testing the least-significant bit in n. So in that way we can look at a single bit in n, and emulate the condition in our “ideal” loop.
  2. The n = int(n/2) on line 6 essentially chops off the last binary digit of n. Just as dividing a normal number by 10 (and rounding down) has the effect of trimming off the last decimal digit of a number, so too does dividing by 2 and rounding down trim off the last binary digit (i.e., the last bit) of the number.
  3. That “trimming” gives us the effect of iterating through every bit of n, accessing that bit with the modulo (%) operator. In this way we can see if the rightmost bit is 1 or 0 (again, using the if statement mentioned in point 1.)

Bit-related questions don’t come up too often, but the “trick” we have here to iterate through a number as a sequence of bits is a useful staple in these bitwise questions. All bit manipulation questions so far on the sight should be collected here.