what is the best, efficient approach to rank the candidates

Question

There are N candidates who sign up answer a series of multiple-choice questions. Design a efficient method to evaluate the answer and rank the candidates.

vector <string> Evaluate (const string& answer, const vector<string>& param)
{
    // answer - will have the answer for multiple choice question.
    // like X X X X X where each X is a capital letter (A-D)
    // (e.g) A B A C D

    // param will have candidate name followed by his/her answer
    // (e.g) param[0] - "Foo A C A C D"
    // param[1] - "Bar D D A C B"

    // return candidates name with highest % of mark in result[0], 
    // next highest in result[1] and so on.
}

One approach that I could think of is, tokenize the answer & param and compare it. But I am looking for any better approach. Any suggestions ?

PS: This is not a homework. Came across this question in topcoder

It's possible to do this without making copies of the data. Given your disclaimer about tokenizing, you might want to change your function signature to return a vector of the indices. — David Nehme, Sep 06 '11 at 02:15

Seth Carnegie · Answer 1 · 2011-09-06T02:00:56.223

One solution is going through all the candidates and grading their answers on a scale of 0 - 5 where 0 is perfect, 1 is 1 answer wrong, etc. After grading each candidate, insert it into a list. Then after grading all the candidates, sort the list by grade (or sort them as you're inserting them).

Alternatively, you could add them to a binary search tree while adding them. This would probably be faster than inserting them into a list and sorting it.

score 1 · Accepted Answer · answered Sep 06 '11 at 02:08

1

You can compute the score for a single candidate without tokenizing, if you assume a single space between answers. First, search for the first space to skip then name, then pass the remaining string to the following function

int compute_score(const string& answer_key, const char answer[])
{
  int score = 0;
  for (unsigned i = 0; i < answer_key.size(); i+=2) {
    score += answer[i]==answer_key[i];
  }
  return score;
}

answered Sep 06 '11 at 02:08

David Nehme

21,379
8
78
117

@Ganesh what is your definition of tokenizing? – Seth Carnegie Sep 06 '11 at 02:30
@Seth I meant something like this as tokenize [link](http://stackoverflow.com/questions/53849/how-do-i-tokenize-a-string-in-c) – Ganesh M Sep 06 '11 at 02:36

score 0 · Answer 3 · answered Sep 06 '11 at 02:07

0

Another idea would be of using a static variable to Store the name of the candidate with the highest % so far. Update the static variable's value on further function call with the student's name if he has the higher % than the current Candidate,, Finally, the Student with the Highest mark will be in the static variable display that value.

This would be a better solution if you don't want the list of all Candidates % and also have a Permission to use a static variable.

answered Sep 06 '11 at 02:07

vivek_jonam

3,237
8
32
44

But the function should return all candidate names in their % of score order not just the highest % candidate. – Ganesh M Sep 06 '11 at 02:09
kidly update your question it says // return candidate name in highest % of mark. – vivek_jonam Sep 06 '11 at 02:11
Sorry about that.. changed the description. – Ganesh M Sep 06 '11 at 02:14

what is the best, efficient approach to rank the candidates

3 Answers3