Interview Question

Software Engineering Interview Tel Aviv-Yafo (Israel)

Simple regex matching.

Tags:
regex
Answer

Interview Answer

5 Answers

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

0

What was the reason of no offer?

Peter on May 15, 2014
0

I couldn't reach a complete solution for the above question.

Anonymous on May 17, 2014
1

Here is a complete solution written in C.

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

/*
 * Write a function that implements a minimum regexp engine
 * where only '.', '*' and '.*' are supported assuming each
 * pattern requires beginning to end matching (not anywhere matching).
 *
 * For instance:
 *
 * 'abc' =~ 'abc' (ok)
 * 'abc' =~ 'a*bc' (ok)
 * 'aaaaaaabc' =~ 'c*bc' (ko)
 * 'aaaaaaabc' =~ 'a.*bc' (ok)
 * 'abbbbaaaaaabc' =~ 'ab*a*b*c' (ok)
 * 'abbbbaaaaaabc' =~ 'ab*a*h*bc' (ok)
 * 'bbd' =~ 'b*bbd' (ok)
 * 'bbd' =~ '.*bbd' (ok)
 * 'bbd' =~ '.*cbd' (ko)
 * '' =~ '.*' (ok)
 */

int string_match_regexp(char *str, char *pattern)
{
   /*
    * If we ever reached the end of the pattern then
    * there might be a match depending if we also
    * reached the end of string see last statement
    * of this function.
    */
   while (*pattern) {

      /*
       * If the next character is a wildcard then
       * we call recursively into the regexp engine
       * until we ate enough characters on the way i.e.
       * until the underlying recursive path succeed
       * or there is no eligible character to be eaten
       * anymore.
       *
       * This is the "backtracking" piece of the code
       * since if the underlying call fails we step back
       * and try again with another character taken out of
       * the way.
       */
      if (*(pattern + 1) == '*') {
         while (*str && (*pattern == *str || *pattern == '.')) {
            if (string_match_regexp(str++, pattern+2)) {
               return 1;
            }
         }
         pattern += 2;
      } else {
         /*
          * The easy part, if the character pointed by str diverges
          * from the character pointed by pattern then we bail out
          * except if pattern points to '.' in which case we keep
          * going.
          */
         if (*pattern != '.' && *str != *pattern) {
            return 0;
         }

         str++;
         pattern++;
      }
   }

   /*
    * Only match if we reached the end of the string as well...
    */
   return !*str;
}

int main()
{
    printf("(1) %u expect 1\n", string_match_regexp("abc", "abc"));
    printf("(2) %u expect 1\n", string_match_regexp("abc", "a*bc"));
    printf("(3) %u expect 0\n", string_match_regexp("aaaaaaabc", "c*bc"));
    printf("(4) %u expect 1\n", string_match_regexp("aaaaaaabc", "a.*bc"));
    printf("(5) %u expect 1\n", string_match_regexp("abbbbaaaaaabc", "ab*a*b*c"));
    printf("(6) %u expect 1\n", string_match_regexp("abbbbaaaaaabc", "ab*a*h*bc"));
    printf("(7) %u expect 1\n", string_match_regexp("bbd", "b*bbd"));
    printf("(8) %u expect 1\n", string_match_regexp("bbd", ".*bbd"));
    printf("(9) %u expect 0\n", string_match_regexp("bbd", ".*cbd"));
    printf("(10) %u expect 1\n", string_match_regexp("", ".*"));
    printf("(11) %u expect 1\n", string_match_regexp("", ".*c*"));
    printf("(12) %u expect 0\n", string_match_regexp("bbbbdbdbdaac", ".*d"));
    printf("(13) %u expect 1\n", string_match_regexp("bbbb", "b*c*"));
    printf("(14) %u expect 1\n", string_match_regexp("bbbb", "b*b*c*"));
    printf("(15) %u expect 1\n", string_match_regexp("abcd", ".*d"));
    printf("(16) %u expect 0\n", string_match_regexp("abcd", ".*d*c*c*e*hhh*j*.*c*h"));
}

Anonymous on May 17, 2014
0

Contact lists merge (data structure question):

public void Merge2ContactsLists(List<string> l1, List<string> l2)
{
    List<string> concatList = l1.AddList(l2);

    Merge(ref concatList, 0, l1.Count, concatList.Count);
}

public void Merge(ref List<string> list, int p, int q, int r)
{
    if(p < 0 || q < 0 || r < 0
        || p >= list.Count || q >= list.Count || r >= list.Count)
        return;

    if(!(p <= q && q <= r))
        return;

    list1Size = q - p + 1;
    list2Size = r - (q + 1) + 1;

    List<string> mergedList = new List<string>(list1Size + list2Size);

    int i = p;
    int j = q+1;
    int k = 0;

    while(i < q && j < r && k < list1Size + list2Size)
    {
        if(char.ToLower(list[i]) < char.ToLower(list[j]))
        {
            mergedList[k] = list[i];
            i++;
            k++;
        }
        else
        {
            mergedList[k] = list[j];
            j++;
            k++;
        }
    }

    while(i < q && k < list1Size + list2Size)
    {
        mergedList[k] = list[i];
        i++;
        k++;
    }

    while(j < r && k < list1Size + list2Size)
    {
        mergedList[k] = list[j];
        j++;
        k++;
    }

    for(k = 0; k < list1Size + list2Size; k++)
    {
        list[p + k] = mergedList[k];
    }
}

Anonymous on Dec 22, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.