Round 1
Questions: Given an array arr of size n of positive integers, you can perform the following operation any number of times (possibly zero) :-
- Choose a prefix of size s (1 <= s <= n) that doesn't contain any zero (there is no index i such that arr[i] = 0 and 1 <= i <= s)
- Decrease all values of this prefix by one i.e., set
arr[i] = arr[i] - 1 for all 1 <= i <= s
.
Find the maximum number of zeroes that the array arr can contain after performing any number of operations on the array.
Example
n = 5 arr = [4,3,5,5,3]
Output
3
| Current Array | Prefix Size | New Array | |------------|------------|------------| | [4,3,5,5,3] | 5 | [3,2,4,4,2] | | [3,2,4,4,2] | 5 | [2,1,3,3,1] | | [2,1,3,3,1] | 5 | [1,0,3,3,0] | | [1,0,3,3,0] | 1 | [0,0,3,3,0] |
Constraints:
1 <= arr.length <= 10^5
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 2
Questions:
You are given two strings, a text string text
, and a regex expression regex
. The string regex
contains exactly one wildcard character (). A wildcard character () matches any sequence of zero or more lowercase English characters. A regex matches some string if it's possible to replace the wildcard character with some sequence of characters such that the regex expression becomes equal to the string. No other character can be changed.
For example, regex "abc*bcd" matches "abcbcd", "abcefgbcd" whereas it does not match the string "abcbd", "abzbcd", "abcd".
Example Given text = "hackerrank", regex = "ack*r"
The following substring match regex:
- "acker", can we replace * with "e", length = 5
- "ackerr", we can replace * with "er" and regex becomes equal to "ackerr" length = 6.
Final solution
6
Constraints:
1 <= regex.length <= text.length <= 10^6 string consists of only lowercase alphabets
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.