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
                                   else
                                   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.
                                                          

3 comments:

  1. This is actually a real thing, the National Resident Matching Program (or NRMP). They describe their algorithm here: http://www.nrmp.org/res_match/about_res/algorithms.html

    Also, isn't your algorithm as described O(n)? As it only takes 2 rounds to match all 2 students. And same for the linked NRMP algorithm (similar, if not the same, to yours).

    ReplyDelete
  2. But in "if the second college is filled do that for same as above college " would that not increase complexity like

    loop1-> student loop will have student3 as example
    student3 wants seat in Hospital1 which is full
    loop2-> In hospital list student3 have higher priority that student2 which already have secured admission

    student2 will be kicked out and student 3 will have admission.

    loop3 -> student2 next priority after hospital1 example its hospital2
    Hospital2 is already full with student1

    loop 4-> find priority list of Hospital2 and we find student2 has better priority than student1

    so student1 is kicked off and sutdent2 will have admission

    loop5 -> go through list of preferences of hospitals for student1 for example hospital3

    loop6 -> as hospital3 is empty and has student1 will be placed

    so for 3 students i had 3! = 6 loops which brings me to complexity O(n!)


    ReplyDelete
  3. Someone must have surely written better algo. Thanks jason for finding it.


    - Keep coding :)

    ReplyDelete