UrbanLife

Last night I was playing around with some simple algorithm questions. The required language was good ol' JavaScript, but being a recent convert to Elixir and the functional programming realm, I went ahead and wrote solutions in both languages.

The question was to write a function that given an array, returns an array that contains cumulative sums.

i.e.:

cumlativeSums([1, 2, 3, 4, 5]) -> [1, 3, 6, 10, 15]

Pretty standard coding assessment question. Deceptively simple, but not too hard that you can't solve it if you don't know it beforehand. There are also so many solutions out there for it. See this Stack Overflow question for inspiration.

JavaScript

Curry 🍛

Now, by far the coolest method you can do is use the native map function with Currying.

function sumArrayCurry(arr) {
  return arr.map(
    (
      (sum) => (value) =>
        (sum += value)
    )(0)
  )
}

This happens to be the top-voted solution on Stack Overview, however, I'm not really a fan. It's honestly hard to read. If I came across this function in an actual codebase I would have to waste time trying to figure out what the hell it was doing. It's even worse if you don't have a strong grasp of what Curring actually is. Here's a link to a Stack Overflow explanation since Wikipedia is so dense.

Array.prototype.reduce

The method that came to mind when I first read the question was to use <some array>.reduce. From reading the question I know that I was going to have to do something to every element of the array and then return a new array containing the resultant values.

This sounds like it would be perfect for map since it returns an array, but reduce is nice since we can easily pass the cumulative sum to the next iteration of the call-back function. This doesn't mean that you can't use a map, just how my thought process worked.

function sumArrayReduce(arr) {
  const sums = []

  arr.reduce((prev, cur, index) => {
    return (sums[index] = prev + cur)
  }, 0)

  return sums
}

I like this because it's easy to follow the programmer's logic and the flow of the program, and if you don't understand what the program is doing, you can easily look up what reduce does. The one thing about this solution is that it relies on native JavaScript functions. During any sort of coding interview (which, let's be honest, is the only situation where this will come up) you'll probably be asked not to use the native API.

Recursion

As I mentioned before, I'm a recent Elixir convert. I just discovered a love of functional programming after years of hate due to the abuse that Scheme left on me during university. Being that an Elixir solution would probably use something with recursion, I wanted to use that without depending on the native JavaScript reduce function.

function sumArrayRecursive(arr) {
  return sumArrayHelper(0, 0, [], arr)
}

function sumArrayHelper(prevSum, index, sums, arr) {
  if (!arr.length) {
    return sums
  }

  const curSum = arr[index] + prevSum
  sums.push(curSum)
  arr.shift()

  return sumArrayHelper(curSum, index++, sums, arr)
}

This solution does rely on some of the native API, but it does eliminate the reduce. It also follows a tail-recursive pattern, even though that doesn't mean much in the current JavaScript world (Safari is the only browser that supports proper tail calls source).

Beautiful Elixir

Elixir makes functional programming make sense and enjoyable with things like pattern matching and tail recursion. Pattern matching is what I particularly like. For those who are not familiar with pattern matching, it means what it sounds like: you can do things based on how they look. This is quite common when it comes to things like cases, conditional statements, or in our case here, function definitions.

defmodule ListHelper do
  def cumlative_sum(list) do
    p_cumlative_sum(0, [], list)
  end

	# 1
  defp p_cumlative_sum(_prev_sum, sums, []), do: Enum.reverse(sums)

	# 2
  defp p_cumlative_sum(prev_sum, sums, [head | tail]) do
    p_cumlative_sum(prev_sum + head, [prev_sum + head | sums], tail)
  end
end

Here I create a module called ListHelper just so I can run the program inside of iex (interactive Elixir). I define one public function cumlative_sum/1 which will take a list (Elixir does not have traditional “arrays” only linked lists). I also define two private functions to handle the recursion p_cumlative_sum/3. These private functions have the same name and the same number of parameters, but what's different is the pattern that they match on.

The third parameter is defined to be a list. #1 p_cumlative_sum/3 will match only when that third argument is an empty list, whereas #2 will match only when the list is not empty. This behavior is the same as the JavaScript recursive solution where we check the list's length before we proceed to do any logic if(!arr.length) {...}.

To me, this just makes a lot more sense in my mind, and in practical situations, it helps build cleaner solutions.

Side effects

Also, on a side note, data in Elixir is immutable. This means no side effects. The recursive JavaScript solution above has a glaring issue. The arr.shift() call. The array passed to the function will be modified during the function's execution. Meaning, after the function has returned, whatever array you passed to it will be empty.

Side effects have been my biggest gripe while Going from JavaScript to Elixir and back again. I want to write in a functional way, but inconsistencies in JavaScript, and all the side effects that pop off just make it so hard.

Summary

I'm not really sure what the point of this was supposed to be, but I had fun playing around with both languages while solving a simple algorithm. I am by no means an expert when it comes to JavaScript or Elixir, and I didn't spend too much time optimizing my solutions so take my code with some 🧂 and 🌶.

Feel free to leave your own solutions to the question, or even improve upon mine. I'm sure there's a way to use recursion in JavaScript without having to use Array.prototype.shift, or even a way to remove the Enum.reverse/1 in the Elixir solution.

Thanks for reading! 👨‍💻

#javascript #elixir #algorithm #writefreely #blog #programming #interviewquestions #codinginterview