stackcats

How to use GenServer in leetcode?

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？

11 comments

#genserver #leetcode

0 1045 11

2024-04-16 00:27:36 UTC

First Post!

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

Post #1

Most Liked

mudasobwa

Creator of Cure

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.

Post #5

Last Post!

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

Post #11