Difference between revisions of "Interview Preparation Strings"

Latest revision as of 09:01, 15 December 2016

1 Reverse a string
2 Reverse words in a string
3 Find the last word in a string
4 Convert numeric String to an int without using stoi function
5 Interview Question - Check if strings are Anagrams
6 Interview question : Check if a string has all unique characters
7 More on strings
- 7.1 Using some in-built functions
- 7.2 Other frequently asked questions

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;
}

Convert numeric String to an int without using stoi function

int string_to_int(char *str)
{
  int i = 0;
  int number = 0; 
  /* Loop till end of string */
  while (str[i] != '\0')    
  {
    if(str[i] >= '0' && str[i] <= '9') //Check if value is between number 0 to 9 
    {

/* 
 * If it is between 0 to 9 then calculate its numeric value.
 * Below value of str[i] is substracted from '0' to get exact numeric value of that numeric character.
 */    
      number = number*10 + str[i] - '0'; 
    }
    else
    {
      break;

    }
    i++;

  }
  return number;

}

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 strings

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. The following declaration and initialization create a string consisting of the word "Hello". To hold the null character at the end of the array, the size of the character array containing the string is one more than the number of characters in the word "Hello."

char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

OR

char greeting[] = "Hello";

The C compiler automatically places the '\0' at the end of the string when it initializes the array even if you don't put one.

Using some in-built functions

Basic template

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

int main () {

1. Copy string 1 to string 3 (using strcpy function)

   char str1[12] = "Hello";
   char str2[12] = "World";
   char str3[12];
   int  len ;

   strcpy(str3, str1);
   printf("strcpy( str3, str1) :  %s\n", str3 );

2. Concatenate string 1 and string 2 (using strcat function)

   strcat( str1, str2);
   printf("strcat( str1, str2):   %s\n", str1 );

3. Total Length of string 1 after concatenation (using strlen function)

   len = strlen(str1);
   printf("strlen(str1) :  %d\n", len );

   return 0;
}

4. Copy first n characters of string 2 to string 1 (Here we have used function memset() to clear the memory location)

   char src[40];
   char dest[12];
  
   memset(dest, '\0', sizeof(dest));
   strcpy(src, "This is tutorialspoint.com");
   strncpy(dest, src, 10);

   printf("Final copied string - %s\n", dest);

   return 0;
}

OUTPUT: Final copied string - This is tu

5. Compare string1 and string2 to determine alphabetic order

   char str1[15];
   char str2[15];
   int ret;

   strcpy(str1, "abcdef");
   strcpy(str2, "ABCDEF");

   ret = strcmp(str1, str2);

   if(ret < 0)
   {
      printf("str1 is less than str2");
   }
   else if(ret > 0) 
   {
      printf("str2 is less than str1");
   }
   else 
   {
      printf("str1 is equal to str2");
   }
   
   return(0);
}

OUTPUT: str2 is less than str1

6. First occurrence of the character c in the string str.

   const char str[] = "http://www.abc.com";
   const char ch = '.';
   char *ret;

   ret = strchr(str, ch);

   printf("String after |%c| is - |%s|\n", ch, ret);
   
   return(0);
}
OUTPUT: String after |.| is - |.abc.com|

7. Last occurence of character c in string.

   int len;
   const char str[] = "http://www.abc.com";
   const char ch = '.';
   char *ret;

   ret = strrchr(str, ch);

   printf("String after |%c| is - |%s|\n", ch, ret);
   
   return(0);
}
OUTPUT: String after |.| is - |.com|

8. First occurence of string string 1 in string 2 (The C library function char *strstr(const char *haystack, const char *needle) function finds the first occurrence of the substring needle in the string haystack. The terminating '\0' characters are not compared.)

   const char haystack[20] = "HelloWorld";
   const char needle[10] = "World";
   char *ret;

   ret = strstr(haystack, needle);

   printf("The substring is: %s\n", ret);
   
   return(0);
}
OUTPUT: The substring is: World

Other frequently asked questions

1. Program to reverse every word of given string

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

void main () {
int i, j = 0, k = 0, x, len;
    char str[100], str1[10][20], temp;
 
    printf("enter the string :");
    scanf("%[^\n]s", str);
 
/* reads into 2d character array */
    for (i = 0;str[i] != '\0'; i++)
    {
        if (str[i] == ' ')
        {
            str1[k][j]='\0';
            k++;
            j=0;
        }
        else
        {
            str1[k][j]=str[i];
            j++;
        }
    }
    str1[k][j] = '\0';
 
/* reverses each word of a given string */
    for (i = 0;i <= k;i++)
    {
        len = strlen(str1[i]);
        for (j = 0, x = len - 1;j < x;j++,x--)
        {
            temp = str1[i][j];
            str1[i][j] = str1[i][x];
            str1[i][x] = temp;
        }
    }
    for (i = 0;i <= k;i++)
    {
        printf("%s ", str1[i]);
    }
}
OUTPUT: 
enter the string :C Programming Class
C gnimmargorP ssalC

2. Program to print all permutations of a string

 
/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
 
/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string.
*/

void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}
OUTPUT:
ABC
ACB
BAC
BCA
CBA
CAB

3. Program To Count the Occurence of a Substring in String

char str[100], sub[100];
int count = 0, count1 = 0;
 
void main()
{
    int i, j, l, l1, l2;
 
    printf("\nEnter a string : ");
    scanf("%[^\n]s", str);
 
    l1 = strlen(str);
 
    printf("\nEnter a substring : ");
    scanf(" %[^\n]s", sub);
 
    l2 = strlen(sub);
 
    for (i = 0; i < l1;)
    {
        j = 0;
        count = 0;
        while ((str[i] == sub[j]))
        {
            count++;
            i++;
            j++;
        }
        if (count == l2)
        {
            count1++;                                   
            count = 0;
        }
        else
            i++;
    }    
    printf("%s occurs %d times in %s", sub, count1, str);
}
OUTPUT:
Enter a string : prrrogram c prrrogramming
 
Enter a substring : rr
rr occurs 2 times in prrrogram c prrrogramming

4. Program to find the frequency of every word in the string

    int count = 0, c = 0, i, j = 0, k, space = 0;
    char str[100], p[50][100], str1[20], ptr1[50][100];
    char *ptr;
 
    printf("Enter the string\n");
    scanf(" %[^\n]s", str);
    printf("string length is %d\n", strlen(str));

    for (i = 0;i<strlen(str);i++)
    {
        if ((str[i] == ' ')||(str[i] == ', ')||(str[i] == '.'))
        {
            space++;
        }
    }

    for (i = 0, j = 0, k = 0;j < strlen(str);j++)
    {
        if ((str[j] == ' ')||(str[j] == 44)||(str[j] == 46))  
        {    
            p[i][k] = '\0';
            i++;
            k = 0;
        }        
        else
             p[i][k++] = str[j];
    }

    k = 0;

    for (i = 0;i <= space;i++)
    {
        for (j = 0;j <= space;j++)
        {
            if (i == j)
            {
                strcpy(ptr1[k], p[i]);
                k++;
                count++;
                break;
            }
            else
            {
                if (strcmp(ptr1[j], p[i]) != 0)
                    continue;
                else
                    break;
            }
        }
    }

    for (i = 0;i < count;i++) 
    {
        for (j = 0;j <= space;j++)
        {
            if (strcmp(ptr1[i], p[j]) == 0)
                c++;
        }
        printf("%s -> %d times\n", ptr1[i], c);
        c = 0;
    }
}

5. Program to Read a String and find the Sum of all Digits in the String

char string[80];
    int count, nc = 0, sum = 0;
 
    printf("Enter the string containing both digits and alphabet \n");
    scanf("%s", string);
    for (count = 0; string[count] != '\0'; count++)
    {
        if ((string[count] >= '0') && (string[count] <= '9'))
        {
            nc += 1;
            sum += (string[count] - '0');
        }
    }
    printf("NO. of Digits in the string = %d\n", nc);
    printf("Sum of all digits = %d\n", sum);
}
OUTPUT:
Enter the string containing both digits and alphabet
hello100
NO. of Digits in the string = 3
Sum of all digits = 1

6. Program to count vowels, consonants, digits and white spaces.

    char line[150];
    int i, vowels, consonants, digits, spaces;

    vowels =  consonants = digits = spaces = 0;

    printf("Enter a line of string: ");
    scanf("%[^\n]", line);

    for(i=0; line[i]!='\0'; ++i)
    {
        if(line[i]=='a' || line[i]=='e' || line[i]=='i' ||
           line[i]=='o' || line[i]=='u' || line[i]=='A' ||
           line[i]=='E' || line[i]=='I' || line[i]=='O' ||
           line[i]=='U')
        {
            ++vowels;
        }
        else if((line[i]>='a'&& line[i]<='z') || (line[i]>='A'&& line[i]<='Z'))
        {
            ++consonants;
        }
        else if(line[i]>='0' && line[i]<='9')
        {
            ++digits;
        }
        else if (line[i]==' ')
        {
            ++spaces;
        }
    }

    printf("Vowels: %d",vowels);
    printf("\nConsonants: %d",consonants);
    printf("\nDigits: %d",digits);
    printf("\nWhite spaces: %d", spaces);

    return 0;
}
OUTPUT:
Enter a line of string: adfslkj34 34lkj343 34lk
Vowels: 1
Consonants: 11
Digits: 9
White spaces: 2

7. Program to remove all characters in second string that are present in first string.

/*
#include <ctype.h>
#include <stdlib.h>
#define CHAR_SIZE 26
*/
void alphacheck(char *, int []);
void create(char [], char [], int[]);
 
int main()
{
    char str1[50], str2[50];
    int a1[CHAR_SIZE] = {0};
    char str2_rem[50];
 
    printf("Enter string1: ");
    scanf("%s", str1);
    printf("Enter string2: ");
    scanf("%s", str2);
    alphacheck(str1, a1);
    create(str2_rem, str2, a1);
    printf("On removing characters from second string we get: %s\n", str2_rem);
 
    return 0;
}
 
void alphacheck(char *str, int a[])
{
    int i, index;
 
    for (i = 0; i < strlen(str); i++)
    {
        str[i] = tolower(str[i]);
        index = str[i] - 'a';
        if (!a[index])
        {
            a[index] = 1;
        }
    }
    printf("\n");
}
 
void create(char str_rem[], char str[], int list[])
{
    int i, j = 0, index;
 
    for (i = 0; i < strlen(str); i++)
    {
        index = str[i] - 'a';
        if (!list[index])
        {
            str_rem[j++] = str[i];
        }
    }
    str_rem[j] = '\0';
}
OUTPUT:
Enter string1: programming
Enter string2: computer
 
On removing characters from second string we get: cute

Difference between revisions of "Interview Preparation Strings"

Latest revision as of 09:01, 15 December 2016

Contents

Reverse a string

Reverse words in a string

Find the last word in a string

Convert numeric String to an int without using stoi function

Interview Question - Check if strings are Anagrams

Interview question : Check if a string has all unique characters

More on strings

Using some in-built functions

Other frequently asked questions

Navigation menu

Views

Personal tools

Navigation

Search

Tools

Google AdSense