Facebook Interview Question: Given a regular expression wit

Search Algorithms

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.


'.' => 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

Your email address will not be published.