How do I do this(Interview question)?

Questions / Help
1

I got this question in elixir interview

They started with giving me two arrays

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

I had to match 1st array with other array and if the numbers matched we have to write the indexes of it.

Like example
[1, 0] [2, 0] [3, 0]

Like this all that which is matching from the first array numbers to second array number we have to write all the indexes of it.

So I mostly write api’s and never used this kind of an example to write particular logics. So I couldn’t do it

I want to ask how can I write this logic here.

2

My first thought was I have a list and it doesn’t actually work like array. So I coudn’t think beyond that

3

Sorry, but I do not understand the requirement.

The example of [1, 0] [2, 0] [3, 0], doesn’t make sense. what is the index? In which list are those indexes looked up?

5 Likes
4

They are trying to match the 1st array with the 2nd array. If the numbers get matched like in the first array on 1st index there is 2 and on second array on 0th index there is 2. So we have to write the indexes of the both

5

I don’t see a 2 at index 1 ?!

1 Like
6

Sorry my bad oth index there is 2

7

I still don’t get it.

In your example [1, 0] [2, 0] [3, 0], what does each value mean exactly? How is it to interpret in the context of the a and b from your initial post?

2 Likes
8

Check the first array on index 1, 2 and 3 there is 2

Now check the second array there is 2 on oth index. For that they have written like that

[1,0] [2,0] [3,0]

9

I would do this by creating two maps where keys of a map will be values of the array and values of map will be indexes where they are in the “array”. Then iterate(through flat_map i guess) one of this map and check if the same key exists in another one, if no - just skip, if exists - multiplicate two arrays with indices.

This would be O(N + M) complexity

If we iterate them one by one checking in process, that would be O(N*M) complexity

1 Like
10

So [x, y] means "The value of a at index x is also to be found at index y in list b"?

How do you deal with multiple occurences?

Though looks like a classic fold over a with a Enum.find or something similar over b.

1 Like
11

This is interesting.

12

can you create some example?

13

ok, 5 min

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

map1 = list1
|> Enum.with_index
|> Enum.reduce(%{}, fn {value, index}, map ->
  Map.update(map, value, [index], fn indicies -> [index | indicies] end)
end)

map2 = list2
|> Enum.with_index
|> Enum.reduce(%{}, fn {value, index}, map ->
  Map.update(map, value, [index], fn indicies -> [index | indicies] end)
end)

map1
|> Enum.flat_map(fn {value, indicies} ->
  if Map.has_key?(map2, value) do
    for idx1 <- indicies,  idx2 <- map2[value], do: [idx1, idx2]
  else
    []
  end
end)

output is:

[
  [0, 0],
  [5, 1],
  [4, 1],
  [3, 1],
  [2, 1],
  [1, 1],
  '\f\v',
  [12, 2],
  '\b\v',
  [8, 2],
  '\v\n',
  [11, 3],
  '\a\n',
  [7, 3],
  '\t\t',
  [9, 4],
  [6, 9],
  [6, 4],
  '\n\b',
  '\n\a',
  [10, 6],
  [10, 5]
]

It’s just a scetch, you should refactor it massively :slight_smile:

15

In a recursive way you could solve it like this:

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
16

Can you make two smaller lists – say, 4-5 elements long – and illustrate the requirements? I still don’t get what is required. :sweat_smile:

4 Likes
17

Okay Sure.
So suppose you have list 1 = [1, 1, 2, 2]

and you have list 2 = [2, 2, 3, 3]

Now you have to match these two lists and if the common term’s matches then you have to give their indexes

In this case
[2, 0] means that 2 which is an index for (list 1) has a 2 value, and 0 is the index of the (list 2) which has a value 2.

so that’s why [2, 0]

I hope this helps :slight_smile:

1 Like
18

Did you test this? I’m getting some error

19

Thanks. I never used this flat_map. Even though I wouldn’t able to solve this in 10 - 15 mins in an interview

1 Like
20

So is [2, 0] the final result expected when you run the code through both lists? If not, can you give us the entire expected output?

1 Like