I had five interviews in one day:

• Four DSA
• One culture fit

Three of the DSA questions were dynamic programming and extremely difficult. The interviewers didn't seem to want to be there.

Given an input string s and a pattern p, implement regular expression matching with support for . and *, where:

• . matches any single character.
• * matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).