edited by
5,228 views
35 votes
35 votes

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?

  1. None
  2. $2$ only
  3. $3$ and $4$ only
  4. $4$ only
edited by

4 Answers

Best answer
13 votes
13 votes
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.
edited by
33 votes
33 votes

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)

edited by
2 votes
2 votes

 

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

edited by
2 votes
2 votes

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.

Answer:

Related questions

52 votes
52 votes
9 answers
1
27 votes
27 votes
2 answers
2
41 votes
41 votes
4 answers
4
Arjun asked Sep 23, 2014
12,117 views
Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?$O(1)$$O(\log n)$...