Find m elements in n arrays, choosing at most 1 element from each of n arrays
I have n
arrays, each containing an arbitrary number of integers. Duplicates are possible inside the array ( [1,1,2]
cannot be one of the arrays n
).
I also have an integer array of size m
that is filled with integers from 1
to m
(value_of_an_array_entry = array_index + 1). Example: m = 4
corresponding array [1,2,3,4]
.
My question is:
For given n
and is m
it possible to find every element in an array m
by selecting at most 1 element from each array n
?
Example:
n = 3, m = 3,
Arrays n
: [1]
, [1, 2]
,[2, 3]
The output should be: Yes
(because we can find every element in an array m
by selecting at most 1 element from each array n
. Look at the arrays n
and select 1
from the first array, 2
from the second and 3
from the third array.)
This is an interview question, I got a hint to think about Max's flow issue (I don't understand how this helps me).
source to share
You can build a graph as follows: The graph is divided into left and right parts. The left side contains n
vertices that represent arrays n
. The right side contains the m
vertices that represent numbers m
.
Then, let's look at these arrays n
. If the element k
is in the i
-th array , we draw an edge between the i
-th vertex on the left and the k
-th vertex on the right. Our goal is to select m
edges so that each of the vertices m
on the right is covered with edges m
exactly once, and the vertices on the left are covered at most once. This is a bipartite graph coincidence problem that can be solved by many algorithms, including max flow.
source to share
I think the recursive method should do this.
- If m is an empty list, PASS
- Otherwise find elements from m containing the first element m
- if not found: FAIL
- for each found:
- this member m is part of the PASS if there is a PASS for
m' = tail(m)
andn' = other members of (n)
- this member m is part of the PASS if there is a PASS for
I haven't tested this, but:
public boolean check(List<Integer> m, List<List<Integer>> n) {
if (m.isEmpty()) {
return true;
}
int head = head(m);
List<Integer> tail = tail(m);
for (List<Integer> nMember : n) {
if (nMember.contains(head) && check(tail, nMinus(n, nMember))) {
return true;
}
}
return false;
}
Suggested methods:
-
head()
returns the first element of the passed list. -
tail()
returns the passed list with the first element removed. -
nMinus()
returns a view or a copyn
with deletednMember
. He shouldn't changen
.
You should use immutable collections, or at least treat them as immutable. Guava provides classes that are likely to be useful. But you could trivially knock out a wrapper class ListOmitting
that can be implemented nMinus()
without Guava.
I cannot say for sure that he is not too rude, but he "feels" an adequately effective response to my answer.
source to share