7
$\begingroup$

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
$\endgroup$
2
  • $\begingroup$ 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". $\endgroup$
    – Lopsy
    Nov 10 '14 at 18:35
  • $\begingroup$ I fixed a little bit of the English. $\endgroup$
    – warspyking
    Nov 11 '14 at 1:21
10
+500
$\begingroup$

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):

enter image description here

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$

$\endgroup$
6
  • 1
    $\begingroup$ What does the double circle around 5 mean. Is that graph related to puzzle 7 on this test by any chance matrix67.com/iqtest? $\endgroup$
    – Kenshin
    Nov 11 '14 at 5:55
  • 2
    $\begingroup$ @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". $\endgroup$
    – d'alar'cop
    Nov 11 '14 at 5:58
  • 2
    $\begingroup$ @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? $\endgroup$
    – d'alar'cop
    Nov 11 '14 at 6:50
  • 1
    $\begingroup$ @atjoshi don't be afraid to tick the answer if it works for you :p $\endgroup$
    – d'alar'cop
    Nov 11 '14 at 8:53
  • 1
    $\begingroup$ Its up there with a green tick .. :) $\endgroup$
    – Mr AJ
    Nov 11 '14 at 9:00
3
$\begingroup$

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)

Tree Structure

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
$\endgroup$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.