Megasoft Interview Question for Testing / Quality Assurances


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
1
of 3 vote

Talked to her/authour, she didn't want want anything except strlen used (and wanted the logic to be easy just for her to learn to do brute force):

She dipped from collabedit session after I typed this mess so I'm going to post it here and give her the homework of fixing the 1000 bugs:

// substring function:  will be used by this problem 
// returns index of FIRST starting point of pattern[ ] inside text[ ]
// or returns -1 if pattern[ ] not found in text[ ]
int substring(char text[], char pattern[])
{
    int s;
    int i;    
    for(s=0; s<=strlen(text)-strlen(pattern); s++)            
    {    
        for(i=0; i<strlen(pattern); i++)
        {
            if( pattern[i] != text[s+i] )
                break;
            if (i==strlen(pattern))
                return s;  //found starting at index s of text[ ] string
        }
    }
    return -1; //not found
}


//main function for replace string problem posed by Reena (she wants all "manual" work, so no library calls, except strlen)
int main(void)

    char *mainstring ="ABCDADXYZDADABC";
    char *fromstring ="DAD";
    char *tostring   ="REENA"   //for our example, we will get "ABCREENAXYZREENAABC" as result, ok???
    
    int N = strlen(mainstring);  //length of main string
    int M = strlen(fromstring);  //length of substring to find
    int T = strlen(tostring);    //length of replacement string
    
    int *positions = malloc(N);  //store positions where "fromstring" is substring of "mainstring"  (picked N size for convenience only)
    char *result = malloc(N*10);  //just create a result array 10 times larger than starting string (you can improve this later with calculation)
    
    // above ^^^ you should really check return value of mallocs for errors too (excluded for now)
    
    int numpos=0;  //index into positions array
    int t=0;  //index into mainstring[ ]  ... t=0 at start because we want to start searching mainstring from start
    int s;    //index of returned substring from every while loop iteration below
    
    while( (s = substring( &mainstring[t] , fromstring) )!= -1 ) //search mainstring[] from 't' index (so we don't hit earlier matches)
    {
        positions[numpost++] = s;  //storing the position of substring 
        t=s+M;  //KEY POINT:  we increase t to s+M so the next "substring" call in while loop will only check past the original position
    }

    /* NOW: after the above while loop we have
        1) positions[] array will have the positions of all the substrings to be replaced
        2) numpos will be the number of positions/substrings we found in the mainstring
     */
     
    // REENA: you can calculate actual needed result[ ] array size at this point and improve code at your liking 
    
     
    // now to build the result array:
    int i=0;  // iterates over positions
    
    int resultfill=0; //position of result array we are filling currently
    int maingrab  =0; //position of mainstring we are getting characters from currently
    
    int k;  //for repalcement copy for loop (dummy index variable)
    
    while ( maingrab < N) //will keep going as long as there is more of the main string to grab
    {
        //grab positions of mainstring[] and place in result[]until next position where substring starts
        for( ; maingrab < pos[i]; maingrab++)
             result[resultfill++] = mainstring[maingrab];
         
        //now maingrab is index of start of next position of substring
        
        //increment position index (to next substring for next iteration of while loop)
        i++;
        
        //copy over replacement string into result string
        for(k=0; k < T; k++)
             result[resultfill++] = tostring[k];
         
        //maingrab must now be pushed ahead by size of substring (we are skipping over it for next while loop iteration)
        maingrab += M;
   }
   result[resultfill] = '\0';  // NUL terminate     
   printf("result is: %s\n", result);
  
   return 0;
}

- S O U N D W A V E October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

What does string replace mean?

- S O U N D W A V E October 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <string.h>


int main(){

char buffer[1024];
char *s1 = "hello world";
char *s2 = "world";
char *s3 = "earth";
char *p;

if (!(p=strstr(s1, s2))) return s1;

strncpy(buffer, s1, p-s1);
buffer[p-s1]='\0';
sprintf (buffer+(p-s1), "%s%s", s3, p+strlen(s3));
printf("%s", buffer);


}

- mezgani October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Reena, type a full example, please.

- S O U N D W A V E October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

collabedit.com/rg7fx

- S O U N D W A V E October 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

char *string_replace(char * orig, char * new, char * old)
{
int count = 0;
char * p, *q = NULL;
char *buff = NULL;
int orig_l = strlen (orig);
int new_l = strlen (new);
int old_l = strlen (old);
int buff_l = 0;

// Calculate the new buff size needed and allocate memory for the new buffer
if ( new_l != old_l) {
// Count the occurrence of the old string
for (count =0, p =orig ; ((q=strstr(p,old)) != NULL);p = q + old_l)
count ++;

buff_l = count * (old_l - new_l)+1+ orig_l;
buff = (char *) malloc ( buff_l * sizeof (char));
} else {
buff_l = orig_l;
}

// Now replace the old string with the new string

for ( count = 0, p = orig ; ((q = strstr(p,old)) != NULL); q = p + old_l) {
strncat(buff, orig, p - q);
strcat( buff, new);
}

// copy the left over in q to buff
strcat (buff,q)

return buff;
}

- Anonymous December 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forgot to put my name

char *string_replace(char * orig, char * new, char * old)
{
int count = 0;
char * p, *q = NULL;
char *buff = NULL;
int orig_l = strlen (orig);
int new_l = strlen (new);
int old_l = strlen (old);
int buff_l = 0;

// Calculate the new buff size needed and allocate memory for the new buffer
if ( new_l != old_l) {
// Count the occurrence of the old string
for (count =0, p =orig ; ((q=strstr(p,old)) != NULL);p = q + old_l)
count ++;

buff_l = count * (old_l - new_l)+1+ orig_l;
buff = (char *) malloc ( buff_l * sizeof (char));
} else {
buff_l = orig_l;
}

// Now replace the old string with the new string

for ( count = 0, p = orig ; ((q = strstr(p,old)) != NULL); q = p + old_l) {
strncat(buff, orig, p - q);
strcat( buff, new);
}

// copy the left over in q to buff
strcat (buff,q)

return buff;
}

- Ravi December 13, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More