All posts by Aaron

Geometric, Interview Questions

Is it a triangle? (Code Wars 5)

Leave a comment

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.

Interview Questions, Stack

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.

Interview Questions, Recursion

Tribonacci (Code Wars 4)

1 Comment

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.

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.

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.