Leetcode Problem Solutions in Elixir

Questions / Help
1

Has someone over here worked on Leetcode problems in Elixir and would be willing to share their solutions?

I was recently solving the LRU Cache problem using the Elixir programming language and it is so frustrating to solve in Elixir. People have mostly used Doubly Linked Lists which are extremely hard to implement in Elixir.

2

Just tried it and came up with this:
Probably not the most performant way, but it works :upside_down_face:

defmodule LRUCache do
  @spec init_(capacity :: integer) :: any
  def init_(capacity) do
    Agent.start_link(fn -> %{lru: [], cap: capacity} end, name: __MODULE__)
  end

  @spec get(key :: integer) :: integer
  def get(key) do
    Agent.get_and_update(__MODULE__, fn %{lru: lru, cap: capacity} = state ->
        case List.keyfind(lru, key, 0) do
            nil -> 
                {-1, state}
            {key, value} -> 
                new_lru = [{key, value} | List.keydelete(lru, key, 0)]
                {value, %{state | lru: new_lru}}
        end
    end)
  end

  @spec put(key :: integer, value :: integer) :: any
  def put(key, value) do
    Agent.update(__MODULE__, fn state ->
        new_lru = [{key, value} | state.lru]
        if length(new_lru) > state.cap do
            %{state | lru: remove_last(new_lru)}
        else
            %{state | lru: new_lru}
        end
    end)
  end
      
  defp remove_last(list), do: list |> Enum.reverse |> tl() |> Enum.reverse
end

# Your functions will be called as such:
# LRUCache.init_(capacity)
# param_1 = LRUCache.get(key)
# LRUCache.put(key, value)

# LRUCache.init_ will be called before every test case, in which you can do some necessary initializations.

Edit: Ohh. Maybe it doesn’t work. Just tried to submit it and got an error :joy:
When I run the commands locally it works though…

3

Perhaps I’m missing some fundamental understanding, but I don’t think you will be able to implement it in Elixir with the constraint that the get and put commands are O(1) time. The only O(1) access data structure in Elixir, per Big-O Time Complexities for Elixir and erlang Data Structures · GitHub, is a tuple, but insertion and deletion are O(n). You can get O(1) for prepending and deleting first element of a list, but accessing it would be O(n). Maps at best appear to be O(log n) for the necessary operations.

1 Like
4

Most of the leetcode problems seem to rely on mutation so functional languages are often at a disadvantage. It’s another reason using leet code for interviewing is usually a bad idea.

7 Likes