Loading....
Coupon Accepted Successfully!

 

Question 51

Write a C program which does wildcard pattern matching algorithm


Here is an example C program...


#include
#define TRUE 1
#define FALSE 0

int wildcard(char *string, char *pattern);

int main()
{
  char *string = "hereheroherr";
  char *pattern = "*hero*";

  if(wildcard(string, pattern)==TRUE)
  {
    printf("\nMatch Found!\n");
  }
  else 
  {
    printf("\nMatch not found!\n");
  }
  return(0);
}

int wildcard(char *string, char *pattern)
{
  while(*string) 
  {
     switch(*pattern)
     {
        case '*': do {++pattern;}while(*pattern == '*');
                  if(!*pattern) return(TRUE);
                  while(*string){if(wildcard(pattern,string++)==TRUE)return(TRUE);}
                  return(FALSE);
        default : if(*string!=*pattern)return(FALSE); break;
     }
     ++pattern;
     ++string;
   }

   while (*pattern == '*') ++pattern;
   return !*pattern;
}



Question 52

How do you calculate the maximum subarray of a list of numbers?


This is a very popular question

You are given a large array X of integers (both positive and negative) and you need to find the maximum sum found in any contiguous subarray of X.


Example X = [11, -12, 15, -3, 8, -9, 1, 8, 10, -2]
Answer is 30.




There are various methods to solve this problem, some are listed below

Brute force


maxSum = 0
for L = 1 to N
{
  for R = L to N
  { 
     sum = 0
     for i = L to R
     {
        sum = sum + X[i]
     }
     maxSum = max(maxSum, sum)
   }
}

O(N^3)




Quadratic

Note that sum of [L..R] can be calculated from sum of [L..R-1] very easily.


maxSum = 0
for L = 1 to N
{
  sum = 0
  for R = L to N
  {
    sum = sum + X[R]
    maxSum = max(maxSum, sum) 
  }
}





Using divide-and-conquer


O(N log(N))

maxSum(L, R)
{
  if L > R then
    return 0
 
  if L = R then
    return max(0, X[L])

  M = (L + R)/2

  sum = 0; maxToLeft = 0
  for i = M downto L do
  {
     sum = sum + X[i]
     maxToLeft = max(maxToLeft, sum)
  } 
 
  sum = 0; maxToRight = 0
  for i = M to R do
  {
     sum = sum + X[i]
     maxToRight = max(maxToRight, sum)
  }


  maxCrossing = maxLeft + maxRight
  maxInA = maxSum(L,M)
  maxInB = maxSum(M+1,R)
  return max(maxCrossing, maxInA, maxInB)
}





Here is working C code for all the above cases


#include
#define N 10
int maxSubSum(int left, int right);
int list[N] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};

int main()
{
  int i,j,k;
  int maxSum, sum;

  /*---------------------------------------
  * CUBIC - O(n*n*n)
  *---------------------------------------*/

  maxSum = 0;
  for(i=0; i   {
    for(j=i; j     {
      sum = 0;
      for(k=i ; k       {
        sum = sum + list[k];
      }
      maxSum = (maxSum>sum)?maxSum:sum;
    }
   }

   printf("\nmaxSum = [%d]\n", maxSum);


   /*-------------------------------------
    * Quadratic - O(n*n)
    * ------------------------------------ */

   maxSum = 0;
   for(i=0; i    {
      sum=0;
      for(j=i; j       {
         sum = sum + list[j];
         maxSum = (maxSum>sum)?maxSum:sum;
      }
   }

   printf("\nmaxSum = [%d]\n", maxSum);


   /*----------------------------------------
    * Divide and Conquer - O(nlog(n))
    * -------------------------------------- */

   printf("\nmaxSum : [%d]\n", maxSubSum(0,9));

   return(0);
}


int maxSubSum(int left, int right)
{
  int mid, sum, maxToLeft, maxToRight, maxCrossing, maxInA, maxInB;
  int i;

  if(left>right){return 0;}
  if(left==right){return((0>list[left])?0:list[left]);}
  mid = (left + right)/2;

  sum=0;
  maxToLeft=0;
  for(i=mid; i>=left; i--)
  {
     sum = sum + list[i];
     maxToLeft = (maxToLeft>sum)?maxToLeft:sum;
  }


  sum=0;
  maxToRight=0;
  for(i=mid+1; i<=right; i++)
  {
      sum = sum + list[i];
      maxToRight = (maxToRight>sum)?maxToRight:sum;
  }

  maxCrossing = maxToLeft + maxToRight;
  maxInA = maxSubSum(left,mid);
  maxInB = maxSubSum(mid+1,right);
  return(((maxCrossing>maxInA)?maxCrossing:maxInA)>maxInB?((maxCrossing>maxInA)?maxCrossing:maxInA):maxInB);
}





Note that, if the array has all negative numbers, then this code will return 0. This is wrong because it should return the maximum sum, which is the least negative integer in the array. This happens because we are setting maxSum to 0 initially. A small change in this code can be used to handle such cases.






Test Your Skills Now!
Take a Quiz now
Reviewer Name