Question 7 of 8: File I/O

Question 7: File I/O

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Three text files, each already sorted alphabetically, each name on its own line, lengths unknown in advance. Find. Every name that appears in all three files, printed once each.

Approach. Because all three files are already sorted, a single-pass three-way merge (analogous to the merge step of merge sort) finds the intersection in linear time — no need to load any file fully into memory or use a hash set. Keep one "current name" cursor per file; whenever all three agree, print and advance all three; otherwise advance only the cursor(s) sitting on the alphabetically smallest current name, since that name cannot possibly appear later in the other file(s) it has fallen behind.

#define MAXNAME 100

int read_name(FILE *fp, char *buf) {
    if (fgets(buf, MAXNAME, fp) == NULL) return 0;
    buf[strcspn(buf, "\n")] = '\0';      /* strip trailing newline */
    return 1;
}

void find_common(FILE *f1, FILE *f2, FILE *f3) {
    char n1[MAXNAME], n2[MAXNAME], n3[MAXNAME];
    int r1 = read_name(f1, n1), r2 = read_name(f2, n2), r3 = read_name(f3, n3);

    while (r1 && r2 && r3) {
        if (strcmp(n1, n2) == 0 && strcmp(n2, n3) == 0) {
            printf("%s\n", n1);
            r1 = read_name(f1, n1);
            r2 = read_name(f2, n2);
            r3 = read_name(f3, n3);
        } else {
            /* advance every cursor currently on the smallest name */
            char *min_name = n1;
            if (strcmp(n2, min_name) < 0) min_name = n2;
            if (strcmp(n3, min_name) < 0) min_name = n3;

            if (strcmp(n1, min_name) == 0) r1 = read_name(f1, n1);
            if (strcmp(n2, min_name) == 0) r2 = read_name(f2, n2);
            if (strcmp(n3, min_name) == 0) r3 = read_name(f3, n3);
        }
    }
}

Each cursor advances at most once per line of its own file and is never rewound, so every name in every file is examined at most a constant number of times — the whole scan costs $O(n_1+n_2+n_3)$ regardless of how large the files are, versus an $O(n_1 \cdot n_2 \cdot n_3)$ naive triple-nested search that compared every name against every other name.