Round 1
Questions:
Question 1
Amazon is introducing an innovative smart canvas display for personalized home decor. The canvas is initially painted white, featuring n rows and m columns, waiting to be transformed into a beautiful masterpiece. Each minute, the canvas undergoes a unique coloring process as specified by the user.
A beautiful canvas is defined by the presence of a square with a side length of k, where all cells within the square are elegantly colored.
Determine the minimum time required for the canvas to achieve its beauty.
Formally, Given n and m that denote the number of rows and columns of the canvas respectively, k denotes the size of the square, and a 2D array paint of dimensions (n * m) rows and 2 columns, where each entry (paint[i][0], paint[i][1]) represents the coordinates of a cell to be painted black during the i-th minute.
Note that each cell is painted only once during this transformation.
Find the minimum time (in minutes) after which the canvas becomes beautiful.
Function Description
Complete the function findFirstBeautifulMoment in the editor below.
findFirstBeautifulMoment has the following parameters:
int n: the number of rows in the canvasint m: the number of columns in the canvasint k: the side length of the black squareint paint[n*m][2]: a 2-D array of integers denoting the positions of the cells that will be painted black every minute
Returns
int: the minimum time (in minutes) after which the canvas becomes beautiful
Example
n = 2 m = 3 k = 2 paint = [ [1, 2], [2, 3], [2, 1], [1, 3], [2, 2], [1, 1]]
Question 2
A team of developers at Amazon is working on a feature that checks the strength of a password as it is set by a user.
Analysts found that people use their personal information in passwords, which is insecure. The feature searches for the presence of a reference string as a subsequence of any permutation of the password. If any permutation contains the reference string as a subsequence, then the feature determines the minimum cost to remove characters from the password so that no permutation contains the string reference as a subsequence.
The removal of any character has a cost given in an array, cost, with 26 elements that represent the cost to replace 'a' (cost[0]) through 'Z' (cost[25]). Given two strings password and reference, determine the minimum total cost to remove characters from password so that no permutation contains the string reference as a subsequence.
Example
Suppose password = "adefgh", reference = "hf", and cost = [1, 0, 0, 2, 4, 4, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0].
Answer: 1
Example 2
password = "abcdcbcb", reference = "bcb" cost = [2, 3, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Output: 3
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.