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.
                                                          

Carrer cup - 4th edition

4.1

Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8. You can use any parentheses you’d like. 

 Answer: +3 -1 +(-3+6) = 8

9.2   The Game of Master Mind is played as follows:

- The computer has four slots containing balls that are red (R), yellow (Y), green (G) or blue (B). For example, the computer might have RGGB (eg, Slot #1 is red, Slots #2 and #3 are green, #4 is blue).

- You, the user, are trying to guess the solution. You might, for example, guess YRGB.

- When you guess right color for the right slot, you get a “hit”. If you guess a color that exists but is in the wrong slot, you get a “psuedo-hit”. For example, the guess YRGB has 2 hits and one pseudo-hit.

For each guess, you are told the number of hits and pseudo hits. Write a method that, given a guess and a solution, returns the number of hits and pseudo hits.

public class carrercup_9_2 {

    void printHitsPseudohits(String solution, String guess)
    {
        int hits =0, psudohits = 0;
      
        int position = 0;
      
        for (int i=0;i        {
          
            position = solution.indexOf(guess.substring(i, i+1));
          
            if(position == i) //guess at same position as that of solution
            {
                hits++;
            }
          
            else if(position != -1) // guess charecter is there in solution somewhere
            {
                psudohits ++;
            }
          
            position = 0;//resetting position
        }
      
        System.out.println("For solution = "+solution +" and guess = "+guess +" hits = "+hits+" psudohits = "+psudohits);
    }
}
 

DB2 to SQL Server conversion

I have been working lately on converting native queries in Java project from DB2 to SQL.

Apart from the date conversion one of the more tricky conversion was NEXTVALUE()  which had no equivalent in sql server 2008.


So here is how I did it.

Essentially we will create a table which wil have auto generated Ids that will supply us next value.

 Create table tableName ( [id] [int] IDENTITY(1,1) NOT NULL ON [PRIMARY]); 

In order not to save ids in table created above we need to have stored procedure which will get id and roll back the transaction.

CREATE procedure spName

 as

 begin     

declare @id int     

set NOCOUNT ON     

insert into tableName default values     

set @id = scope_identity()     

delete from tableName WITH (READPAST)



select @id as id



end

Additional links

Reset Identity Column Value in SQL Server (Source: http://www.howtogeek.com/howto/database/reset-identity-column-value-in-sql-server/ )

If you are using an identity column on your SQL Server tables, you can set the next insert value to whatever value you want. An example is if you wanted to start numbering your ID column at 1000 instead of 1.
It would be wise to first check what the current identify value is. We can use this command to do so:

DBCC CHECKIDENT (‘tablename’, NORESEED)

For instance, if I wanted to check the next ID value of my orders table, I could use this command:

DBCC CHECKIDENT (orders, NORESEED)

To set the value of the next ID to be 1000, I can use this command:

DBCC CHECKIDENT (orders, RESEED, 999)

Note that the next value will be whatever you reseed with + 1, so in this case I set it to 999 so that the next value will be 1000.
Another thing to note is that you may need to enclose the table name in single quotes or square brackets if you are referencing by a full path, or if your table name has spaces in it. (which it really shouldn’t)

DBCC CHECKIDENT ( ‘databasename.dbo.orders’,RESEED, 999)

Also calling stored procedure Seam project (Java) was a big task and has been accoplished in Entity class like code below:

Declaration in Model/Entity class:

import javax.persistence.NamedNativeQueries;

import javax.persistence.NamedNativeQuery;

import javax.persistence.SqlResultSetMapping;

import javax.persistence.Table;





@Entity



@SqlResultSetMapping(name="mappingName", columns=@ColumnResult(name="id")) 

@NamedNativeQueries({

          @NamedNativeQuery(name = NativeQueries.spName, 

                          query = NativeQueries.spName, 

                          hints={ @QueryHint(name = "org.hibernate.callable",value = "true"), @QueryHint(name = "org.hibernate.readOnly",value = "true")}, 

                          resultSetMapping = "mappingName")

          })

Calling a Stored Procedure:

  if(entityManager == null) {

            entityManager = (EntityManager)Component.getInstance("entityManager");

            if(entityManager == null) {

                log.fatal("entityManager is not available in seam context!");

            }

        }

        Query query = entityManager.createNamedQuery(spName);

        NEXTNUMBER (Integer) query.getSingleResult();