Tag Archives: Codewars

Highest-Scoring Word (Code Wars 10)

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.

Find the halfway point (Code Wars 9)

This one, actually called “Equal sides of an array” threw me for a loop because I hadn’t realized we were excluding the i-th element for each possible index where we would try splitting the array. That induces some off-by-one-ish errors, which is the main interesting part.

This is a nice first approach, and it gets the goal:

def find_even_index(arr):
    if len(arr) == 0: return True
    for i in range(len(arr)):
        if sum(arr[:i]) == sum(arr[i+1:]):
            return i
    return -1

The slices-and-sums can be helper functions.

The natural sequel is to not repeat the addition so many times (so, what’s the runtime complexity of the first solution?). That requires some careful thinking and avoiding off-by-one errors.

def find_even_index(arr):
    if len(arr) == 0: return True
    leftSum = 0
    rightSum = sum(arr[1:])
    if leftSum == rightSum:
        return 0
    for i in range(1, len(arr)):
        leftSum += arr[i-1]
        rightSum -= arr[i]
        if leftSum == rightSum:
            return i
    return -1

Take-Aways

This problem seems to hit a lot of right notes: It’s approachable, it has trickiness that requires careful debugging thought, it has plausible applicability (partitioning resources evenly), and keeps the door open to optimizations. Nice! For this and other array questions, I collect them here.

Is This Number Prime (Code Wars 8)

Primality is a math-y topic. Sure, let’s implement the naive definition of what a prime number is. Excuse to talk about a bit of trivia I know.

Meta-note: not sure what the question-author is getting at with the Wikipedia mention. I don’t know if they’re “trying to make knowledge accessible”, or they don’t realize the limits of Wikipedia. I think that, and their encouragement that “there are no fancy optimizations required, but…” shows that they may have certain assumptions about their audience. Ah well!

Key facts:

  1. n % m == 0 when m divides n. So we can recast the definition of primality as: for our input n, is there such an m such that n%m==0? I would venture that this is the “trivial” solution the author was thinking of.
  2. A subtle complication is that n can be very big. Counting up to n may actually take a long time, even though the data itself is very small. If n were 100 digits, for instance, we’d just never finish. Fortunately, we’re not in that scenario.
  3. Cute trick: say that n is not prime. So there must be some a*b=n. Try to convince yourself that one of a or b must be less than the square root of n, or a and b are the square root of n. Turning that around: if there’s some number that divides n, it will be found between 2 and sqrt(n). This is a much shorter loop (still a big loop!) to get through. It gets us across the finish-line, here.
import math
def is_prime(num):
    if num < 2: return False
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0: return False
    return True

Closing Notes

I’m not a big fan of using numerical questions for interview questions. Obviously if it comes up in the work etc. etc., but these sort of questions seem more “targeted” (you either know the right approach or you don’t). This one is an interesting way to present the unintuitive fact that even though your input is “only” one number, your loop can run for a really long time! n, for O(n), is the number of values between 0 and num, which is exponential in the length of n. For the times I do other numerical questions, I’d list them here.

Replace with Alphabet Position (Code Wars 7)

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.

Pairify Strings (Code Wars 6)

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.

Is it a triangle? (Code Wars 5)

Given 3 integers, can there be a triangle with edges equal to those lengths?

I have never encountered even the tiniest of geometric questions in my professional career. On the other hand, many people have worked in graphics and games, where geometric reasoning (presumably) matters a lot. As it happens, even my stunted geometric reasoning was able to handle this question. I think it’ll be a nice exercise on a whiteboard as a general sort of problem-solving measurement, but I don’t see how it says much about the interviewee’s actual software-development capabilities.

Ultimately, what the question is asking for is a list of constraints. If those constraints are all satisfied, then there can exist a triangle with edge-lengths a, b, c. If those constraints aren’t satisfied, then there isn’t.

Finding Constraints

So we have to determine those constraints. What are those constraints? The way I think about them is that I imagine the constraints are true for (a, b, c) so I ask myself something like: “if a, b, c from a triangle (so to speak), and a is really big (relative to b and c), what does b and c look like?”

Sketching out that question on paper, it seems that the “larger” a gets relative to b and c, the “flatter” the triangle has to be. Turning it around, b and c together are always going to be a bit bigger than a. So can hypothesize: “a < b + c”, and pretty quickly establish analogous constraints with the other 2 edges.

So that’s a nice constraint! We can play around with the opposite: say a is 100, and b and c are both 2. It seems pretty clear that b and c won’t be able to touch each other, when placed on either end of a. So that’s reassuring.

Looking at the constraint we have, we have what’s called an “upper bound” on a. We know that the size of a can only get so big before it breaks the rules. Can we go the other way? If we know b and c, does a have to be a certain length? Intuitively, we can imagine a sort of arm or hinge, where one edge is b, the other c. Say c=b/2. Clearly, even if we close the hinge entirely, the end of c is pretty far away from the other end of b. It suggests that the length of a must be at least the difference between c and b, or a > b – c.

Do fun arithmetic, and those are the same constraints as we determined above, just with a sign change. Is this a real proof? Not in my opinion. But at this point I have intuitive arguments that shows the 3 constraints we determined (a<b+c,b<a+c,c<a+b) effectively both upper-and-lower bound the value of each a, b, c, so I got confident enough to hit the go button. Hey, it passed all the tests.

Here are those constraints, plus an edge case handler, written down:

def is_triangle(a, b, c):
    if a < 0 or b < 0 or c < 0:
        return False
    b1 = a + b > c
    b2 = a + c > b
    b3 = b + c > a
    return b1 and b2 and b3

Should I have included pictures explaining my reasoning in this post? Almost certainly yes.

I don’t often explore geometric problems, and I don’t think their a focus for my students, but as more come up the solutions will be found here.

Valid Parentheses (Leetcode 1)

It’s a classic problem: given a string of parentheses, determine if they’re properly nested. The complication here is that, instead of just 1 kind of parens, we have 3 to deal with. This same problem can be found on codewars.

This is often presented as an exercise where the “solution” is to realize that a stack works perfectly for this scenario. What else can we learn from this?

Opportunities for Learning

  1. Helper functions! The flip here is pretty useful and helps makes the different cases we want to deal with clearer.
  2. Dealing with cases! This is an interesting question because we have a lot of branches inside the loop. Usually that’s not so.
  3. An extension of that is thinking about loop invariants. What are all the different cases we can expect in our loop, and what do we want to maintain? For instance, it’s important not to push on close-parens (we’re not just pushing on every character we see, the invariants we want to maintain aren’t quite that).
  4. I like the “tail” condition. We’re not just done at the end of the loop, we have to make sure we’ve matched all our open parens.

Something I’m not so excited about with this question is that, as I’ve seen, it invites a lot of complicated experiments. People seem inclined to try very “stateful” approaches (build up a complicated analysis of the string, start doing some kind of weird tree-ish thing). It seems a lot of the neat-ness of this question is from realizing that you may tempted to have a very sophisticated amount of state, but you “just” need a stack. It’s very gratifying to make those realizations, and can be very valuable for professional software development… but is answering this a useful signal?

class Solution:
    def flip(self, c):
        if c == '}': return '{'
        if c == ')': return '('
        if c == ']': return '['
        assert(False)
        
    def isValid(self, s: str) -> bool:
        stack = []
        for c in s:
            if c in {'(', '[', '{'}:
                stack.append(c)
                continue
            elif len(stack) == 0:
                return False
            elif self.flip(c) == stack[-1]:
                stack.pop()
            else:
                return False
        return len(stack) == 0

It’s a bit difficult to categorize this problem. On the one hand the input is a string, but the intended solution uses a stack. As I think the string-edness is more arbitrary, I would categorize this as a stack-based question, even though that speaks more to the solution than the nature of the problem. Here is where any other stack questions will end up.

Tribonacci (Code Wars 4)

Let’s compute the complete Tribonacci (riff off of “Fibonacci”) sequence.

It’s worth a few minutes understanding and “visualizing” what the solution might look like. In this case, I just mean that we’re going to be returning a list. Moreover, (most of) the elements in that list are computed by prior elements in that list. The list is going to be n elements long (the same n as is a parameter to our function).

One of my favorite exercises: dealing with the edge/easy cases.

  1. If n is 0, we can return the empty list.
  2. If n is less than or equal to the number of elements in signature, we can just return that appropriate subsequence.
  3. Otherwise, we already have enough elements in signature to compute all the other elements we need.

And that’s the answer:

def tribonacci(signature, n):
    if n == 0:
        return []
    if n <= len(signature):
        return signature[:n]
    result = signature[:]
    for i in range(3, n):
        s = result[i-1]+result[i-2]+result[i-3]
        result.append(s)
    return result

Additional Thoughts

  1. The slice on line 5 may not be available in all languages; it will just be more verbose, if slicing isn’t available, with the spirit being the same.
  2. I think sometimes we’re returning a shallow copy (line 5), otherwise a deep copy. Probably not ideal. I wouldn’t let this pass code-review.
  3. We often have for loops that go over an array of length n. Here we’re creating an array of length n. That’s a fun contrast.
  4. This sort of algorithm, where we build the contents of the list based off of previous elements, hasn’t come up very often in my professional experiences. I suppose it’s neat to see what that kind of code looks like, though I think it doesn’t add much versus other, more applicable loop questions.

I’d categorize this question as one in the “recursion” topic. You can find all such questions on this site here.

Displaying Sum in Binary (Code Wars 3)

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!

Capitalizing Words (Code Wars 2)

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.