Wednesday, August 28, 2013

Match Making Algorithm

My friend is interviewing for Cerner Corporation and one of the questions asked was how will you design a match making algo for hospitals and students where

Hospitals rank students as per their preference
Students ranks hospitals as per their preference
Number of positions in hospitals and number of students are equal so student will end up going in hospital.

Given :

Student1 ->  Hospital1 - 1(pref) , Hospital2(pref)
Student 2 -> Hospital1 -1(pref) ,  Hospital2 (pref)

Hospital1 -> Student2 - 1(pref), Student1 - 2(Pref)
Hospital2 -> Student 1 - (pref) , Student 2 - 2 (pref)

We need a list of hospitals in rank stating with super awesome to lower

for each student
                   check preference in acceding order
                                  if hospital has space accommodate student
                                   check the internal ranking for hospital and see if current student has higher preference
                                              if so kick a student with lowest rank as per hospital list who still has got admission to his next best preference

                                                        if the second college is filled do that for same as above college
                     end the student loop

The algo will be very well written recursively

Tracing given example

Hospital one = empty , Hospital 2 =  empty both having capacity of accommodating 1 Student each

----Student1 wants in Hospital 1 -> go for it

----Student 2 wants in Hospital 1 but Hospital 1 can only accommodate one student so checking internal list -> Student2 is more preferred so Student 1 has to go to Hospital 2

Final Solution

Hospital1 will have Student2
Hospital2 will have Student1

Algorithm is more biased to students as Students preferred list is first checked.

Complexity of Algorithm would be O(n!) which is quite high probably someone can do it better.

Please Comment will love to hear more about it.