Round 1
Questions:
Question 1: Minimum Value Calculation by Replacing '!' in a Binary String
Problem:
You are given a string consisting of '0', '1', and '!', where '!' represents a character that can be replaced with either '0' or '1'. Additionally, you are given two integers x and y.
Your task is to replace all '!' characters in such a way that you minimize the calculated value based on the following rules:
- For every adjacent pair of characters:
- If the pair is '01', the contribution to the total is x.
- If the pair is '10', the contribution to the total is y.
Example:
-
Input:
- String:
'01!0' - x = 2
- y = 3
Output:
8Explanation:
- Replace
'!'with'0'to get'0100':- Pairs:
('01', '10')→ Contribution: (2 * 1 + 2 * 3 = 8)
- Pairs:
- Replace
'!'with'1'to get'0110':- Pairs:
('01', '10')→ Contribution: (2 * 2 + 2 * 3 = 10)
- Pairs:
- The minimum contribution is (8).
- String:
-
Input:
- String:
'!0!1' - x = 3
- y = 4
Output:
7Explanation:
- Replace the first '!' with '1' and the second '!' with '0' to get
'10'and'01':- Pairs:
('10', '01')→ Contribution: (3 + 4 = 7)
- Pairs:
- String:
Constraints:
- The string contains at least one '!', and its length is between 1 and (10^5).
- x and y are non-negative integers.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Question 2: Find First Index Where Prefix Sum Becomes Non-Positive
Problem:
You are given an array of integers representing inventory stock. Your task is to find the first index where the prefix sum of the array becomes non-positive (i.e., less than or equal to 0). The prefix sum is the cumulative sum of elements from the start of the array to the current element. If no such index exists, return -1.
Example:
- Input:
[1, 2]- Output:
-1(prefix sums are[1, 3], no non-positive sum)
- Output:
- Input:
[2, -4, 1]- Output:
2(prefix sums are[2, -2, -1], becomes non-positive at index 2)
- Output:
- Input:
[1, 2, 3, -6]- Output:
3(prefix sums are[1, 3, 6, 0], becomes non-positive at index 3)
- Output:
Constraints:
- The array contains at least one element, and its length is between 1 and (10^5).
- The integers in the array can range from (-10^9) to (10^9).
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.