DEV Community: Lucas

How to do better on coding interviews

Lucas — Wed, 13 Jan 2021 11:12:45 +0000

tl;dr Warm up before the interview.
This post is a summary of my YouTube video:

Intro

A few years ago I learned a trick: warm up before my coding interviews. I know, it sounds weird. But don't worry, keep reading, it will all make sense (hopefully).

Why warm up

Being the gym lover I am, let's start with gym analogy.

Pretend today is leg day. You come into the gym, grab the bar, load 200KG on it and start squatting. Sounds reasonable? Probably not.

Most likely we would come into the gym and warm up. We'd just do enough exercise to get the blood flowing and our bodies ready for the exercise. So why don't we do the same for coding interviews? Isn't it weird?

We all know coding demands focus. Anyone who's had random ping on Slack or meeting interrupt their flow knows how it feels. It takes time to get back on track.

The same applies to interviews.

Interviewing is inherently hard, not because of the coding challenge, but because of all the other factors involved: time, stress, anxiety, etc. Jumping into an interview cold does you no good. In the best case, it slows you down. In the worst case, it causes you to fail the interview.

Warming up will prime your mind and put yourself in a ready state to come in and crush that interview.

How to warm up

YMMV, but this is what works for me and a few people I know that are pretty good at interviews.

One hour before your interview, start the warm up.

You can use whatever you want: VS Code, LeetCode, pen and paper. Anything that works for you.

Choose 1-3 problems you already know how to solve and start working on them. This is key.

Back to the gym analogy: you don't warm up for squats with a load that leaves you busted and prevents you from doing the actual working sets. You load just enough to get yourself ready for the real thing. That's the goal with the coding warm up.

You choose exercises you already know to avoid wasting energy that can be used for the interview itself. You just need to get those brain juices flowing.

Another reason to stick to a problem you know how to solve is this: if you pick a hard problem and fail at solving it right before your interview, what do you think that's gonna do to your confidence? Probably not much good, right? So don't do it. Stick to what you know for the warm up.

And last, but not least, stop your warm up 15 minutes before the interview starts. Just step away from the computer. Go get some water, use the toilet, or stare at a wall if you have to. Use this time to chill. I like to play some chill music to help me get in the mood. Do this to help control your interview stress (we all get stressed, trust me).

Takeaways

Warm up before your interview so your mind is ready for the coding problems.
Start your warm up 1 hour before the interview.
Choose 1-3 exercises you already know how to solve and get cranking.
Give yourself a 15 minute break before the interview to relax.

That's all

Thank you for reading this far!
If you like this post, let me know on Twitter! I also post videos about this sort of stuff on YouTube, so go check my channel if you haven't yet.

How I got offers from Amazon, Microsoft, and Bloomberg

Lucas — Mon, 04 Jan 2021 09:13:25 +0000

This post is an excerpt of my YouTube video:

Intro

Last year I decided it was time to switch jobs. Interviewing is always a hassle, so I decided to keep track of what worked for me. I'm sharing this in the hopes someone else might benefit from what I've learned.

How I prepared for the phone screens

I kept it simple: LeetCode for practice problems. I didn't aim for an arbitrary number of questions to "be ready".

Practiced each day for a few hours and used space repetition. I'd cover multiple topics each session. That prevented things from getting too boring.

How I prepared for the onsite interviews

Since I had practiced a lot of coding for the phone screens, I put coding in the back-burner.

Instead, I focused on system design and behavioral questions.

For system design, Grokking the System Design Interview was pretty useful. To supplement that, I also watched YouTube videos to see how different people approached different problems.

When it came to behavioral prep, I used Anki flashcards. I went through all of Amazon's leadership principles, researched common behavioral questions, and created the cards with my answers. I also made sure to include any follow ups I could think of to my cards.

This definitely made me memorize my answers.

This might sound like cheating, but the truth is you're not gonna be able to come up with a story on the spot. You'll ramble. You'll forget details. You'll get confused. Interviewing is already stressful enough. Preparing the questions and answers beforehand will give you a leg up.

Why I did all of my interviews in a single week

Onsite interviews usually take 5 hours. Three onsites in a week totals 15 hours. I won't lie, it sucked. I was pretty exhausted after that week. But at the same time, it didn't suck.

Doing all the interviews at once gave me momentum and helped me perform well. It also helped me get it over quickly.

It also gave me a huge advantage: leverage. You see, when you tell companies you already have other onsites, they pay attention. You're suddenly in high demand. That makes them move faster and gives you more power to command a better offer.

This was the first time I scheduled my interviews like this and, trust me, it made a huge difference.

That's all folks

If you've read this far, thank you! I hope this post was useful and showed you one path you can take to prepare for your interviews.

If you liked this post, have a look at my YouTube channel. I post videos every week, discussing tech, career, and productivity!

If you'd like to chat, hit me up on Twitter.

Advent of Code 2020 in Kotlin: Day 05

Lucas — Sat, 05 Dec 2020 16:25:11 +0000

On Day 05 we need to find our seat on the airplane! We must go over and decode a list of boarding passes to find their seat IDs. A boarding pass is just a sequence of 10 characters.

The whole problem revolves around Binary Search. Decoding a boarding pass is composed of two parts: Initially we analyse the first 7 characters to find the correct row; then, we look at the last 3 characters to find the correct column.

When looking for a row or a column, we divide the search space in half after each inspected character.

Since we are not looking for a number specifically, we can use left-most binary search to get the correct index we are looking for.

Let’s dig into the code!

Data representation

I wanted to represent each line in the input file as a BoardingPassobject. The boarding pass would list its row, column, and seat ID:

data class BoardingPass(val row: Int, val column: Int) {
  val seatID: Int
    get() = row * 8 + column
}

Pretty straightforward, isn’t it?

Reading the data

Like on Day 04, I extended the File class to return me a list of BoardingPasses:

fun File.toListOfBoardingPassesOrNull() : List<BoardingPass>? {
  return readLines().map { it.toBoardingPass() }
}

And to convert a line (String) into a BoardingPass:

fun String.toBoardingPass(): BoardingPass {
    // Find the correct column
    var lo = 0
    var hi = 127
    for (i in 0..6) {
    val mid = lo + (hi - lo) / 2

    if (this[i] == 'F') {
        hi = mid
    } else {
        lo = mid + 1
    }
    }

    val row = lo

    // Find the correct row
    lo = 0
    hi = 7
    for (i in 7..9) {
    val mid = lo + (hi - lo) / 2
    if (this[i] == 'L') {
        hi = mid
    } else {
        lo = mid + 1
    }
    }

    val column = lo

    return BoardingPass(row, column)
}

I’m not gonna go over how the binary search above works (check the Wikipedia article for that). All we do here is iterate over the characters in the boarding pass and extract the row and column. We then return a BoardingPass object with those values.

Part 1: Get the max seat ID in the list of boarding passes

Pretty easy this one:

fun main() {
  print(File("input.txt").toListOfBoardingPassesOrNull()?.map { it.seatID }?.maxOrNull())
}

We read the boarding passes, get the seat ID for each one of them and then select the one with maximum value.

Part 2: Find our own seat ID

The question tells us that our boarding pass is the only one missing in the input, and that the seats immediately before and after ours are taken.

We just must find the empty seat.

One way to do this might be to sort the list of seatIDs and find where there’s a gap of 1. That would give us O(n * log(n)) runtime complexity.

Instead, I decided to use a variation of Counting Sort. We know there will be at most 128 * 8 seats (i.e., 128 rows and 8 columns per row). So I preallocated an array of that size, where each position denotes a seat. Each position in the array has value 0 or 1. Zero means that seat is empty, one means it is taken.

Now we just go over each seat ID we have and mark then as taken in the array. After that, we just iterate over the entire array and find an empty seat between two taken seats. That empty seat is ours.

Here’s what the code looks like:

fun main() {
    val totalSeats = 128 * 8
    val maxSeatID = totalSeats - 1

    // Preallocate array for seats. Zero indicates the seat is emtpy
    val seats = ByteArray(totalSeats) { 0 }

    File("input.txt").toListOfBoardingPassesOrNull()?.map { it.seatID }?.forEach {
    seats[it] = 1
    }

    for (i in 1..maxSeatID-1) {
    // The current seat is empty but the previous and next seats are taken,
    // so that's our seat.
    if (seats[i] == 0.toByte() && seats[i-1] == 1.toByte() && seats[i + 1] == 1.toByte()) {
        print(i)
    }
    }
}

You’ll notice that on the line highlighted I call the toByte method multiple times. That’s necessary due to Kotlin’s limitation. It cannot automatically detect that those literals are of type Byte and there’s no shorthand to cast them. There’s even a ticket on JetBrains’s issue tracker but it doesn’t seem to be going anywhere.

That’s all folks

Today’s puzzle was pretty straightforward. My only surprise was the weirdness about the implicit conversions in Kotlin. Still, I’m happy with my solution.

Let’s see what’s up with day 06 tomorrow!

Advent of Code 2020 in Kotlin: Day 04

Lucas — Fri, 04 Dec 2020 15:39:00 +0000

Day 04 was Advent of Code’s version of Papers, Please. You had to go over a list of passports and validate them. I’m not too happy with how the code turned out, as it’s a bit verbose for my taste. Alas, it’s not terrible.

Data representation

A passport must contain a set of fields and we need to ensure they are present. I created a Passport class with an entry for each of those fields:

data class Passport(
    val byr: Int?,
    val iyr: Int?,
    val eyr: Int?,
    val hgt: String?,
    val hcl: String?,
    val ecl: String?,
    val pid: String?,
    val cid: String?) { }

You’ll see I mark each field as nullable (the ? after the type). I do this is because each passport maybe have missing fields, making them invalid.

To help me construct the Passport objects, I defined a Builder class:

data class Passport(
  ...
) {
    class Builder {
      var byr: Int? = null
      var iyr: Int? = null
      var eyr: Int? = null
      var hgt: String? = null
      var hcl: String? = null
      var ecl: String? = null
      var pid: String? = null
      var cid: String? = null

      fun setField(fieldName: String, fieldValue: String) {
        when (fieldName) {
          "byr" -> byr = fieldValue.toInt()
          "iyr" -> iyr = fieldValue.toInt()
          "eyr" -> eyr = fieldValue.toInt()
          "hgt" -> hgt = fieldValue
          "hcl" -> hcl = fieldValue
          "ecl" -> ecl = fieldValue
          "pid" -> pid = fieldValue
      "cid" -> cid = fieldValue
      }
    }

    fun build() = Passport(
      byr, iyr, eyr,
      hgt, hcl, ecl,
      pid, cid)
    }
}

Reading the data

Like on Day 03, I defined an extension method on the File class. This method returns a nullable list of Passports.

fun File.toPassportListOrNull() : List<Passport>? {
  val result = ArrayList<Passport>()
  var passportBuilder = Passport.Builder()

  forEachLine {
    if (it.isEmpty()) {
      result.add(passportBuilder.build())
      passportBuilder = Passport.Builder()
    } else {
      it.split(" ").forEach {
        val parts = it.split(":")
        passportBuilder.setField(parts[0], parts[1])
      }
    }
  }

  result.add(passportBuilder.build())

  return result
}

Parsing the passports is a bit tricky. The fields might span multiple lines. An empty line marks the end of a passport record. That’s why in the code above I check if the current line is empty to insert the passport in the list.

Counting the valid passports

To check if a passport is valid or not, I just added a new method to the Passport class:

    fun isValid(): Boolean {
    return (
        byr != null &&
        iyr != null &&
        eyr != null &&
        hgt != null &&
        hcl != null &&
        ecl != null &&
        pid != null
    )
    }

The code to actually count the passports is trivial:

fun main() {
  val count = File("input.txt").toPassportListOrNull()?.count { it.isValid() }
  print(count)
}

Part 2

The second part of the problem is nothing special. Before we just had to check if the required fields were present, now we must check if the fields have correct values. That’s easy enough, we just extend the isValidmethod.

    val validEyeColors = setOf("amb", "blu", "brn", "gry", "grn", "hzl", "oth")
    val hairColorRegex = Regex("""#[a-f0-9]{6}""")

    fun validHeight(height: String): Boolean {
    if (height.contains("in")) {
        val value = height.substring(0..height.length - 3).toInt()
        return 50 <= value && value <= 76
    } else if (height.contains("cm")) {
        val value = height.substring(0..height.length - 3).toInt()
        return 150 <= value && value <= 193
    } else {
        return false
    }
    }

    fun isValid(): Boolean {
    return (
        byr != null && byr in 1920..2002 &&
        iyr != null && iyr in 2010..2020 &&
        eyr != null && eyr in 2020..2030 &&
        hgt != null && validHeight(hgt) &&
        hcl != null && hairColorRegex.matches(hcl) &&
        ecl != null && validEyeColors.contains(ecl) &&
        pid != null && pid.length == 9
    )
    }

The validation code is pretty ugly but it gets the job done. The first 3 fields are years, so we just check if they are within a given range.

To validate the height, I created a separate method. Heights can be given either in centimeters or inches. It made sense to have a separate method for that.

Hair color was just a matter of using a regular expression for a HEX color code. Eye color is a set membership check. And the last field, Passport ID (PID), we just check its length.

The end

That’s it for day 4. I’m not exactly happy with this code. I feel like I wrote too much to accomplish too little. I’m sure Kotlin has some facilities that would make writing this code a lot shorter, but I haven’t explored that yet.

Now on to day 05!

Advent of Code 2020 in Kotlin: Day 03

Lucas — Thu, 03 Dec 2020 19:08:31 +0000

Today’s puzzle was a bit more involved than the last two days. The puzzle asks us to write some code to direct a toboggan. We are given a grid that represents the area we have to cross. We start at the top-left position (coordinates (0, 0)) and need to get to the last row and count how many trees we’ve seen along the way. The way we are allowed to move is specified in the question.

Let’s have a look at how I tackled this problem.

Representing the grid

I chose to represent the grid as data class containing three fields: width, height, and cells. Cells is just an array of arrays that represents each coordinate in the grid. If the cell is true, it means there’s a tree there.

data class Grid(val width: Int, val height: Int, val cells: Array<Array<Boolean>>) {}

Loading the grid

I initially implemented this using companion methods, like I did on Day 02. Once I got it working, I saw someone commented on Redditthat using extension methods would be more Kotlin-like. I changed the code and what I did instead was extend the File class with a method to load the grid.

On the one hand, I think the code reads quite nicely this way. On the other hand, I’m not a huge fan of extension methods in this case. It feels wrong to embed this application-specific functionality in the File class.

Here’s what that looks like:

fun File.toGridOrNull(): Grid? {
    val cells =
    readLines().map { line -> line.map { it == '#' }.toTypedArray() }.toTypedArray()

    if (cells.size > 0 && cells[0].size > 0) {
    val height = cells.size
    val width = cells[0].size

    return Grid(width, height, cells)
    }

    return null
}

No magic here. We read all the lines in the file, apply map to them transforming each line into an array of Booleans. We mark the cell as a tree if the character we are looking at is equal to #.

Getting the answer

Now that we’ve loaded the grid into memory, we need to actually find the result.

I started by first extending the Grid class with a couple of methods:

    // Inside the Grid class    
    fun isTree(row: Int, column: Int) = cells[row][column]

    fun countTrees() : Int {
    var currentRow = 0
    var currentColumn = 0

    val verticalStep = 1
    val horizontalStep = 3

    var trees = 0

    while (currentRow < height - 1) {
        currentRow += verticalStep
        currentColumn = (currentColumn + horizontalStep) % width // this ensures we wrap around

        if (isTree(currentRow, currentColumn)) {
        trees++
        }
    }

    return trees
    }

isTree is just a helper method so we can check if a cell is a tree. countTreesis a bit morecomplex: In part 1 of the problem, we always move 3 columns to the right and 1 row down. Those numbers are represented by the horizontalStep and verticalStep variables, respectively. We then iterate until we reach the last row of the grid. At each step, we compute currentColumnusing modulo since the grid wraps around. The tree counter is bumped whenever we find one.

Now our main function looks very simple:

fun main() {
    println(File("input.txt").toGridOrNull()?.countTrees())
}

Part 2

The second part is pretty similar to the first one, but now we are asked to count how many trees we find by moving in different patterns. Once we have the count for each pattern, we multiply all of them and that’s the answer.

When it comes to the Grid class, we only need to make a minor tweak:

    // Inside the Grid classs
    fun countTrees(verticalStep: Int, horizontalStep: Int) : Int {
        var currentRow = 0
        var currentColumn = 0
        var trees = 0

        while (currentRow < height - 1) {
            // ...

All we did was pull the verticalStep and horizontalStep variables out of the body and into the parameter list.

The difference now is that our main function is a lot more complex:

fun main() {
    val grid = File("input.txt").toGridOrNull()

    if (grid != null) {
    val steps = listOf(
        Pair(1, 1),
        Pair(1, 3),
        Pair(1, 5),
        Pair(1, 7),
        Pair(2, 1),
    )

    val treeCounts = steps.map { (verticalStep, horizontalStep) -> grid.countTrees(verticalStep, horizontalStep) }
    val totalTrees = treeCounts.map { it.toBigInteger() }.reduce() { acc, n -> acc * n}

    println(totalTrees)
    }
}

Let’s unpack what is going on here:

Load the grid
If the grid was successfully loaded, create a list with all the movement patterns we need to check (specified in the question).
For each pattern, create count how many trees we find in the grid and put the results in a list.
Multiply all the tree counts.
Print the result.

The code is fairly easy to follow and the points above should help understand what is going on. One thing to notice is the call to toBigInteger(): If we just multiply the numbers as Int, the result overflows (we get a negative number). Kotlin’s Int type is only 32-bits long. To avoid that, we convert each tree count to a BigInteger object.

Thoughts

Today’s puzzle was interesting, in particular because it let me play with a few more things. Like I mentioned above, I’m not sure I like extension methods in this case but it was a good exercise.

Another thing was the integer overflow issue. I wonder if Kotlin, like Rust, is able to detect this sort of errors when the program is compiled in debug mode. That would be very handy.

Let’s see what day 4 brings us!

Advent of Code 2020 in Kotlin: Day 02

Lucas — Wed, 02 Dec 2020 18:19:49 +0000

A new day, a new challenge. Day 02 of the Advent of Code gave us a “practical” problem: There’s a database of passwords and it has inconsistent data. We need to find the passwords that match the correct format and count them.

The input is provided in a file, where each line is formatted as <number>-<number> <letter>: <password>.

How the input should be interpreted is different in parts 1 and 2.

Part 1

In this first part, the <number> items in the line indicate the minimum and the maximum (respectively) number of times <letter> should appear in the <password> for it to be valid.

Here’s how I solved it:

import java.io.File

data class PasswordEntry(
  val min: Int,
  val max: Int,
  val letter: Char,
  val password: String) {
  companion object {
    val entryRegex = Regex("""(\d+)-(\d+) +([a-z]): ([a-z]+)""")

    fun of(string: String) : PasswordEntry? {
      val matchResult = entryRegex.matchEntire(string)

      if (matchResult != null) {
        val (min, max, letter, password) = matchResult.destructured
        return PasswordEntry(min.toInt(), max.toInt(), letter[0], password)
      }
      return null
    }
  }

  fun isValid(): Boolean {
    val count = password.count({ it == letter })
    return (min <= count && count <= max)
  }
}

fun main() {
  var numberOfValidPasswords: Int = 0

  File("input.txt").forEachLine {
    val entry = PasswordEntry.of(it)

    if (entry != null && entry.isValid()) {
      numberOfValidPasswords++
    }
  }

  println(numberOfValidPasswords)
}

How it works

The solution is quite simple: We go over each line, use a Regex to extract the components we are interested in, and then create an object representing the entry.

The way I solved it is a bit over-engineered for such a simple problem, but it let me play with a few Kotlin concepts: Regexes and companion objects.

Kotlin doesn’t support static methods like Java, which you would normally use to define a Factory method. Instead, it offers companion objects: Inside your class, you can define another that provides methods to construct the object you want.

So after we covert each line into a PasswordEntryobject, we call isValid() to determine if the password is valid. If it is, we bump the count of valid passwords.

Part 2

The solution is almost identical, but the condition to determine if a password is valid changes. The <number> entries indicate that <letter> should be present in one of those indexes, but not both at the same time.

Here’s the code:

data class PasswordEntry(
  val firstOffset: Int,
  val secondOffset: Int,
  val letter: Char,
  val password: String) {
  companion object {
    val entryRegex = Regex("""(\d+)-(\d+) +([a-z]): ([a-z]+)""")

    fun of(string: String) : PasswordEntry? {
      // ... 
       return PasswordEntry(firstIndex.toInt() - 1, secondIndex.toInt() - 1, letter[0], password)
      // ...
      }
    }

    fun isValid(): Boolean = 
      (password[firstOffset] == letter).xor(password[secondOffset] == letter)
}

How it works

Not much changed here. Since the <number> entries represent the index, we subtract 1 from them. This way we get the correct offset in the string.

Then in the isValid() method, we use Boolean.xor to check that only of those offsets has the letter.

Done for the day

This was a nice little program to work on. I was exposed to Kotlin’s regex facilities and companion objects. Not sure how I feel about latter yet. I need to play with them for a while longer to see what’s the advantage over static methods.

Next up, Day 03.

Advent of Code 2020 in Kotlin: Day 01

Lucas — Tue, 01 Dec 2020 17:35:00 +0000

December is here, and with it came Advent of Code. Advent of Code is coding challenge that starts on December 1st and ends on December 25th. Every day a new puzzle is released. To win points (stars) you need to complete the puzzles.

Although I’ve followed the event in its past incarnations, I never took part in it. I decided to give it a go this year and since Kotlin has picked my interest recently, I chose to solve the challenges using the language. I’ll do this as an exercise, to learn more about the language and experiment.

Every day, I’ll make a new post with my solution for the day’s challenge. If you don’t want spoilers, please try to solve it on your own first!

The problem

The question is fairly straightforward. We are given a list of numbers (transaction values) as input and need to find numbers that match a certain criteria.

Part 1

In the first part of the challenge, we need to find two numbers that sum up to 2020. When we find them, we should return the result of multiplying those two numbers. That’ll be the answer to the problem.

Although the question masks it with a story, this is just a 2sum problem: We want to find two numbers that sum up to a given target (in this case, 2020).

Here’s how I solved it:

import java.io.File

fun solve(numbers: Array<Int>) : Int? {
    val complementMap = mutableMapOf<Int, Int>()

    for (index in numbers.indices) {
    val number: Int = numbers[index]

    if (complementMap.containsKey(number)) {
        return number * complementMap.get(number)!!
    }

    val complement: Int = 2020 - number
    complementMap[complement] = number
  }

    return null
}

fun main() {
    val numbers = mutableListOf<Int>()

    File("input.txt").forEachLine { numbers.add(it.toInt()) }

    print(solve(numbers.toTypedArray()))
}

How it works

The idea behind this solution is that we can simply iterate over the array of numbers and store their complements in a map. For each number of the array, we check if it is present in the map. If it is, that means we have seen its complement before and we can return the answer. If we haven’t seen the number yet, we put it in the map keyed by its complement.

With this, we get O(n) runtime complexity and O(n) space complexity.

Part 2

The second part is similar. We need to find three numbers that sum up to 2020 and return the result of multiplying them. This boils down to a 3SUMproblem.

import java.io.File

fun solve(numbers: Array<Int>) : Int? {
    numbers.sort()
    val count = numbers.size

    for (i in 0..count) {
        var left = i + 1
        var right = count - 1

    while (left < right) {
       val sum = numbers[left] + numbers[right] + numbers[i]

        if (sum == 2020) {
              return numbers[left] * numbers[right] * numbers[i]
        } else if (sum > 2020) {
              right--
        } else {
              left++
            }
        }
    }
    return null
}

How it works

This solution is a bit more involved. We start by sorting the array of numbers. For each number in the sorted array, we try to find two so that the three of them sum up to 2020.

Since we know the array is sorted, we can be smart when we search for those two numbers. We use two pointers: One after the number we “fixed” and the other at the end of the array. If the sum of the three numbers is larger than 2020, we move the right pointer to the left: We know there that then the sum will be either the same or less than current one. On the other hand, if the sum is less than 2020, we move the left pointer to the right: The new sum then will either be the same or greater than the current one.

When we find three elements that sum up to 2020, we just return the result.

This gives us O(n^2) runtime complexity and O(1) space complexity.

That’s all

It was quite fun to give this problem a go with Kotlin. The language is quite nice to write in and fairly readable, although I do have my beefs with it. Once thing i don’t get is why the for (i in 0..count) doesn’t require the keyword val/var since we are effectively declaring the variable i there. Seems like an inconsistency to me.

On the next post, I’ll go over how I solved day 02’s problem!

Would you pay for a React component?

Lucas — Sat, 14 Nov 2020 21:44:47 +0000

Places like Code Canyon allow you to build and sell your own (mostly) Wordpress plugins. That made me think about React.

Why not sell React components that do some useful integration?

Would you pay for a component that solved a problem you have or would you build your own?

Better code decoupling via delegates

Lucas — Mon, 27 Jul 2020 11:09:21 +0000

I work on a system called NetNORAD. NetNORAD is responsible for monitoring hosts across our fleet. We do that to measure the rate of packet loss happening in our clusters and determine if there’s a problem.

The system is comprised of three main components: A scheduler, an agent, and an aggregator. The scheduler decides what hosts the agents should monitor. The agents probe those hosts using UDP packets. The aggregators chew through all the data generated by the agents and try to come up with something useful.

The scheduler stores the lists of hosts it generates in Zookeeper. The system looks a bit like this:

A problem we had with our system until recently was the lack of backups. If something went wrong and the scheduler produced a bad list of hosts, we had no way of rolling back (only forward).

To address this, we decided store a copy of the lists in an object store.

A teammate of mine went about implementing this in a straightforward way: We had a class called ZookeeperWriter that knew how to encode the data and write it to Zookeper. My colleague’s approach was to just add a new method to support the new storage layer. Whenever we were done writing to Zookeeper, we’d write to the object store.

The code looked something like this:

class ZookeeperWriter: def writeShardedHostList(self, region, regionalHostList, globalHostList): blobs = { f"{region}\_regional\_host\_list": self.encoder.encode(regionalHostList), f"{region}\_global\_host\_list": self.encoder.encode(globalHostList) } try: self.writeBlobs(blobs) except ZookeeperError: raise else: self.writeShardedHostListToObjectStore(region, regionalHostList, globalHostList) def writeShardedHostListToObjectStore(self, region, regionalHostList, globalHostList): blobs = { f"{region}\_regional\_host\_list": self.encoder.encode(regionalHostList), f"{region}\_global\_host\_list": self.encoder.encode(globalHostList) } self.writeBlobsToObjectStore(blobs)

For historical reasons, we have multiple “flavours” of ZookeeperWriter classes: VanillaZookeeperWriter, ChocolateZookeeperWriter, etc. Each taking different arguments to encode and store. This made the code very cumbersome to extend when we needed to extend.

There was also another problem. When we encode data, we convert it to a binary format and compress it using bzip2. With the implementation we had that conversion and compression was executed twice: Once to store the data in Zookeeper and another to send it to the object store. Since the amount of data to encode was quite large, this repetitive behavior caused a slowed of around 15 minutes to our system.

To address the latter, we could just rearrange the code to avoid double encoding, but that needed to be replicated to every “flavour”.

How could we solve that?

Delegates

Delegation is when an object handles a request (i.e., method call) by delegating the request to a different object.

I know. That’s quite abstract.

In the context of this problem, think of it this way: The logic to encode data shouldn’t be tied to the code that actually writes data to the storage layer. The code handling the storage layer should only care about moving bits from here to there.

In our case, we had multiple ZookeeperWriters that knew both how to encode and how to store data. This made it difficult for us to reuse the compressed data and extend the system.

To solve this, I came up with a two different concepts: a BlobWriter and an AssetWriter. A BlobWriteris only concerned about writing bytes to a specific path in some kind of storage. It doesn’t care what the data is.

An AssetWriter, on the other hand, does care about the data. It knows how it should be handled and how the paths should be set. But it does not care how or where the data is written to. It delegates the writing to storage to a BlobWriter.

In this new setting, our classes looked like this:

class BlobWriter: @abstractmethod def writeBlobs(self , blobs: bytes): passclass ZookeeperBlobWriter(BlobWriter): def writeBlobs(self, blobs: Dict[str, bytes]): # Do zookeeper stuff to write blobsclass ObjectStoreBlobWriter(BlobWriter): def writeBlobs(self, blobs: Dict[str, bytes]): # Do object store stuffclass AssetWriter: def \_\_init\_\_(self, blobWriterDelegates: List[BlobWriter]): self.writerDelegates = blobWriterDelegatesclass ShardedListsAssetWriter(AssetWriter): def write(self, region: str, regionalHostList: HostList, globalHostList: HostList): blobs = { f"{region}\_regional\_host\_list": self.encoder.encode(regionalHostList), f"{region}\_global\_host\_list": self.encoder.encode(globalHostList) } for writer in self.writerDelegates: writer.writeBlobs(blobs)

And this is what the usage code looks like:

assetWriter = ShardedListsAssetWriter(writerDelegates=[ZookeeperBlobWriter(...), ObjectStoreBlobWriter(...),])...assetWriter.write(regionName, regionalHostList, globalHostList)

With this change, adding or modifying different asset writers is quite easy. We only need to specify how the data should be encoded and its storage will be handled by the blob writers.

On the other hand, adding or modifying blob writers (i.e., support different storage layers) is a breeze. We just need to write enough code to push bytes to the storage and all the encoding is taken care by the asset writers.

In conclusion

Knowing how and when to decouple your code is an important skill. It can make adding/modifying a code base easy.

Delegates are one tool we should keep in our arsenal to achieve that.

How about you? What do you think about delegates? Would you approach this problem differently?

I’d love to hear from you and learn different ways to solve the same problem.

3 ways to filter through collections in C++

Lucas — Mon, 20 Jul 2020 08:00:00 +0000

I spent some time last week reviewing a teammate’s diff (what we call pull-requests/patches where I work). The idea was pretty simple: The system processes a list of devices (i.e., hosts in our data centers) and applies a set filters to it.

Their code was straightforward: They had an abstract class called Filter that specified the interface. Each filter, in turn, received a vector of devices to process and spit out the filtered results. It looked something like this:

// Represents a host in the data center.struct Device;class Filter {public: ~Filter() {}; virtual std::vector<Device> filter(std::vector<Device>&& devices) = 0;};class MaintenanceStatusFilter : public Filter {public: std::vector<Device> filter(std::vector<Device>&& devices) override { return std::move(devices) | ranges::actions::remove\_if(somePredicate); }};class RackFilter : public Filter {public: std::vector<Device> filter(std::vector<Device>&& devices) override { return std::move(devices) | ranges::actions::remove\_if(someOtherPredicate); }};

Upon first inspection, that code is absolutely fine. ranges::actions::remove_if makes understanding the code a breeze.

The problem is what happens when we chain filters. When you do that, with the current code, you end up reallocating the vector whenever a filter was applied:

MaintenanceStatusFilter maintenanceFilter;RackFilter rackFilter;auto filteredDevices = rackFilter.filter( maintenanceFilter.filter(std::move(devices)));

How can we avoid that?

Views

C++ ranges offer a handy feature called View. Views differ from iterators in that they can be easily composed and are lazily evaluated. You can chain multiple of them and the result only gets computed when it is needed.

If we change our filters to be simple functions that look at a device and decide whether they should be removed or not, our code can be as simple as:

using ranges::views;auto filteredDevices = std::move(devices) | views::remove\_if(maintenanceStatusPredicate) | views::remove\_if(rackPredicate);

It doesn’t get much simpler than that.

But what if I can’t use ranges?

C++ ranges are fairly recent and chances are, if you’re working in an older code base, you won’t be able to use it. Or maybe you’re working with some other programming language that doesn’t have that sort of functionality. What do you do?

Here’s a few things you can try.

Use a driver

The idea is simple: Change our filter classes to only operate on a single device at a time, and move the logic to apply all the filters to a driver. This allows us to decouple the filtering logic from the “iterate-over-the-vector” logic.

Here’s what the filter classes would look like:

class Filter { ... virtual bool filter(std::Device& device) = 0;};class MaintenanceStatusFilter : public Filter {public: virtual bool filter(std::Device& device) override { return somePredicate(device); }};class RackFilter : public Filter {public: virtual bool filter(std::Device& device) override { return someOtherPredicate(device); }};

Here’s what the driver code looks like:

class Driver {private: std::vector<Filter\*> filters\_;public: Driver(std::initializer\_list<Filter\*> filters) : filters\_(filters) {} std::vector<Device> operator()(std::vector<Device>&& devices) { std::vector<Device> result; for (const auto& device : devices) { bool keep = true; for (Filter\* filter : filters\_) { if (f->filter(device)) { keep = false; break; } } if (keep) { result.push\_back(device); } } return result; }};

Using the driver:

MaintenanceStatusFilter maintenanceStatusFilter;RackFilter rackFilter;Driver driver = {&maintenanceStatusFilter, &rackFilter};auto filteredDevices = driver(std::move(devices));

This option is quite verbose, but I find it quite easy to follow. The driver takes a list of filters to apply and, when called, applies the filters to each device. If a filter matches, it short-circuits the whole process and excludes the device.

Template composition

This one might be the least straightforward to implement, but using it is trivial.

Just like in the previous example, we will change our filters to operate on single devices.

We can define a template class that allows us to chain our filters into a single one. That class will be responsible for ensuring all chained filters get applied.

template<typename F0, typename... F>class Chainer : Filter {private: F0 f\_; Chainer<F...> rest\_; public: Chainer(F0 f, F... rest) : f\_(f), rest\_(rest...) {} bool filter(const Device& device) override { if (f\_.filter(device)) return true; return rest\_.filter(device); }};template<typename F>class Chainer<F> : Filter {private: F f\_;public: Chainer(F f) : f\_(f) {} bool filter(const Device& device) override { return f\_.filter(device); }};template<typename... F>Chainer<F...> chain(F... fs) { return Chainer<F...>(fs...);}

Here’s how we apply it:

auto filter = chain(MaintenanceStatusFilter(), RackFilter());std::vector<Device> filteredDevices;for (const Device& device : devices) { if (!filter.filter(device)) { filteredDevices.push\_back(device); }}

This one is quite a mouthful. Basically what we did was define a “recursive” template class that can take multiple filters as input. We specialize the class for the case it receives a single filter.

The Chainer class is also made a child of Filter so we can use it as such. When filter is called on a Chainer, it will apply all its chained filters to the given device. If an early filter says the device should be removed, we short-circuit the whole process and don’t invoke the remaining filters.

The chain function is just a convenience so we can avoid typing the templated types.

The usage code is quite simple, not that different from the driver code we had before.

In conclusion

I can’t lie, C++ ranges are a great addition to the language and I can’t wait to use it in more places. That said, it is still important to know how to accomplish the same thing in different ways.

How about you? What are your thoughts on C++ ranges? Can you think of other ways to solve this problem?

Espresso shots and software development

Lucas — Wed, 08 Jul 2020 14:08:58 +0000

A programmer saying they love coffee must be a cliché at this point, but I am guilty as charged: I love coffee.

As Ireland started to ease its lockdown and things are opening up, I finally had a chance to take a barista course. That was something I’d wanted to do for many years.

After gaining insight into the processes that happen at a coffee shop, I couldn’t help but trace parallels to what we do as software engineers. That’s what I want to talk about today.

Prep work

We started our session going over what needs to happen before you start making coffee.

You start by calibrating the grinders, trying to find the coarseness that will let you pull an espresso shot to perfect. Once you have it, you move to to set the grinders with the correct timing to give you the right amount of coffee for a double shot.

Skip all that and you’ll get (at best) subpar coffee that won’t make your customers happy.

I find this similar to the work we do before embarking on a project. Gathering the requirements, sketching out what the system should look like, defining service-level indicators (SLIs) and objectives (SLOs), etc, are all part of the prep work we do as engineers.

Planning before starting the work enables us to assess the risks and put our projects in a better position to succeed.

Balance

After we learn about the prep work, our instructor went over the espresso brewing process. If you brew it for too short a period, the coffee comes out too acidic. Brew it for too long and it comes out too bitter. There’s a fine balance between those two extremes that gives you perfect coffee.

The same applies to software.

If you under-engineer a system, you might find yourself in trouble when requirements change or demand increases. The lack of planning will result in pain points when it’s time to make the project scale.

On the other hand, an over-engineered system can become a nightmare to understand and maintain. Changes become difficult and sometimes (most of the time?) lead to unexpected results.

Finding balance is not easy, but it’s needed to achieve great software.

Clean up

One of the things our instructor mentioned was clean up.

As you go about making lattes, spillage will happen. Too much of that and your workspace becomes a mess, you become less effective at preparing the orders and everything feels terrible.

That’s why clean up is important. From time to time, he said, you have to stop and clean up the area so you can keep working.

I relate this to what we call tech debt in software development. As projects go on and deadlines grow tighter, we cut corners and sometimes make poor decisions that leave our code base in a bad state.

Tech debt is not inherently bad. Just like a coffee shop has to accept some untidiness to get the orders going, so does software development. Sometimes it’s needed and the right thing to do.

That untidiness only becomes a real problem when we take too long to clean it up. When the debt is not repaid, work becomes difficult. Tasks that should be simple take longer to complete.

Just like the coffee shop needs periodic cleaning, so do our code bases.

Conclusion

Although this posts draws parallels to software engineering topics, I’m sure you can see similarities to other areas as well.

I hope you found this post interesting, and that it helped you stop and think deeper about our craft. Or, if anything, I hope it makes you appreciate the work that’s put into your lattes a bit more!