# How many possible interview slots

The table below illustrates the availability of four interviewers (π1, π2, π3, π4) at four time slots (π1, π2, π3, π4). A 1 in the table indicates that the corresponding interviewer is available at the corresponding time slot.

For example, the first interviewer, π1, is available at time slots π1 and π2.

Each interviewer may only take one interview and all four slots should follow sequentially, like π1 β π2 β π3 β π4.

What are all possible sequences of interviewers? Can this be generalised?

π1 π2 π3 π4
π1 1 1 1 1
π2 1 1 0 0
π3 0 1 1 0
π4 0 1 1 1
• Hesitant attempt to translate into English: a valid sequence of interviews is a collection of squares in the table, one in each column and one in each row, all marked "1". Commented Nov 10, 2014 at 18:35
• I fixed a little bit of the English. Commented Nov 11, 2014 at 1:21

There are 5 solutions to your particular problem.

1. $i_1 \rightarrow i_2 \rightarrow i_3 \rightarrow i_4$
2. $i_3 \rightarrow i_1 \rightarrow i_2 \rightarrow i_4$
3. $i_4 \rightarrow i_1 \rightarrow i_2 \rightarrow i_3$
4. $i_4 \rightarrow i_1 \rightarrow i_3 \rightarrow i_2$
5. $i_2 \rightarrow i_1 \rightarrow i_3 \rightarrow i_4$

This is a variation of the "Nurse Scheduling Problem". It is NP-Hard so we can't do much better than brute-force and some heuristics.

I have a Non-Deterministic Finite Automata here (a graph with directed and weighted edges):

So the problem becomes, how many ways are there to accept the word "1234f"? And equivalently, how many Hamiltonian paths are there from 0 to 5 where you must always take the cheapest edge that you haven't taken already (and f is the most expensive).

And finally, this particular problem is equivalent to the formal language:

$L = \left\{ w | w = s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_4 \land (\forall i \not= j. s_i \not= s_j) \land s_1 \in \{i_1,i_2,i_3,i_4\} \land s_2 \in \{i_1,i_2\} \land s_3 \in \{i_2,i_3\} \land s_4 \in \{i_2,i_3,i_4\}\right\}$

Explanation: L is a set of "words". A word can be denoted w. So L is a set of all w where w looks like 4 symbols separated by a β. The 4 symbols are $i_1,i_2,i_3,i_4$. The little sub-formula with $\forall$ means that all symbols used must be distinct (i.e. an interviewer may only be used once). Then the last part of the formula expresses what the constraints on the positions of the symbols are: e.g. $s_2 \in \{i_i,i_2\}$ means that only interviewers $1$ and $2$ can go second (which matches your diagram).

The size of $L$ is: $|L| = 5$

• What does the double circle around 5 mean. Is that graph related to puzzle 7 on this test by any chance matrix67.com/iqtest? Commented Nov 11, 2014 at 5:55
• @Mew Interesting link. No, it's not like that. It's from automata theory - look up "non-deterministic finite automata". The double circle signifies an accepting state. It's state machine basically - as well as a graph - as well as an "automaton". Commented Nov 11, 2014 at 5:58
• @atjoshi Sure. $L$ is a set of "words". A word can be denoted $w$. So $L$ is a set of all $w$ where $w$ looks like 4 symbols separated by a $\rightarrow$. The 4 symbols are $i_1,i_2,i_3,i_4$. The little subformula with $\forall$ means that all symbols used must be distinct (i.e. an interviewer may only be used once). Then the last part of the formula expresses what the constraints on the positions of the symbols are: e.g. $s_1 \in \{i_i...i_4\}$ means that any interviewer can go first (which matches your diagram). Does that help? Commented Nov 11, 2014 at 6:50
• @atjoshi don't be afraid to tick the answer if it works for you :p Commented Nov 11, 2014 at 8:53
• Its up there with a green tick .. :)
– Mr X
Commented Nov 11, 2014 at 9:00

I have created a simple solution using Tree

I. Step 1

Create a Tree of level 5 (n+1) and start point as Root Node

II. Step 2

Create possible route as a child by parsing matrix (Assumption 1 is true)

III. Step 3

Repeat step 2 until you reach at the end (Level S4)

IV. Step 4

Now all the path which lead to S4 level are unique So the possible arrangement will be :

• I1 - I2 - I3 - I4
• I2 - I1 - I3 - I4
• I3 - I1 - I2 - I4
• I4 - I1 - I2 - I3
• I4 - I1 - I3 - I2