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.
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.
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
ReplyDeleteAlso, 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).
But in "if the second college is filled do that for same as above college " would that not increase complexity like
ReplyDeleteloop1-> 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!)
Someone must have surely written better algo. Thanks jason for finding it.
ReplyDelete- Keep coding :)