Interview Preparation Strings

Reverse a string

void reverse_str(char *s)
{
    const int len = strlen(s);
    const int mid = len / 2;
    for (int i = 0, j=len-1; i < mid; i++, j--) {
        char c = s[i];
        s[i]   = s[j];
        s[j]   = c;
    }
}

Reverse words in a string

If string to be reversed is "where there is a will there is a way"
Output needed : "way a is there will a is there where"
To reverse the words in a string , we will follow below steps:
1) First, we will reverse each word in the string as "erehw ereht si a lliw ereht si a yaw"
2) Second, we will reverse this string by letter to get the desired output.
We are going to use previous reverse_str function with one more parameter "length" as below:

void reverse_str(char *s ,int len)
{
    int i,j;
	char temp;
	j= len - 1;
	int mid = len/2;
	for(i=0;i<mid;i++,j--)
	{
		temp = s[i];
		s[i] = s[j];
		s[j] = temp;

	}
}

void reverse_words_in_string(char *s)
{
	/*
	 * 1st step
	 * In below while loop , string becomes "erehw ereht si a lliw ereht si a yaw"
	 */
	/* To obtain the start of word to be reversed in a string and its length */
	int i=0;
	/*To traverse through string */
	unsigned int j=0;

	while(j <= strlen(s))
	{
		/* Check for word in string. '\0' condition is checked for last word */
		if( *(s+j) == ' ' || *(s+j) == '\0')
		{
			/* (s+i) points at the start of word and (j-i) denotes the length */
			reverse( s+i, j-i );
			/* "i" will have the index at which next word starts */
			i = j+1;
		}
		j++;
	}
	/*
	 * 2nd Step
	 * string "erehw ereht si a lliw ereht si a yaw" is reversed to get "way a is there will a is there where"
	 */
	reverse(s,strlen(s));

}

Find the last word in a string

If given string is "Dreams don't work unless you do "
Output needed : "do"
To get the desired output we will use one pointer which points at the end of string and we will transverse it till we get our first blank space between last 2 words in string.

char* last_word_in_string(char *s)
{
	int i=0;
	char* last;
	const int len= strlen(s) -1;
	char *j = s + len;
/* If last letter of string is blank space then it will be avoided */
	if (*(s+len) == ' ')
	{
		j = j-1;
	}
	while(*j)
	{

		if ( *j== ' ')
		{
			j++;
			break;
		}
		j--;
		i++;

	}
	return j;
}

Interview Question - Check if strings are Anagrams

Two strings are said to be Anagram, if the two strings contain same characters,although they can be in different order. The characters of one string can be rearranged to form a different string. The characters in both the strings should occur the same number of times. For example, ball and abll are anagrams. all and ball are not anagrams.

/** To check if the two strings are anagrams.**/

int Anagram(char str1[], char str2[])// two input strings str1 and str2
{
   int count1[100] = {0}, count2[100] = {0}, i = 0;// initialize two arrays count 1 and count 2 to zero to count the characters in the strings
   
   /* if String size is not equal */
   if(strlen(str1) != strlen(str2))
   {
	   return 0;
   }

   for(i=0;i<strlen(str1);i++)//iterating through the string to calculate the number of characters in string1
   {
      count1[str1[i] - 'a']++;
   }
   i=0;
   for(i=0;i<strlen(str2);i++)//iterating through the string to calculate the number of characters in string2
   {
      count2[str2[i] - 'a']++;
   }
   for (i = 0; i < 100; i++)
    {
        if (count1[i] != count2[i])// condition to check if the number of characters are equal in two strings.
            return 0;
    }
    return 1;
}

Interview question : Check if a string has all unique characters

Approach: Create an array of Boolean values, where the flag at index i indicates whether character i in the alphabet is contained in the string. The second time we see that character, return false.

bool isStringUnique (string str)
{
	if (str.length() > 256) // Base case: assuming extended ASCII character set
	{
		return false;
	}
	bool char_array [256];
	memset(char_array, '\0', 256);
	for (unsigned int i = 0; i < str.length(); i++)
	{
		int value = str.at(i);
		if(char_array[value])
		{
                     return false;
		}
		char_array[value] = true;
	}
	return true;
}

More on String

Strings are one-dimensional array of characters terminated by a null character '\0'. Thus a null-terminated string contains the characters that comprise the string followed by a null.