MathWorks 店面

Job Hunting Interview
, , , , ,
1

Given a grid with w as width, h as height. A company wants to develop an office park in the grid where each cell represents a potential building lot. The goal is for the furthest of all lots to be as near as possible to an office building. Given an input n, which is the number of buildings to be placed in the lot, determine the building placement to minimize the distance the most distant empty lot is from the building. Distance is measured in horizontal and vertical directions, i.e. diagonal distance measurement is not considered.

inputs
w: an integer, the width of the grid
h: an integer, the height of the grid
n: an integer, the number of buildings to be placed

For example, w=4, h=4 and n=3. An optimal grid placement sets any lot within two unit distance of the building. The answer for this case is 2.

“0” indicates optimal building placement and in this case the maximal value of all shortest distances to the closest building for each cell is “2”.

1 0 1 2
2 1 2 1
1 0 1 0
2 1 2 1
The above represents one optimal solution, there could be more like the above array rotated as an example. The above is an optimal solution because out of the 3 buildings (n=3), one building was placed at index (0,1), second was placed at (2,1) and third was placed at (2,3). The surrounding horizontal and vertical distance is shown as 1 and 2 by adding 1 each time we move horizontally and/or vertically. Note again that diagonal movement is not allowed:

1 ← 0 → 1 → 2
↓
2 ← 1 → 2 ← 1
↑. . ↑
1 ← 0 → 1 ← 0
↓ . . ↓
2 ← 1 → 2 ← 1

Other examples:

Example 1)

w=3, h=3, n=2
Two buildings (zeros) have to be optimally placed. One of the optimal plan for this case is:

01
11
10

0 → 1
↓
1 . . .1
. . . . ↑
1 ← 0

Answer: 1

3

也报一下我的

As an assignment, a student is given two strings s and t. Create a function that performs per the following rules.

Find whether string s is divisible by string t. A string s divisible by string t if string t can be concatenated some number of times to obtain the string s.
If s is divisible, find the smallest string u such that it can be concatenated some number of times to obtain both s and t.
If it is not divisible, set the return value to -1.
Finally, return the length of the string u or -1.

Example 1:

s = “bcdbcdbcdbcd”

t = “bcdbcd”

If string t is concatenated twice, the result is “bcdbcdbcdbcd” which is equal to the string s. The string s is divisible by string t.

Since it passes the first test, look for the smallest string u that can be concatenated to create both strings s and t.

The string “bcd” is the smallest string that can be concatenated to create both strings s and t.

The length of the string u is 3, the integer value to return.

Example 2:

s = “bcdbcdbcd”

t = “bcdbcd”

If string t is concatenated twice, the result is “bcdbcdbcdbcd” which is greater than string s. There is an extra “bcd” in the concatenated string.

The string s is not divisible by string t, so return -1.

Function Description

Complete the function findSmallestDivisor in the editor below. The function should return a single integer denoting the length of the smallest string u if string s is divisible by string t, or return -1 if not.

findSmallestDivisor has the following parameter(s):

s : string s

t : string t

Constraints

1 ≤ size of s ≤ 2 x 105
1 ≤ size of t ≤ 2 x105
size of t ≤ size of s