Code Zone: November 2016

We have an integer array that is sorted in ascending order. We also have 3 ints A, B and C. We need to apply A*x*x + B*x + C for each element x in the array and return the corresponding sorted array.

Example: Input array = -1 0 1 2 3 4 and A = -1, B = 2, C = -1
Result of applying the formula to each element = -4 -1 0 -1 -4 -9
So expected result = -9 -4 -4 -1 -1 0 (sorted)

Time complexity :o(n), no extra space

Method: Parabolic Property
The equation given is parabolic. So the result of applying it to a sorted array will result in an array that will have a maximum/minimum with the sub-arrays to its left and right sorted.

In your case the maximum is 0 and the sub array to its left [-4 -1] is sorted in ascending order and the sub-array to its right [-1 -4 -9] is sorted in descending order.
All you need to do is merge these sorted arrays which is linear in time.

So the algorithm is:

Apply equation on each element
Find maximum/minimum
Merge subarrays

Useful Link:
http://stackoverflow.com/questions/4551599/sorting-result-array

Write your own implementations for following string library functions

1.strstr()
2.strcpy()
3.strcmp()
4.substr()
5.strdup()
6.strlen()
7.strcat()
8.strchr()
9.toUpper() & isUpper()

Set-2
1.strncmp()
2.strncat()
3.strncpy()
4.strrchr()

strcpy()

Method 1:
char *mystrcpy(char *dst, const char *src)
{
char *ptr;
ptr = dst;
while(*dst++=*src++);
return(ptr);
}
Method 2:
char *my_strcpy(char dest[], const char source[])
{
int i = 0;
while (source[i] != '\0')
{
dest[i] = source[i];
i++;
}
dest[i] = '\0';
return(dest);
}
NOTE:
1.The strcpy function copies src, including the terminating null character, to the location specified by dst. No overflow checking is performed when strings are copied or appended. The behavior of strcpy is undefined if the source and destination strings overlap. It returns the destination string. No return value is reserved to indicate an error.

2.Note that the prototype of strcpy as per the C standards is
char *strcpy(char *dst, const char *src);
Notice the const for the source, which signifies that the function must not change the source string in anyway!.
strncpy()

char * strncpy ( char * destination, const char * source, size_t num );

Copy characters from string

Copies the first num characters of source to destination. If the end of the source C string (which is signaled by a null-character) is found before num characters have been copied, destination is padded with zeros until a total of num characters have been written to it.

No null-character is implicitly appended to the end of destination, so destination will only be null-terminated if the length of the C string in source is less than num.
char *(strncpy)(char *s1, const char *s2, size_t n)
{
     char *dst = s1;
     const char *src = s2;
     while (n > 0) {
         n--;
         if ((*dst++ = *src++) == '\0') {
             memset(dst, '\0', n);
             break;
         }
     }
     return s1;
}

substr():

void mySubstr(char *dest, char *src, int position, int length)
{
while(length > 0)
{
    *dest = *(src+position);
    dest++;
    src++;
    length--;
}
}
Alternative:
char *substr(const char *pstr, int start, int numchars)
{
char *pnew = (char *)malloc(numchars+1);
strncpy(pnew, pstr + start, numchars);
pnew[numchars] = '\0';
return pnew;
}

Note:
substr() is used to copy a substring starting from position upto length

strdup():

char *mystrdup(char *s)
{
    char *result = (char*)malloc(strlen(s) + 1);
    if (result == (char*)0)
             {return (char*)0;}
    strcpy(result, s);
    return result;
}
strcmp()

int (strcmp)(const char *s1, const char *s2)
 {
     unsigned char uc1, uc2;
     /* Move s1 and s2 to the first differing characters 
        in each string, or the ends of the strings if they
        are identical.  */
     while (*s1 != '\0' && *s1 == *s2) {
         s1++;
         s2++;
     }
     /* Compare the characters as unsigned char and
        return the difference.  */
     uc1 = (*(unsigned char *) s1);
     uc2 = (*(unsigned char *) s2);
     return ((uc1 < uc2) ? -1 : (uc1 > uc2));
 }

Note:

strcmp(str1,str2) returns a -ve number if str1 is alphabetically less than str2, 0 if both are equal and +ve if str1 is alphabetically above str2.The prototype of strcmp() is

int strcmp( const char *string1, const char *string2 );

strncmp()
int (strncmp)(const char *s1, const char *s2, size_t n)
{
     unsigned char uc1, uc2;
     if (n == 0)
         return 0;
     while (n-- > 0 && *s1 == *s2)
    {
         if (n == 0 || *s1 == '\0')
             return 0;
         s1++;
         s2++;
     }
     uc1 = (*(unsigned char *) s1);
     uc2 = (*(unsigned char *) s2);
     return ((uc1 < uc2) ? -1 : (uc1 > uc2));
}

strlen():

Method 1:
int my_strlen(char *string)
{
int length;
for (length = 0; *string != '\0', string++)
{
length++;
}
return(length);
}
Method 2: Pointer difference
int my_strlen(char *s)
{
char *p=s;
while(*p!='\0')
p++;
return(p-s);
}
Note:
The prototype of the strlen() function is
size_t strlen(const char *string);

strrchr()

const char * strchr ( const char * str, int character );
      char * strchr (       char * str, int character );

Locate first occurrence of character in string
Returns a pointer to the first occurrence of character in the C string str.
The terminating null-character is considered part of the C string. Therefore, it can also be located to retrieve a pointer to the end of a string.

char *(strrchr)(const char *s, int c)
 {
     const char *last = NULL;
         if (c == '\0')
         return strchr(s, c);
     while ((s = strchr(s, c)) != NULL) {
         last = s;
         s++;
     }
     return (char *) last;
 }

strcat():

char *myStrcat(char *s, const char *t)
{
    char *p = s;
    if (s == NULL || t == NULL)
        return s;   /* we need not have to do anything */
    while (*s)
        s++;
    while (*s++ = *t++);
    return p;
}
strncat()

 char *(strncat)(char *s1, const char *s2, size_t n)
 {
     char *s = s1;
     while (*s != '\0')
         s++;
     while (n != 0 && (*s = *s2++) != '\0') {
         n--;
         s++;
     }
     if (*s != '\0')
         *s = '\0';
     return s1;
 }

toUpper():
int toUpper(int ch)
{
    if(ch>='a' && c<='z')
        return('A' + ch - 'a');
    else
        return(ch);
}

isUpper():
int isUpper(int ch)
{
    if(ch>='A' && ch <='Z')
       return(1); //Yes, its upper!
    else
       return(0); // No, its lower!
}
Note:
Another way to do this conversion is to maintain a correspondance between the upper and lower case alphabets. The program below does that. This frees us from the fact that these alphabets have a corresponding integer values.

#include <string.h>
#define UPPER   "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define LOWER   "abcdefghijklmnopqrstuvwxyz"

int toUpper(int c)
{
    const char *upper;
const char *const lower = LOWER;

    // Get the position of the lower case alphabet in the LOWER string using the strchr() function ..
    upper = ( ((CHAR_MAX >= c)&&(c > '\0')) ? strchr(lower, c) : NULL);

      // Now return the corresponding alphabet at that position in the UPPER string ..
    return((upper != NULL)?UPPER[upper - lower] : c);
}

Useful Links:
http://en.wikibooks.org/wiki/C_Programming/Strings

Code Zone

Labels

Wednesday, November 9, 2016

Design a Coffee Shop

OO design for a coffee shop

Design a Tic Tac Toe Game

Efficient data structure for storing and calculating the total resistance

Sunday, November 6, 2016

Design a Chess Game

Thursday, November 3, 2016

Sort the Result Array

Wednesday, November 2, 2016

Own vesions of String library functions