It is very common to for the interviewer to ask a string question. Following blogpost will help you implement some of the string functions. It is not an extensive list but will give you a basic idea of what kind of questions can be asked.
1) Finding length of the string
It is a common phone interview question. The interviewer is checking your understand of strings and how you will parse them. You can start with the algorithm and then can continue with its implementation.
Algorithm:
- Initialize length counter to 0.
- Initialize a pointer to the start of the string.
- If character at pointer location is not null('\0') then increment the length and pointer location.
- Repeat step 3 till you find a character whose value is null.
- The counter length at the end of the string will specify the string's length.
int len = 0;
char *ptr;
ptr = s;
while(*ptr!='\0')
{
len++;
ptr++;
}
2) Copying strings with the help of arrays
This is another common interview question which is often asked in phone interview or initial rounds of technical interviews. It is asking to copy one string to another and both strings are represented as arrays.
Algorithm:
- Initialize a length counter to 0 and pointer to the the first location in the source array.
- If character at pointer location is not null then copy the character at target[len], where len is the pointer location of target array.
- Increment the source pointer and target pointer.
- Repeat steps 2 and 3 till the pointer in the source location is null
Implementation:
void func(char source[],char target[])
{
int len = 0;
char *ptr;
ptr = source;
while(*ptr!='\0')
{
//*target = *source;
target[len++] = *ptr;
ptr++;
}
target[len++] = '\0';
std::cout << target << std::endl;
}
Complexity:
O(M + N) where M is the length of source string, and N is the length of target string.
3) Concatenating the strings
It will append one string to the end of another. If string1 = 'hello ' and string2 = 'world' then concatenating string2 to string1 will result in 'hello world'
Algorithm:
1) Point one pointer to start of string1 and another to the start of string2
2) Move pointer one till you encounter end of string1.
3) Then append characters from string2 to string1 one by one. Meanwhile move pointers along by one location at a time.
4) At the end append a null character.
void func(char *source,char *target)
{
int len = 0;
char *ptr_s,*ptr_t;
ptr_s = source;
while(*ptr_s!='\0')
{
source++;
ptr_s++;
}
ptr_t = target;
while(*ptr_t!='\0')
{
*source = *ptr_t;
source++;
ptr_t++;
}
*source = '\0';
}
4) Comparing the strings
It will compare the strings and displays if strings match or not.
Algorithm:
1) Initialize pointers at the start of string1 and string2. Initialize a flag to zero.
2) If characters at location i match in both the strings then move the pointers to next location.
3) Keep on repeating the step 2 till you either reach the end of string or till you don't find a match.
4) If you don't find a match then break loop and change the flag value to 1.
5) If flag is zero then output 'Strings match' or else 'Strings don't match'.
Implementation:
void func(char *source,char *target)
{
int len = 0,flag=0;
char *ptr_s,*ptr_t;
ptr_s = source;
ptr_t = target;
while(*ptr_s!='\0' && *ptr_t!='\0')
{
if(*ptr_s != *ptr_t)
{
flag = 1;
break;
}
ptr_s++;
ptr_t++;
}
if(flag==0)
std::cout << "String matches" << std::endl;
else
std::cout << "String does not matches" << std::endl;
}
5) String matching brute force
It will search for a pattern in string in a brute force manner. Algorithm:
1) Find of string and pattern.
2) Intialize a counter1 and counter.
3) If character a location counter is found then increment both counters or else increment only counter 1.
4) If counter2 matches the length of pattern then the match is found or else not.
5) Repeat steps 3,4 till end of input string. Implementation:
Implementation:
char string[] = {'B','o','x','o','x','m','\0'};// "Box";
char pattern[] = {'o','x','\0'};//"ha";
int len1 = strlen(string);
int len2 = strlen(pattern);
int flag = 0;
int count = 0;
std::cout << len1 << std::endl;
std::cout << len2 << std::endl;
int curr = 0;
int curr1 = 0;
while(curr != len1)
{
if(string[curr] != pattern[curr1])
curr++;
else if(string[curr] == pattern[curr1])
{
curr++;
curr1++;
}
if(curr1 == len2)
{
flag = 1;
curr1 = 0;
count++;
}
}
if(flag == 0)
std::cout << "String not matching\n";
else
std::cout << "String matching\n" << count;
You might also like:
No comments:
Post a Comment