edited by
14,220 views
52 votes
52 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”$

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. Only one
  2. Only two
  3. Only three
  4. All four
edited by

9 Answers

1 votes
1 votes

We have there arrays, Array A with input string, Array oldc which tells which characters of the input string needs to be replaced and Array newc tells with which characters we will replace the characters of A.

Ex: A=abcde, oldc = abc and newc = dab.

Every occurance of a in A need to be replaced by d, each b will be replaced with a, each c with b, then we will get our output .

Input A=abcde, expected output A = dabde

But because there is a flaw(program not designed well) in the program, because of which when we give a input, we are not getting expected output.

Lets see where the program fails to give expected output.

Lets take 3rd test case and A = bcdea

oldc = bca, newc = cda; the expected output is A=cddec; lets see what program gives as output

i=0, j=0 ==> a[0] == oldc[0] ==> a[0] = new[0]  = c ;

After this iteration updated string A=ccdea and now A[0] = c;

i=0, j=1 ==> a[0] == oldc[1] ==> a[0] = new[1]  = d  

After this iteration updated string A=dcdea and now A[0] = d;

If you notice, A[0] first changed to c and again to d which is the flaw here, we are expected to change only once but change is happening twice. 

This is because when first character is changed to something , that something is again present in oldc after current index which is making it to change again when we reach that index, which we don’t want to happen.

This will happen in 3,4 test cases and not in 1,2 test cases, that is why 3,4 test cases detect the flaw.

see this image for why 3,4 can detect the flaw.

image credits: 

In 3,4 test cases the changed character is again present in oldc array after current index, which makes the characted to change again.

Answer:B) only two

0 votes
0 votes
The flaw here is in say oldc= xyz and newc = yvw here if in, A contains x at 0th position it will be replaced by y(for x=0,j=0). However when j=1, again that y will be replaced by v (for x=0,j=1) which is wrong.

By now we get the idea that  if 'a' is replaced by say 'x' then x should appear in right of a in oldc.

Test case1  and case2: the above mentioned condition doesn't occur here. Therefore flae will not be detected.

In test3, 'b' is replaced by c and c appears in right of b in oldc. Therefore flaw will be detected.

In test 4, 'a' is replaced by 'b' and b appears rigtr of a in oldc. Therefore flaw will be detected.

Answer (B)
0 votes
0 votes

The correction in the code should be that once a character is replaced, it should not be modified again because that will disturb the intended mapping. So with just the addition of a break statement, the code will work fine.

Now for analysis check for the test cases in which the same character can be replaced multiple times.

Example:

 

 

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];
                  break;     //notice that break will allow replacement only once
              }  
}
–3 votes
–3 votes

51 answer should be D option that is 4 only
test case 3 can't detect its flaw because "bca"(i.e. 3) is not there in the INPUT!

:(
 

Answer:

Related questions

27 votes
27 votes
2 answers
2
41 votes
41 votes
4 answers
4
Arjun asked Sep 23, 2014
12,135 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)$...