How to use GenServer in leetcode?

[stackcats]

900. RLE Iterator

The problem needs to keep track of the encoding list

So I used GenServer to solve this

This is the first version of the code

defmodule RLEIterator do
  use GenServer
  
  @spec init_(encoding :: [integer]) :: any
  def init_(encoding) do
    GenServer.start_link(__MODULE__, encoding, name: __MODULE__)
  end

  @spec next(n :: integer) :: integer
  def next(n) do
    GenServer.call(__MODULE__, {:next, n})
  end

  def init(encoding) do
    {:ok, encoding}
  end

  def handle_call({:next, n}, _from, state) do
    {res, new_state} = next_(n, state)
    {:reply, res, new_state}
  end

  defp next_(_n, []), do: {-1, []}
  
  defp next_(n, [ct, num | rest]) do
    if ct >= n do
      {num, [ct - n, num | rest]}
    else
      next_(n - ct, rest)
    end
  end
end

The code will be called as such:

RLEIterator.init_([3, 8, 2, 5])

param_1 = RLEIterator.next(2)

RLEIterator.init_([2, 5, 3, 8])

param_1 = RLEIterator.next(5)

I got the wrong answer.

Because there are multiple test cases with one GenServer instance.

So I changed my code

defmodule RLEIterator do
  use GenServer
  
  @spec init_(encoding :: [integer]) :: any
  def init_(encoding) do
    GenServer.start_link(__MODULE__, [], name: __MODULE__)
    GenServer.call(__MODULE__, {:init, encoding})
  end

  @spec next(n :: integer) :: integer
  def next(n) do
    GenServer.call(__MODULE__, {:next, n})
  end

  def init(encoding) do
    {:ok, encoding}
  end

  def handle_call({:init, encoding}, _from, _state) do
      {:reply, [], encoding}
  end    
  def handle_call({:next, n}, _from, state) do
    {res, new_state} = next_(n, state)
    {:reply, res, new_state}
  end

  defp next_(_n, []), do: {-1, []}
  
  defp next_(n, [ct, num | rest]) do
    if ct >= n do
      {num, [ct - n, num | rest]}
    else
      next_(n - ct, rest)
    end
  end
end

I think it’s so ugly in function init_.

How to improve the code？

[Sebb]

You don’t need a GenServer for RLE. Thats just a function.
Seems like you want to do OO in Elixir.

It could look sth like

defmodule RLE do
   def encode(seq) do
   ...
   end

   def next(encoded) do
   ...
   end
end

[stackcats]

How to do OO in Elixir such as Class static fields without GenServer or Agent?

[Sebb]

I think there is a good thread here about transition from OO to Elixir, but I can’t find it.

The very short answer is: create a module with a defstruct which replaces the attributes. The functions of the module replace the methods. The functions get an instance of the struct as argument. Inheritance is replaced by aggregation.

[stackcats]

But the signature of the function can’t be changed in leetcode.

[mudasobwa]

@stackcats

GenServer.start_link(__MODULE__, [], name: __MODULE__)

This line in subsequent calls to init_/1 won’t do what you think it will. There might be only one instance with the name RLEIterator running, meaning the second and all other calls would return {:error, {:already_started, pid}} tuple and next/1 will send a message to the very first instance started. That is one of the reasons you are better to directly pattern match on the return value of GenServer.start_link/3.

{:ok, _pid} = GenServer.start_link(__MODULE__, []} # , name: __MODULE__)

You likely need an agent, keeping the map %{encoding ⇒ pid} and a bunch of anonymous instances of RLEIterators.

[stackcats]

How to find the corresponding GenServer when calling RLEIterator.next(2)?

Agent needs the encoding list to get pid

[mudasobwa]

Ah, indeed. next/1, accepting an integer only, won’t likely work in the concurrent environment at all.

Then what has been suggested above (no processes, no state, plain old good recursion) is the way to go.

[deadbeef]

TL;DR: I think @stackcats solution is basically spot on. Just dealing with LeetCode’s contrived problem setup/environment is awkward and basically forces anti-patterns.
Here’s my solution: https://leetcode.com/problems/rle-iterator/solutions/5024907/elixir-solved-with-recursion-state-held-in-agent/

---

Sorry to necropost, but came across this post while I’ve been doing LeetCode problems.

@Sebb is correct that this problem can be solved without GenServer or any “state” management. However, also pointed out, LeetCode setup the “API” in a way that we can’t just recurse/yield results. So we do need a way of storing state for subsequent calls to next/1.
IMO, it’s a bit contrived for Elixir, but I assume LeetCode has adapted this in “spirit” of other languages implementations.

I believe the problem can be “generically” (i.e. without GenServer) with something like this:

defp do_next([], _n), do: {-1, []}
defp do_next([cnt, _elm | rest], n) when cnt < n, do: do_next(rest, n - cnt)
defp do_next([cnt, elm | rest], n), do: {elm, [cnt - n, elm | rest]}

We find the value, then return the updated list, which will be used for subsequent calls.

---

@mudasobwa is correct about how subsequent calls to init_/1 (in current impl.) will result in {:error, {:already_started, pid}}, and that normally you’d use something like a dynamic supervisor, something to manage anonymous processes, or something. I feel test cases would normally manage resetting processes or have one “fresh” one per test case (or something). However, LeetCode provides a black box and just tells us

RLEIterator.init_/1 will be called before every test case, in which you can do some necessary initializations.

So, to me, this also feels a bit contrived, but need to adapt to the LeetCode environment. So we need a way to setup the process on the first call, then “reset” on every subsequent call.

To handle the multi-calls to init_/1, I’m sure we could do something with superviors/anonymous processes or something. Instead, I kept the process “well-known” (i.e. name: __MODULE__) and “reset” it on subsequent calls with Agent.cast/2, i.e.

@spec init_(encoding :: [integer]) :: any
def init_(encoding) do
  case GenServer.whereis(__MODULE__) do
    nil -> Agent.start_link(fn -> encoding end, name: __MODULE__)
    _ -> Agent.cast(__MODULE__, fn _ -> encoding end)
  end
end

It’s kinda hacky, IMO, but feels fine/fitting for the blackbox environment the problem suggests/provides.

---

I found this problem to be similar to 380. Insert Delete GetRandom O(1), which also heavily suggests the use of GenServer or the like.
Now that we have our “generic” solution and handled init_/1, we just need to wrap do_next/2 by having next/1 leverage Agent. I used it like this:

@spec next(n :: integer) :: integer
def next(n) do
  Agent.get_and_update(__MODULE__, &do_next(&1, n))
end

do_next/2’s return is already in the form of {a, state()}, so we can just call do_next/2 and pass in the current state and n.

---

My full solution here: https://leetcode.com/problems/rle-iterator/solutions/5024907/elixir-solved-with-recursion-state-held-in-agent/

[deadbeef]

Solution copy/pasted (in case someone doesn’t want/can’t click the link):

defmodule RLEIterator do
  use Agent

  @spec init_(encoding :: [integer]) :: any
  def init_(encoding) do
    # Kinda hacky, IMO. But feel it's a fine way to "reset" the named Agent for
    # this scenario
    case GenServer.whereis(__MODULE__) do
      nil -> Agent.start_link(fn -> encoding end, name: __MODULE__)
      _ -> Agent.cast(__MODULE__, fn _ -> encoding end)
    end
  end

  @spec next(n :: integer) :: integer
  def next(n) do
    Agent.get_and_update(__MODULE__, RLEIterator, :rle_next, [n])
  end

  @spec rle_next([integer], integer) :: {integer, [integer]}
  def rle_next([cnt, _elm | rest], n) when cnt < n, do: rle_next(rest, n - cnt)
  def rle_next([cnt, elm | rest], n), do: {elm, [cnt - n, elm | rest]}
  def rle_next([], _n), do: {-1, []}
end

# [As noted by LeetCode:]
# Your functions will be called as such:
#
# RLEIterator.init_(encoding)
# param_1 = RLEIterator.next(n)
#
# `RLEIterator.init_/1` will be called before every test case, in which you can
# do some necessary initializations.

[christhekeele]

@deadbeef

I believe the problem can be “generically” (i.e. without GenServer) with something like this:

defp do_next([], _n), do: {-1, []}
defp do_next([cnt, _elm | rest], n) when cnt < n, do: do_next(rest, n - cnt)
defp do_next([cnt, elm | rest], n), do: {elm, [cnt - n, elm | rest]}

We find the value, then return the updated list, which will be used for subsequent calls.

Yep, this “reducer” pattern is pretty idiomatic Elixir, especially as you formulated it: a def xxx/1 that calls a recursive defp do_xxx/2 with an empty list as an initial accumulator, that returns the accumulator from the result of the final recursion. You’ll often see the acc last, rather than first, in your example.

@deadbeef

@Sebb is correct that this problem can be solved without GenServer or any “state” management. However, also pointed out, LeetCode setup the “API” in a way that we can’t just recurse/yield results. So we do need a way of storing state for subsequent calls to next/1.

This is also a reasonable use-case for the (often discouraged in production use) process dictionary (see: Process.put/2, Process.get/1, Process.delete/1).

[deadbeef]

You’ll often see the acc last, rather than first, in your example.

Totally agree.

To provide more detail, I structured it specifically to adapt for Agent.get_and_update/5, i.e. to do this:

@spec next(n :: integer) :: integer
def next(n) do
  Agent.get_and_update(__MODULE__, RLEIterator, :rle_next, [n])
end

• I changed the name from do_next/2 to (public) rle_next/2 to distinguish against the do_* pattern. I felt it isn’t a traditional reducer/accumulator. Felt more akin to something like Map.pop/3, where I return some value alongside the “updated” data structure in a tuple (i.e. {a, state()}
• For args :: [term()], the state is added first, i.e. the state list needs to be the first argument passed to do_next/2/rle_next/2. So [n] effectively becomes [state, n] → rle_next(state, n) (similar to the recursive case).
• Agent.get_and_update/5 (and /3) expect the return to be {a, state()}, which is why the return is in that same ordered tuple (like mentioned above, similar to the likes of Map.pop/3)

This is also a reasonable use-case for the (often discouraged in production use) process dictionary

For sure. I chose Agent since common behaviors like get_and_update are provided “for free” and just what I was more familiar with.
But Process.put/2 for init_/1 could be cleaner since I think you can call it the same the first time and subsequent times.
Imagine you could do something like this:

defmodule RLEIterator do
  def init_(encoding), do: Process.put(__MODULE__, encoding)

  def next(n) do
    Process.get(__MODULE__)
    |> rle_next(n)
    |> then(fn {val, encoding} ->
      Process.put(__MODULE__, encoding)
      val
    end)
  end
 
  def rle_next(encoding, n)
  # ...
end