The procedure given below is required to find and replace certain characters…

20132013

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each. However, the procedure is flawed.

void find_and_replace(char *A, char *oldc, char *newc) {
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 3; j++)
            if (A[i] == oldc[j])
                A[i] = newc[j];
}

The procedure is tested with the following four test cases:

  • oldc = "abc", newc = "dab"

  • oldc = "cde", newc = "bcd"

  • oldc = "bca", newc = "cda"

  • oldc = "abc", newc = "bac"

The tester now tests the program on all input strings of length five consisting of characters 'a', 'b', 'c', 'd' and 'e' with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

  1. A.

    Only one

  2. B.

    Only two

  3. C.

    Only three

  4. D.

    All four

Attempted by 26 students.

Show answer & explanation

Correct answer: B

Concept

The inner loop scans oldc in increasing index order and overwrites A[i] in place. Because the just-written character stays in A[i] for the rest of the same inner loop, a single character can be replaced more than once in one pass. A test pair (oldc, newc) can expose this flaw if and only if some replacement character is matched again later, i.e.

there exist indices j < k with newc[j] == oldc[k]. When that holds, an input character equal to oldc[j] is first set to newc[j], then re-matched at index k and overwritten again, giving a final value that differs from the intended single mapping.

Apply the condition to each pair

oldc

newc

Chain? (newc[j] = oldc[k], j<k)

Exposes flaw

abc

dab

d,a,b never appear later in abc

No

cde

bcd

b,c,d: c is oldc[0] only (not later)

No

bca

cda

newc[0]='c' = oldc[1]='c'

Yes

abc

bac

newc[0]='b' = oldc[1]='b'

Yes

Trace the two that chain

  1. bca / cda: take input character 'b'. At j=0, 'b' matches oldc[0] and becomes 'c'. At j=1, that 'c' matches oldc[1] and becomes 'd'. Intended b->c comes out as b->d — flaw observed.

  2. abc / bac: take input character 'a'. At j=0, 'a' becomes 'b'. At j=1, that 'b' matches oldc[1] and becomes 'a'. Intended a->b comes out as a->a (no net change) — flaw observed.

Cross-check

For abc/dab and cde/bcd, no replacement character reappears at a strictly later oldc index, so no input string can trigger a second overwrite; their output always equals the intended one-shot mapping. Hence exactly two of the four test pairs can capture the flaw.

Explore the full course: Gate Guidance By Sanchit Sir