Wednesday, November 9, 2016

Thursday, November 3, 2016

Sort the Result Array


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

Wednesday, November 2, 2016

Pending


Own vesions of String library functions

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

Sunday, October 16, 2016

Wednesday, October 12, 2016

Group Shifted Strings

Given an array of strings (all lowercase letters), the task is to group them in such a way that all strings in a group are shifted versions of each other. Two string S and T are called shifted if,

S.length = T.length
and
S[i] = T[i] + K for
1 <= i <= S.length  for a constant integer K
For example strings {acd, dfg, wyz, yab, mop} are shifted versions of each other.

http://www.geeksforgeeks.org/group-shifted-string/

Count maximum points on same line

Given N point on a 2D plane as pair of (x, y) co-ordinates, we need to find maximum number of point which lie on the same line.

Examples:

Input : points[] = {-1, 1}, {0, 0}, {1, 1},
                    {2, 2}, {3, 3}, {3, 4}
Output : 4
Then maximum number of point which lie on same
line are 4, those point are {0, 0}, {1, 1}, {2, 2},
{3, 3}

http://www.geeksforgeeks.org/count-maximum-points-on-same-line/

Assembly Line Scheduling

A car factory has two assembly lines, each with n stations. A station is denoted by Si,j where i is either 1 or 2 and indicates the assembly line the station is on, and j indicates the number of the station. The time taken per station is denoted by ai,j. Each station is dedicated to some sort of work like engine fitting, body fitting, painting and so on. So, a car chassis must pass through each of the n stations in order before exiting the factory. The parallel stations of the two assembly lines perform the same task. After it passes through station Si,j, it will continue to station Si,j+1 unless it decides to transfer to the other line. Continuing on the same line incurs no extra cost, but transferring from line i at station j – 1 to station j on the other line takes time ti,j. Each assembly line takes an entry time ei and exit time xi which may be different for the two lines. Give an algorithm for computing the minimum time it will take to build a car chassis.

http://www.geeksforgeeks.org/dynamic-programming-set-34-assembly-line-scheduling/


Thursday, October 6, 2016

Happy Numbers

What is an happy number can be shown in the following example:

19 is a happy number
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

http://www.programcreek.com/2014/04/leetcode-happy-number-java/
http://getprogramcode.com/2013/12/java-program-to-check-for-a-happy-number/

Caterpillars and Uneaten Leaves

K caterpillars are eating their way through N leaves, each caterpillar falls from leaf to leaf in a unique sequence, all caterpillars start at a twig at position 0 and falls onto the leaves at position between 1 and N. Each caterpillar j has as associated jump number Aj. A caterpillar with jump number j eats leaves at positions that are multiple of j. It will proceed in the order j, 2j, 3j…. till it reaches the end of the leaves and it stops and build its cocoon.

Given a set A of K elements K<-15, N<=10^9, we need to determine the number of uneaten leaves.

Input:

N= No of uneaten leaves.

K= No. of caterpillars

A = Array of integer jump numbers

Output: The integer nu. Of uneaten leaves.

Sample Input:10, 3, 2, 4, 5

Output: 4

Explanation:

[2, 4, 5] is a j member jump numbers, all leaves which are multiple of 2, 4, and 5 are eaten, leaves 1,3,7,9 are left, and thus the no. 4

http://codereview.stackexchange.com/questions/95145/caterpillar-uneaten-leaves
http://stackoverflow.com/questions/27248327/caterpillars-and-leaves-can-we-do-better-than-onc
http://qa.geeksforgeeks.org/219/uneaten-leaves-problem