Devops Interview Prep: Leetcode as Code

In a competitive job market it’s important to be able to demonstrate the technologies you’re proficient with, and the undisputed best test for this takes the form of a whiteboard exercise or an algorithm test to see if you’re able to implement common data structures and the sort.

But, could I succeed without functions, true if/else statements, and loops?

Fizzbuzz is often a first interview question for candidates and we’ll cut our teeth on it:


locals {
  iterations = 100 # First we specify the number of iterations
  fizzbuzz = [for i in range(local.iterations) : {
    index = i
    value = i % 15 == 0 ? "FizzBuzz" : 
      i % 3 == 0 ? "Fizz" : 
      i % 5 == 0 ? "Buzz" : 
      i # Otherwise, just return the index
  }]
  fizzbuzz_result = [
    for i in local.fizzbuzz : length(i.value) > 0 ? i.value : i.index
  ]
}
# ["1", "2", "Fizz", "4", "Buzz", "Fizz", <snip>..., "14", "FizzBuzz"]

Okay, not so bad, what about sorting? Surely this will scale well. Can it sort?

locals {
  mixed_list = [
    1, 3, 5, 1,1,1
  ]

  bubble_sorted_list = [
    for i, val in range(length(local.mixed_list)) :
    i < length(local.mixed_list) - 1 ?              # Make sure we don't go out of bounds
    local.mixed_list[i] < local.mixed_list[i + 1] ? # Determine if we need to swap
    local.mixed_list[i] : local.mixed_list[i + 1] : # Handle the swap
    local.mixed_list[i]                             # We were on the last element, just return the value
  ]
}
# Not quite. We're not sorted, and we misplaced a 5 somewhere.
# [1,3,1,1,1]

Let’s update that to use a module:

locals {
  state = [5, 4, 3, 1, 2]
}

# Five passes, each pass performs odd+even swaps
module "pass_0" {
  source = "./mods/pass"
  in     = local.state # [5,4,3,1,2]
}

# <snip> pass_1 through pass_4 </snip>

module "pass_4" {
  source = "./mods/pass"
  in     = module.pass_3.out # [1,2,3,4,5]
}

The timeless product of cs50 students everywhere, but we want to set our sights higher.

P.S. unfortunately importing ./mods/pass from within mods/pass led to a circular dependency, bringing terraform to its knees. I also considered putting terraform apply --auto-approve into a while loop and letting it mutate a file input, but I think I’m getting distracted.

# Here's the module:
variable "in" {
  type        = list(number)
  description = "Input list for a single odd+even bubble pass"
}

module "swap_odd" {
  count  = floor(length(var.in) / 2)
  source = "../swap"
  in     = [var.in[count.index * 2], var.in[count.index * 2 + 1]]
}

locals {
  pass_odd = concat(
    flatten([for i in range(0, length(module.swap_odd)) : module.swap_odd[i].out]),
    length(var.in) % 2 == 1 ? [var.in[length(var.in) - 1]] : []
  )
}

module "swap_even" {
  count  = floor((length(local.pass_odd) - 1) / 2)
  source = "../swap"
  in     = [local.pass_odd[count.index * 2 + 1], local.pass_odd[count.index * 2 + 2]]
}

locals {
  pass_even = concat(
    [local.pass_odd[0]],
    flatten([for i in range(0, length(module.swap_even)) : module.swap_even[i].out]),
    length(local.pass_odd) % 2 == 0 ? [local.pass_odd[length(local.pass_odd) - 1]] : []
  )
}

A bit messier, but it works. I think I could get rid of the swap module but I need a new challenge. Let’s try something with a cleaner approach: is this a palindrome?

locals {
  is_palindromes = [
    "", "a", "aa", "aaa", "kayak", "radar", "racecar", "madam", "dog", "god",
    "cat", "act", "rat", "mat", "hat", "bat", "tab", "cab", "bac", "aca", "cac",
    "aac", "cca", "aaa", "ccc", "aaaa"
  ]
  palindromes = [
    for str in local.is_palindromes :
    length(str) <= 1 ? true : # empty string and single characters are palindromes
    alltrue([
      for i in range(floor(length(str) / 2)) :
      substr(str, i, 1) == substr(str, length(str) - 1 - i, 1)
    ])
  ]
}

The next challenge is Two Sum, which we can conquer with a map:

locals {
  # Test data for Two Sum
  two_sum_array = [2, 7, 11, 15, 3, 6, 1, 8, 4, 9]
  two_sum_target = 23
  
  two_sum_value_map = {
    for i, val in local.two_sum_array : tostring(val) => i
  }
  
  # For each number, check if (target - number) exists in the map
  two_sum_raw = [
    for i, num in local.two_sum_array :
    contains(keys(local.two_sum_value_map), tostring(local.two_sum_target - num)) && 
    local.two_sum_value_map[tostring(local.two_sum_target - num)] != i ?
    {
      indices = [i, local.two_sum_value_map[tostring(local.two_sum_target - num)]]
      values = [num, local.two_sum_target - num]
      sum = local.two_sum_target
    } : null
  ]
  
  # Filter out null results from optimized solution
  two_sum_results = [
    for result in local.two_sum_raw: result if result != null
  ]
}
# {
#     "indices" = [3,7]
#     "sum" = 23
#     "values" = [15,8]
# }

Ah yes Mitchell would be proud.