nikiiv
Hi all, I am trying to learn how to write idiomatic Elixir. I decided to write an implementation of a coding challenge I was given long time ago.
I wrote the implementation and tests, but.. I don’t like it
The problem I see is that I use too many exit checks . The algo is explained on the github page. If someone can take a look and give me some pointers I will be very very grateful.
I should note that the goal is O(n) including how any internal or external libraries could potentially affect it
defmodule CodingTest do
@moduledoc """
* Implement a method that will determinate if exists a range of
* non-negative elements in an array that sum up to a specific non-
* negative number
*
* Example 1 - targetSum 3, numbers = [1,7,1,1,1,5,6,1] - output true (the sum of the elements in range 2 to 4 is 3
* Example 2 - targetSum 7, numbers = [0,4,5,1,8,9,12,3,1] - output false (no range sums to 7)
*
"""
def solution([h|t], target_sum) do
find_solution([h],t,h, target_sum)
end
defp find_solution(_,_,target_sum, target_sum) when target_sum > 0, do: :OK
defp find_solution(_,[0 | _], _, 0), do: :OK
defp find_solution(arr, [h | t], current_sum, target_sum) when current_sum < target_sum do
#Slog.log ["case_less", arr, [h | t], current_sum, target_sum]
current_sum = current_sum + h
find_solution(arr ++ [h], t, current_sum, target_sum)
end
defp find_solution([h | t], right, current_sum, target_sum) when current_sum > target_sum do
current_sum = current_sum - h
find_solution(t, right ,current_sum, target_sum)
end
defp find_solution([], [h|t], _, target_sum), do: find_solution([h],t,h, target_sum)
defp find_solution(_,[],current_sum, target_sum) when current_sum != target_sum do
:KO
end
defp find_solution([],[],_, _), do: :KO
end
TEST
defmodule CodingTestTest do
use ExUnit.Case
doctest CodingTest
test "solution" do
assert CodingTest.solution([1,2,3,4],6) == :OK
assert CodingTest.solution([1,7,1,1,1,5,6,1],3) == :OK
assert CodingTest.solution([0,4,5,1,8,9,12,3,1],7) == :KO
assert CodingTest.solution([5,3,3,3,4,100],13) == :OK
assert CodingTest.solution([5,4,3,2,1,0,1,2,3,4,5],0) == :OK
assert CodingTest.solution([5,4,3,2,1,1,1,2,3,4,5],0) == :KO
end
end
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Error tracking, logs, APM, uptime and cron monitoring in one dev-friendly platform. Find and fix problems before your users notice.
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixirconf-us
- #ai
- #blog-post
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #hex
- #security
- #metaprogramming
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!
Practical resources that improve the lives of professional developers.
Master modern tools, write cleaner code, and tackle real-world challenges.
**Building the future of software with AI, trust, and human connection.**
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
First Post!- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
tomekowal
I’d do it this way:
Thoughts:
[h | t] = _nameto convey variable meaningandin guards, so havinglength(current_sublist) > 0drops one of the cases that started from scratch and merges it with the case where we have too little elements (they were doing the same thing conceptually - taking a new element from the rest of the list)We could potentially still put stop conditions first, but the check would be we would be more compiicated and I’d rather reduce the number of clauses.
Most Liked
Qqwy
I had some spare time, so here are three implementations.
I have created an updated gist for the benchmark which you can run just as before as
elixir benchmark.exs.I’ve also added a few larger inputs, so you can see the difference in how solutions behave if they get a list with 100 elements vs a list with 1_000_000 elements.
1. Using Okasaki
The following is a 1:1 conversion of @100phlecs ’ solution but using the afore-mentioned Okasaki library for the queue rather than using Erlang’s
:queuemodule directly. I’ve added the three different backing queue implementations as separate functions to the benchmark so you can see what the difference in performance and memory usage is (for this particular problem).The main takeaway (at least for me) is that in these kinds of situations you can see the overhead of an extra Elixir struct wrapping the thing you are manipulating, and the overhead of dispatching through a protocol (even though it is consolidated).
I expect that these overheads are especially visible because there are many inter-module calls which are not JIT-friendly. Nonetheless, in everything but the most performance-critical code I think that using a library that has Elixir-friendly features (e.g. pipe-able functions, data structures implementing
Inspect,Enumerable,Collectable,Access) is preferable to using:queueor:arraydirectly (or rolling your own).2. Using Nx
This was mostly written for fun because I haven’t had the opportunity to use Nx much yet.
It is not actually fast. I think this is because of two reasons:
3. Using lists properly
After tinkering a little, I realized that there is a much simpler solution! We only need to walk over the input list once, and can build up the window implicitly while doing this.
The trick is that we pass the same list twice to the recursive function. Inside the recursion, one of the two parameters will become the ‘tail’ of the list used by the other argument. Because of how immutable, persistent datastructures work, the same underlying memory is used without any copying so this is fast and memory-efficient.
And because we are only looking at the head of the list, access is O(1).
This is my preferred solution, and I think it is reasonably readable.
EDIT: The new solution by @wanton7 implements the same idea. I believe both of our solutions compile down to virtually identical bytecode.
Benchmarking results:
100phlecs
Here’s mind attempt to create less checks.
In order to maintain an O(n) runtime complexity, I reached for the :queue erlang module which allows O(1) inserts and pops for a FIFO data structure.
This allows us to maintain a ‘sliding window’ view of the list, moving the right side it when the range sum is too small and moving the left side when the range sum is too large.
Originally I reached for
Enum.reducebut because we have to process nodes within the list more than once (seewhen sum > targetfunction) recursion makes the most sense.Idiomatic Elixir usually keeps atoms lowercase, and represents empty states either with
nilor{:error, reason}, so I changed those values.As to why I changed
find_solutiontofindis just personal preferenceWithout the
:queuedata structure we could take advantage ofEnum.reverseto simulate a queue, but then the runtime is no longer O(n), but O(n * k) where k is the max length of the simulated queue (I think, feel free to correct if wrong)Edit: I found a case where my solution fails, which is the case where the range is at the very end of the list. It requires modifying the case of
when sum == target:I’m sure there’s more elegant ways to solve this, but I went with this because it’s more readable to me.
Here’s a new test case to confirm it works:
I updated the Livebook (here is where it is hosted)
stefanluptak
I did a benchmark of the solutions presented here and @100phlecs’s solution is still the fastest, but your second solution uses the least memory. See: benchmark.exs · GitHub
Results:
Last Post!
100phlecs
This solution reminds me of how imperative languages may approach the problem–by maintaining “pointers” or indices within the array. It seems you found the most elegant solution to the problem. It is clever to use pattern matching as the “pointer” effectively, thanks for sharing your solution
One could entertain converting the list into a map
list |> Enum.with_index |> Map.newto mimic pointers with two indices, one for the start of the window and one for the end.Though looking at the Big O for map access the solution would be O(n * log n) in that case, so it won’t work. I also think the code would be more verbose going down this path.