Code Question 1

The developers at Amazon are developing a regex matching library for their NLP use cases. A prototype regex matching has the following requirements:

• The regex expression contains lowercase English letters, '(', ')', '.', and '*'.
• '.' matches with exactly one lowercase English letter.
• A regular expression followed by '*' matches with zero or more occurrences of the regular expression.
• If an expression is enclosed in parentheses '(' and ')', it is treated as one expression and any asterisk '' applies to the whole expression. It is guaranteed that no expression enclosed within parentheses contains any '' but is always followed by '*'. Also, there is no nested brackets sequence in the given regex expression for the prototype.

For example:

• Regex "(ab)*d" matches with the strings "d", "ababd", "abd", but not with the strings "abbd", "abab".
• Regex "ab*d" matches with the strings "abbbd", "ad", "abd", but not with strings "ababd".
• Regex "a(b.d)*" matches with the strings "abcd", "abcd", "abcded", "abed", "a" but not with strings "bcd", "abd".
• Regex "(.)*e" matches with the strings "a", "aa", "aaa", "b", "bb" and many more but not "ac", "and", or "bcd" for example.

Given an array, arr, of length k containing strings consisting of lowercase English letters only and a string regex of length n, for each of them find whether the given regex matches with the string or not and report an array of strings "YES" or "NO" respectively.

Example:

Suppose, n = 8, regex = '(a.b)*bd', k = 3, arr = ['acbabbbd', 'bd', 'abbd']

• arr[0] = "acbabbbd" matches the regex "(a.b)bd", if we replace '' with 2 occurrences of "a.b", i.e. it becomes "a.ba.bbd". Now, replace both '.' with 'c' and 'b' respectively.
• arr[1] = "bd" matches the regex "(a.b)bd", if we replace '' with 0 occurrences of "a.b", i.e. it becomes "bd".
• arr[2] = "abbd" doesn't matches the regex "(a.b)*bd".

Hence, the answer is ["YES", "YES", "NO"].

Function Description

Complete the function isRegexMatching in the editor below.

isRegexMatching has the following parameters:

• regex: A regex
• arr[k]: An array of strings

Returns:

• string[]: An array of strings of size k where the ith string is "YES" if the regex matches the string arr[i], otherwise it is "NO".

Constraints

Sample Input For Custom Testing

Sample Case 0

Input

regex = "ab(e.r)*e"
k = 2
arr = ["abbeeere", "abefretre"]

Output

["YES", "NO"]

Code Question 2

Amazon uses small, Roomba-shaped robots, called "Drives". They deliver large stacks of products to human workers by following set paths around the warehouse.

The warehouse can be represented in the form of a Cartesian plane, where robots are located at integral points of the form (x,y)(x, y)(x,y). When a product is to be delivered to some point (i,j)(i, j)(i,j), the nearest robot is sought and chosen. Thus if a robot is surrounded by other robots nearby, it will seldom be chosen for work. More formally, a robot is said to be idle if it has a robot located above, below, left, and right of it. It is guaranteed that no two robots are at the same location.

Given the locations of nnn robots, find the number of idle robots.

Example

The xxx and yyy coordinates are given as two arrays, with the coordinates aligned by index: x=[1,1,1,2,2,2,3,3,3,3]x = [1, 1, 1, 2, 2, 2, 3, 3, 3, 3]x=[1,1,1,2,2,2,3,3,3,3] and y=[1,2,3,1,2,3,1,2,3,5]y = [1, 2, 3, 1, 2, 3, 1, 2, 3, 5]y=[1,2,3,1,2,3,1,2,3,5].

The 10 robots are arranged as follows:

• The robot at (2,2)(2, 2)(2,2) is idle because it has robots at (1,2)(1, 2)(1,2), (3,2)(3, 2)(3,2), (2,3)(2, 3)(2,3), and (2,1)(2, 1)(2,1) directly to the left, right, up, and down respectively.
• The robot at (2,3)(2, 3)(2,3) is idle because it has robots at (1,3)(1, 3)(1,3), (3,3)(3, 3)(3,3), (2,5)(2, 5)(2,5), and (2,2)(2, 2)(2,2) directly to the left, right, up, and down respectively.

There are 2 idle robots in this arrangement.

Sample Input For Custom Testing

Input

x = [-1, 0, 1, 2, -2, 0, 1, -1, 0, 1, 0, 0]
y = [-1, 0, 1, 2, -2, 0, 1, -1, 0, 1, 0, 0]

Output

5

Explanation

The Cartesian plane with idle robots marked red can be represented as:

If you also have OA writing needs, please contact us. We are service-oriented and are inspired to be the number one interview support agency in North America. CSOAHELP

如果您也有OA代写的需求，请联系我们，我们服务至上，励志做北美面试支持机构第一品牌。 CSOAHELP