GATE CSE 2013 | Question: 51

Question

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.

1. $oldc = “abc”, newc = “dab”$     
2. $oldc = “cde”, newc = “bcd”$
3. $oldc = “bca”, newc = “cda”$     
4. $oldc = “abc”, newc = “bac”$

If array $A$ is made to hold the string “$abcde$”, which of the above four test cases will be successful in exposing the flaw in this procedure?

• A. None
• B. $2$ only
• C. $3$ and $4$ only
• D. $4$ only

Comments

See this:

https://gateoverflow.in/1557/Gate-cse-2013-question-50?show=365258#a365258

Answer 1

The test cases $3$ and $4$ are the only cases that capture the flaw. The code does not work properly when an old character is replaced by a new character and the new character is again replaced by another new character. This does not happen in test cases $(1)$ and $(2),$ it happens only in cases $(3)$ and $(4).$

Correct Answer: C.

Answer 2

Here when the element of array $A$ and $oldc$ match , we replace that array element of $A$  with  array element of $newc$ . For every element of $A$ array update occurs maximum one time.

Similarly for (2) array element of $A$ has updated with array element of $newc$ less than or equal to one time,

Now, for (3) when $i=0$ , value of $A$ match with $oldc[2]$ i.e.'$a$' , and replace with $newc[2]$ i.e. also '$a$'. So, no changes

when $i=1$ value of array $A[1]=$'$b$' 

match with $oldc[0]=$'$b$' and replace with $newc[0]=$'$c$'.

Now, $A[1]=$'$c$' which equal with next element of $oldc[1]=$'$c$'.

So, replace again with $newc[1]=$'$d$'.

Now, we can say here in array $A[1]$ value replace with $newc[0]$ value , and that $newc[0]$ value replace with next $newc[1]$ value.

  

Similarly for (4) here $2$ times replacement for $A[0]$ with element $newc[0]$ and $newc[1]$

Updating of $newc$ value with another $newc$ value is calling flaw here

So Ans (C)

Comments

@ srestha plz explain the meaning of "exposing the flaw"

---

i m neither getting question nor answer , plz @bikram sir help!!!

---

the logic is simple- If the updated value matches again with any of the character in the the oldc array, it will be updated again and that's the flaw we are talking about.

Answer 3

 

I have tried to display all the iterations for each options below.  

In option no 3 -  If your replaced/updated newc[i] (here 'C') matches with next oldc[j] ('C'), so it is causing the value to get replaced again, which is not expected. Similar happenings for option 4

Comments

exposing of flaw: If the updated value matches again with any of the character in the the oldc array, it will be updated again.

In ur diagram...if updated value is match than its flaw.

Am I right ??

Answer 4

Ans – (C)

In simple words, since a break statement is not used inside the inner j loop, so even after finding and updating A[i], the inner j loop will keep running and comparing the updated A[i] with every oldc[j] which should not happen and is the actual flaw. 

In Test cases 1 and 2, the updated value of A[i] will not further match with any oldc[j] 

but in Test cases 3 and 4 it does match and updated value of A[i] will again match with one of the remaining oldc[j] value and hence it will get updated again resulting in an incorrect updated string.

If break statement was used inside the j loop in the if (A[i] == oldc[j]) condition after updating A[i]=newc[j] then the flaw would not exist.