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
Deploy Phoenix to your own VPS with PaaS ease: push-to-deploy, zero downtime, auto SSL, managed Postgres. 14-day free trial at potions.io
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
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!
Master modern tools, write cleaner code, and tackle real-world challenges.
Producing high quality Elixir screencasts since 2017.
The deployment platform built for Elixir: PaaS ease, VPS control.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
Showing Posts 24 to 15- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
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.
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:
wanton7
Used bit more of my time to avoid more memory allocations and here is v2. Now uses 0KB
Qqwy
Thank you @eksperimental for tagging me. What an interesting topic!
Yes and no. The Erlang
:arraymodule indeed does not state a particular time complexity and it is allowed to change its internal implementation whenever a new version of Erlang would want.But practically speaking, for the last 15+ years, the implementation has been the same: finger trees with node size 10 (in other words: nested 10-element-tuples), meaning that access is O(log10(n)). Logarithmic time complexities (especially those with large bases) can be considered ‘practically constant-time’.
Besides my Arrays library there’s also Okasaki which is very similar but for queues. It probably will have a constant-time overhead over using
:queuedirectly because of the extra layer of wrapping with Elixir structs and protocols, but using it should be much more idiomatic than using:queueor:arraydirectly.And then there are of course a hand full of libraries written using NIFs (natively implemented functions), such as Explorer and Nx which are faster for certain math or data science operations (when you want run the same calculation on a large block of data) but they are not general-purpose (you cannot store any Elixir structure in them; most operations only work on ints or floats).
I might try to write an implementation of this example problem myself if I find the time
.
stefanluptak
Benchmarking is quite simple. You download the gist file I posted above and then run
That’s it.
elixir benchmark.exs.wanton7
I mean I would avoid recreating list must as possible with something like this.
I actually don’t know how to benchmark in Elixir
so maybe someone else can check how does this perform.
nikiiv
That’s not going to work in this approach. The original code was trying to have a sliding window within the original list by appending or removing from both end of the
windowbased on the numbers. Otherwise, you are rightwanton7
I just use Elixir in hobby project but my two cents are that’s why in Elixir it’s sometimes better for performance to add items into beginning of list and reverse it later. Or solution might be to put items into multiple lists then reverse some and combine lists.
eksperimental
There’s a relevant discussion in the forum related to constant time access.
The possible options seem to be using tuples or ETS tables.
Another alternative would be to create your own constant-time-access structure, which is a struct, but internally it uses a tuple. You could take as an inspirations @Qqwy’s library Array, GitHub - Qqwy/elixir-arrays: Well-structured Arrays with fast random-element-access for Elixir, offering a common interface with multiple implementations with varying performance guarantees that can be switched in your configuration. · GitHub
I will play with different solutions and come back to it when I have time.
eksperimental
Sorry, it is too late here