Facebook Interview Question: Given a regular expression wit

Please follow & like us :)

Search Algorithms
Search

In Facebook Engineering Interview, you may be asked to do linear search on given String using reggex pattern.

Here is the detailed Question For Search Algorithm:

Facebook Coding Question: Given a regular expression with characters A-Z, ‘ * ‘, ‘ . ‘ (Ex: AB.*D*). Check if that pattern matches to given string and return flag true. Return false otherwise.

Here are the clarifications we need to keep in cosideration.

Clarifications:

'.' => Any character
'*' => 0 to N occurrence of preceding element(for ".*").
'*' => Any character ( for "A*" )
'*' => N occurrence ( for "A*" ). 

Sample Data:

Example1: Input String: “ABCDDE”, Input Regex: AB.*D* Output: true

In This Example we are comparing characters in input string and input regex.

  • Step1: AB are present in Both given String and also in given Regex.
  • Step2: “.” means Any character so basically we don’t need to compare at all.
  • Step3: “*” means we need to check character after that character and it should be the same character as it is next to “.”. We can easily check using str[currenti] === str[currenti+1] comparison.
  • Step4: “D” is present in Both given String and also in given Regex.
  • Step5: Lastly for “*” as it doesn’t have “.” before it, it could be any character and could be N occurrences.

Now we know the execution and comparison steps we need to solve this problem, we can add it to working program using Javascript.

const testRegex = (str, ptrn) => {
  let flag = true;
  for (let i = 0; i < str.length; i++) {
    if (str[i] !== ptrn[i]) {
      if (ptrn[i] === '.') {
      
      } else if (ptrn[i] === '*' && flag === true) {
       
      } else if (ptrn[i] === '*' && ptrn[i-1] === '.') {
        flag = true;
        const char = ptrn[i+1];
        if (char === str[i]) {
          
        }
        else {
          return false;
        }
      } else {
        return false;
      }    
    }
  }
  return true;
}
console.log(testRegex('ABCDDE', 'AB.*D*'));

Try on Coding Playground to test it out:

Be the first to comment

Leave a Reply