How do I do this(Interview question)?

Questions / Help
21

No It was just a example

list 1 = [1, 1, 2, 2]
list 2 = [2, 2, 3, 3]

this will be the final output
[2, 0], [3,0], [2, 1], [3, 1]

22

I took a “quick” stab at it with plain recursion:

defmodule Y do
  def do_it(list1, list2) do
    index_map = map_items_to_indexes(list2)
    collect_matches(list1, index_map) |> Enum.reverse()
  end

  defp map_items_to_indexes(list, acc \\ %{}, index \\ 0)
  defp map_items_to_indexes([], acc, _), do: acc
  defp map_items_to_indexes([first | rest], acc, index) do
    acc = Map.update(acc, first, [index], & [index | &1])
    map_items_to_indexes(rest, acc, index + 1)
  end

  defp collect_matches(list, index_map, matches \\ [], index \\ 0)
  defp collect_matches([], _, matches, _), do: matches
  defp collect_matches([first | rest], index_map, matches, index) do
    indexes = Map.get(index_map, first, []) |> Enum.reverse()
    matches =
      for match_index <- indexes, reduce: matches do
        matches -> [[index, match_index] | matches]
      end
    collect_matches(rest, index_map, matches, index + 1)
  end
end

list1 = [1, 2, 2, 2, 3, 4, 4, 5, 6, 6]
list2 = [2, 4, 1, 1, 3, 3, 4, 5, 6]

Y.do_it(list1, list2)
|> IO.inspect(charlists: :as_list)

Outputs:

[
  [0, 2],
  [0, 3],
  [1, 0],
  [2, 0],
  [3, 0],
  [4, 4],
  [4, 5],
  [5, 1],
  [5, 6],
  [6, 1],
  [6, 6],
  [7, 7],
  [8, 8],
  [9, 8]
]

If you don’t need to guarantee the matches are ordered, remove the Enum.reverses :slight_smile:

1 Like
23

Absolutely my error, i have written it without testing and i missed one clause, here you have:

defmodule CollectIndex do
  def something(list1, list2) do
    collect_index(list1, list2, [], 0)
  end
  
  defp collect_index([], list2, results, _index1) do
    results
  end
  
  defp collect_index([head | tail] , list2, results, index1) do
    coincidences = get_coincidences(head, list2, index1)
    newresults = results ++ coincidences
    collect_index(tail, list2, newresults, index1+1)
  end
  
  
  defp get_coincidences(item, items_list, index) do
    get_coincidences(item, index, items_list, [], 0)
  end
  
  defp get_coincidences(item, index, [], coincidences, _index2) do
    coincidences
  end
  
  defp get_coincidences(item, index, [item | tail], coincidences, index2) do
    newcoincidences = [{index, index2} | coincidences]
    get_coincidences(item, index, tail, newcoincidences, index2+1)
  end

  defp get_coincidences(item, index, [noitem | tail], coincidences, index2) do
    get_coincidences(item, index, tail, coincidences, index2+1)
  end
end
24

Another possible solution

a = [1, 2, 2, 2, 3, 4, 4, 5, 6, 6]
b = [2, 4, 1, 1, 3, 3, 4, 5, 6]


# map with key as the value and value as a list of indexes where it occurs
{first_indexes_map, _} =
  Enum.reduce(a, {%{}, 0}, fn element, {map_acc, ind} ->
    {Map.update(map_acc, element, [ind], fn prev -> [ind | prev] end), ind + 1}
  end)

# here we're just producing the final list of indexes,
# but the result looks a bit nonsensical since there's no other information
# of what the resulting indexes refer to
{final_list, _} =
  Enum.reduce(b, {[], 0}, fn(element, {acc, ind}) when is_map_key(first_indexes_map, element) ->
      {
        Enum.concat(
          acc,
          Enum.reduce(first_indexes_map[element], [], fn f_el, inner_acc -> [[f_el, ind] | inner_acc] end)
        ),
        ind + 1
      }

    _, {acc, ind} ->
      {acc, ind + 1}
  end)

final_list

iex(11)> [
  [1, 0],
  [2, 0],
  [3, 0],
  [5, 1],
  [6, 1],
  [0, 2],
  [0, 3],
  [4, 4],
  [4, 5],
  [5, 6],
  [6, 6],
  '\a\a',
  '\b\b',
  '\t\b'
]

If we wanted to add additional info, as for instance what the value is for the accumulated indexes, we could use a similar logic as the first reduce on the second part:

{final_map, _} =
  Enum.reduce(b, {%{}, 0}, fn
    (element, {acc, ind}) when is_map_key(first_indexes_map, element) ->
      pairs = Enum.reduce(first_indexes_map[element], [], fn f_el, inner_acc -> [[f_el, ind] | inner_acc] end)
      {Map.update(acc, element, pairs, fn prev -> Enum.concat(prev, pairs) end) , ind + 1}

    _, {acc, ind} ->
      {acc, ind + 1}
  end)

final_map

%{
  1 => [[0, 2], [0, 3]],
  2 => [[1, 0], [2, 0], [3, 0]],
  3 => [[4, 4], [4, 5]],
  4 => [[5, 1], [6, 1], [5, 6], [6, 6]],
  5 => ['\a\a'],
  6 => ['\b\b', '\t\b']
}

Assuming matches don’t remove the possibility of the same values being matched further down again.

25

Once I finally understood the problem, a for comprehension works nicely

iex(66)> list_1 = [1, 1, 2, 2]
[1, 1, 2, 2]
iex(67)> list_2 = [2, 2, 3, 3]
[2, 2, 3, 3]
iex(68)> for {a, an} <- Enum.with_index(list_1), {b, bn} <- Enum.with_index(list_2), a == b, do: [an, bn]
[[2, 0], [2, 1], [3, 0], [3, 1]]

if the ordering of the results is important, then reversing the order of the generator results in:

iex(69)> for {b, bn} <- Enum.with_index(list_2), {a, an} <- Enum.with_index(list_1), a == b, do: [an, bn]
[[2, 0], [3, 0], [2, 1], [3, 1]]
18 Likes
26

The first step in solving a problem is understanding the problem. When you have a hard time writing down whats expected in prose or even as a (complete and correct) example you have no hope to solve the problem.

6 Likes
27

Next time someone asks “bUt HoW dO yOu Do ThInGs WiThOuT lOoPs” to detract Elixir I’m showing them this :rofl:

29

really nice. Thankyou for you help

30

I always try to assume the best intent from others, so I read it as “the better you are able to describe the problem, the easier it is to come up with a solution”, and the opposite is also true. So if you are stuck, try explaining what should be done, once it’s clearly defined coding the solution is mostly a translation exercise.

This is a good exercise, get stuck, start writing a question in the most detailed way you can(what you would like to do, what have you tried and failed), and I can assure you the answer comes by itself in 90% of the cases. If you’re in that 10% of the cases where you don’t come up with a possible solution by doing this exercise, you would already have a solid question that other people can answer more easily.

Rubber duck debugging at it’s finest.

4 Likes
31

I also had very hard time understanding what you where asking for and what the numbers where in the result. Something else that was missing was if that result format was what they asked for or something you think it should have been?

Would output like this have been fine for them that only contains the indexes?

[
  [2, 3], 
  [0], 
  [0],
  [0], 
  [4, 5], 
  [1, 6],
  [1, 6],
  [7],
  [8],
  [8]
]

You get that by running this code

a = [1, 2, 2, 2, 3, 4, 4, 5, 6, 6]
b = [2, 4, 1, 1, 3, 3, 4, 5, 6]

a
|> Enum.map(fn a_val ->
    b
    |> Enum.with_index()
    |> Enum.filter(fn {b_val, _} -> b_val == a_val end)
    |> Enum.map(fn {_, idx} -> idx end)
end)
2 Likes
32

Tbh: even if you solved the problem, this attitude or lack of correct communication would destroy your career. If you ignore his advice, that is “not nice of you” and “I don’t think this is the place for you.”

1 Like
33

@Maxtonx may this help

a = [1, 2, 2, 2, 3, 4, 4, 5, 6, 6]
b = [2, 4, 1, 1, 3, 3, 4, 5, 6]

a = Enum.with_index(a)
b = Enum.with_index(b)

result =
 Enum.reduce(a, [], fn {want, idx}, acc ->
   acc ++ Enum.flat_map(b, fn {wantb, idxb} ->
          if want == wantb do
            [[idx, idxb]]
          else
            []
         end
  end)
end)

outputs

[[0, 2], [0, 3], [1, 0], [2, 0], [3, 0], [4, 4], [4, 5], [5, 1], [5, 6], [6, 1],......]
34

So I think this has been well answered, but perhaps a summary of the key things to research:

  • Enum.with_index

Adds indexes to your list values (technically by wrapping each item into a tuple). This means you can now pass this to some subsequent operation with the ordering known. Probably we will need to do this to both lists since we will need to show indexes from both lists

So then you are faced with a choice. You can either do a “cross product” of both arrays, ie an “N x M” cost, ie phrased another way, you get all possible permutations of both arrays and just spit out an answer if they both match. This can be done neatly with the “for comprehension” for example

You could optimise the above if you knew that the lists were sorted, but it basically has a relatively high cost as the size of the lists gets larger and no doubt that was question 2 in the interview

The second option is the inspiration to optimise the operation is to use a map on one of the lists, so your keys are the items and the contents of the map are the locations that item is found in the map. So you say in array a, “item “2” is found in positions [1,2,3]”, ie

%{1: [0, 2], 2: [1,2,3], etc}

Then you run through the other list (with indexes), looking up in the map if there are any matches in the other list

The cost to build the map is around the log(N) kind of cost, plus the second sweep through the second list, so I guess the cost of this is lower in general, I guess it’s O(2N log(N)) ish? Might be a log(log(N)) in there as well, can’t decide? Lost in the implementation wash of how Elixir will implement maps anyway

Note that adding indexes is no different to a recursive strategy where you do the whole of the optimised strategy in some single loop. You can always merge the steps together, but sometimes it’s nice to split the steps up for clarity.

I hope you implement both of these algorithms yourself. Perhaps use a random number generator and benchee and let us know how the timings compare! Good luck!

35

The funny thing is, I don’t know if I’d get points or get docked points for my understanding of the ask.

I’d expect the final answer to be a list of indexes (zero-based) where the numbers in each list matched (4,6,7, and 8).

iex code,

a = [1, 2, 2, 2, 3, 4, 4, 5, 6, 6]
b = [2, 4, 1, 1, 3, 3, 4, 5, 6]

set_a = (Enum.with_index(a) 
	|> MapSet.new)

set_b =	(Enum.with_index(b) 
	|> MapSet.new)

result = 
	(MapSet.intersection(set_a, set_b) 
	|> Enum.map(&(elem(&1,1))) 
	|> IO.inspect(label: "Matching indexes"))

# Matching indexes: [4, 6, 7, 8]

Also, I had to lookup MapSet in the docs because I didn’t know which module handled intersections.