Interview Question for Software Engineer at Google:

Use a Max heap (a min heap where the x<=y operation is score(x) >= score(y)). It can be built in O(n) time. Extracting the maximum element (which is the root) take O(log(n)) , and you do it k times.

Anyway the idea is around sorting. There are tons of less efficient way but I am sure there is one or 2 more efficient way.

{{{
int score(char *str)
{
    int x = 0;

    while (*str)
    {
        x += (int)*str++;
    }

    return x;
}

int partition(int *scores, char **s, int n)
{
    int pivot = scores[0];
    char *ps = s[0];

    int small = n - 1;
    int large = 1;

    while (small > large)
    {
        if (scores[small] < pivot)
        {
            --small;
        }
        else if (scores[large] >= pivot)
        {
            ++large;
        }
        else
        {
            int temp = scores[small];
            scores[small] = scores[large];
            scores[large] = temp;
            char *st = s[small];
            s[small] = s[large];
            s[large] = st;
        }
    }

    if (scores[small] < pivot)
    {
        --small;
    }

    scores[0] = scores[small];
    s[0] = s[small];
    scores[small] = pivot;
    s[small] = ps;

    return small;
}
char ** TopKScorer(char **s, int n, int k)
{
    if (n <= k)
    {
        return s;
    }

    int *scores = new int [n];

    for (int i = 0; i < n; ++i)
    {
        scores[i] = score(s[i]);
    }

    int goal = k;
    char **cs = s;
    int *c_scores = scores;
    int length = n;

    int current = -1;

    while (1)
    {
        current = partition(c_scores, cs, length);

        if (current == goal)
        {
            break;
        }
        if (current < goal)
        {
            goal -= (current + 1);
            cs += (current + 1);
            c_scores += (current + 1);
            length -= (current + 1);
        }
        else if (current > goal)
        {
            length = current;
        }
    }

    delete []scores;
    return s;
}
}}}

/*return the position of the ith smallest element(index start with 0). scores[index][0=str_key 1=value]*/
    public static int quick_select(int[][] scores, int p, int r, int i) {

        if(i > r || i < p) return -1;

        if (p == r) {
            return scores[p][0];
        }

        int q = partition(scores, p, r);

        if (q == i) {
            return scores[q][0];
        }

        if (q > i) /*ith is in the left pile*/ {
            return quick_select(scores, p, q - 1, i);
        }

        return quick_select(scores, q + 1, r, i);

    }

    /*return the position of the selected pivot*/
    private static int partition(int[][] scores, int p, int r) {
        int x = scores[r][1];
        int q = p;

        for (int i = p; i < r; i++) {
            if (scores[i][1] < x) {
                int[] tmp = {scores[i][0], scores[i][1]};
                scores[i][0] = scores[q][0];
                scores[i][1] = scores[q][1];

                scores[q][0] = tmp[0];
                scores[q][1] = tmp[1];
                q++;
            }
        }

        int[] tmp = {scores[r][0], scores[r][1]};
        scores[r][0] = scores[q][0];
        scores[r][1] = scores[q][1];

        scores[q][0] = tmp[0];
        scores[q][1] = tmp[1];

        return q;
    }

Depending on the size of the string set, you have multiple possibilities here.
1. If the number of strings is reasonable and you can store the score for each one of these. Then the method you guys described, by using the idea from QSORT is perfect! :)
Complexity:
Time: O(M)
Space: O(M)
M is the number of strings! Good when M is reasonable as size.

2. If the set size is really big, and also you assume the strings come to you 1 by one, then the most efficient solution that I can see is to implement a Double Ended Priority Queue of maximum size N (Nth element). This can be done by using a Min-Max Heap.
The total complexity will be in this case:
Time: O(M * log (N))
Space: O(N)
M is the number of strings and N the Nth Element we want. Good method when N<<M

If N is small then have a binary tree of size N with smallest element at the head. Then check another string if it is bigger than the tree head remove the tree head and insert the new string. The tree stays size N. So complexity is O(M log(N)). For small N this is the most efficient, for large N this is of the same complexity as sorting.