Difference between revisions of "Interview Preparation Strings"
Proj user18 (talk | contribs) (→Other frequently asked questions) |
Proj user18 (talk | contribs) (→Other frequently asked questions) |
||
| Line 413: | Line 413: | ||
CAB | CAB | ||
</syntaxhighlight> | </syntaxhighlight> | ||
| − | 3. Occurence of a | + | 3. Program To Count the Occurence of a Substring in String |
| + | <syntaxhighlight lang="c"> | ||
| + | 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 | ||
| + | </syntaxhighlight> | ||
Revision as of 03:11, 12 December 2016
Contents
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. 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 tu5. 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 str16. 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: WorldOther 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 ssalC2. 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
CAB3. 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
