I was tested on the last two of these. My solutions passed all the test cases. All of the questions below are from 1point3acres.
Prefix Count of "10"
Given a binary string sequence of length n, you can perform the following operation any number of times: append a '0' or '1' to the end of the sequence. After updating the sequence (i.e. appending characters to the end of the original sequence), if the total number of "10" subsequences equals exactly k, the sequence is considered valid. Your task is to compute the total number of valid non-empty prefixes of the given binary sequence.
def count_10_subsequences(s: str) -> int:
"""
Counts the number of "10" subsequences in the string.
Traversal order: right to left, pairing each '1' with the '0's seen so far.
"""
count_0 = 0
count_10 = 0
count_1 = 0
for ch in reversed(s):
if ch == '0':
count_0 += 1
elif ch == '1':
count_10 += count_0
count_1 += 1
return count_10, count_1, count_0
def count_valid_prefixes(s: str, k: int) -> int:
"""
Computes how many non-empty prefixes can be extended so the number of "10" subsequences equals exactly k.
"""
n = len(s)
result = 0
for i in range(1, n + 1):
prefix = s[:i]
cnt_10, count_1, count_0 = count_10_subsequences(prefix)
if cnt_10 == k:
result += 1
elif k > cnt_10 and k - cnt_10 >= count_1:
result += 1
print(f"Prefix: {prefix}, count_10: {cnt_10}, count_1: {count_1}, count_0: {count_0}, result: {result}")
return result
Special Sum (grossValue)
Quoting another forum member's description: "Basically you cut an array into four segments and ask for the maximum value of sub1 - sub2 + sub3 - sub4 (cuts are allowed at the same position, or at the very start or very end of the array — there are a lot of edge cases). n goes up to 310^3. I maintained preSum and postSum and enumerated the cut positions, O(n^3), which only passed 60%. I didn't have an idea for how to optimize it. For this problem, based on the formula below, you can see the total splits into two parts (s1-s2)+(s3-s4), so the position where you split s2 and s3 matters. If you enumerate that position from 1 to n, and split s2 and s3 at x, the total is equivalent to s1-(sum(1-x)-s1)+(sum(x-n)-s4)-s4) = 2(s1-s4)-sum(1-x)+sum(x-n). So you only need the max s1 and the min s4, which are a prefix sum and a suffix sum respectively. So by spending O(n) preprocessing left to right — the largest prefix sum seen by the time each number is the last one used, and a similarly-defined minimum suffix sum — the original problem can also be solved in O(n) time."
def max_gross_value(arr):
"""
Computes the maximum grossValue for the given array.
grossValue(i1, i2, i3) = sum[1, i1) - sum[i1, i2) + sum[i2, i3) - sum[i3, n+1)
Split into s1 - s2 + s3 - s4, where indices are 1-based half-open intervals.
Args:
arr (List[int]): input array, 0-based (but logically we treat it as 1-based)
Returns:
int: the maximum grossValue
"""
n = len(arr)
# Build the prefix sum array: prefix[i] represents sum[1, i); note 1-based means prefix[1] = arr[0]
prefix = [0] * (n + 2)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] + arr[i - 1]
prefix[n + 1] = prefix[n]
result = float('-inf')
# Enumerate the middle split point i2 (the second cut), 1 <= i2 <= n+1
for i2 in range(1, n + 2):
max_left = float('-inf') # stores the max value of s1 - s2
for i1 in range(1, i2 + 1):
s1 = prefix[i1 - 1]
s2 = prefix[i2 - 1] - prefix[i1 - 1]
max_left = max(max_left, s1 - s2)
max_right = float('-inf') # stores the max value of s3 - s4
for i3 in range(i2, n + 2):
s3 = prefix[i3 - 1] - prefix[i2 - 1]
s4 = prefix[n] - prefix[i3 - 1]
max_right = max(max_right, s3 - s4)
result = max(result, max_left + max_right)
return result
Developer and Skill
There are n developers, where the skill level of the ith developer is given by i, for 1 ≤ i ≤ n. The task is to form a team of developers for a hackathon. A developer agrees to be on the team only if certain conditions are met. Given two arrays, lowerSkill and higherSkill, the ith developer will join the team if at most lowerSkill[i] team members have a lower skill level than them, and at most higherSkill[i] team members have a higher skill level than them. The objective is to select the largest possible team such that every developer on the team agrees with the team composition based on these conditions. Example: Given n = 5, lowerSkill = [1, 3, 2, 2, 2], higherSkill = [2, 2, 1, 1, 3]. It is optimal to select developers with skill levels 1, 3, and 4. For the developer with skill level 1, there are two developers with higher skill levels and higherSkill[1] = 2. For the developer with skill level 3, there is one developer with a lower skill level and one with a higher skill level (lowerSkill[3] = 2, higherSkill[3] = 1). For the developer with skill level 4, there are two developers with lower skill levels. Thus, all three developers are content. Hence, the number of developers selected for the hackathon team will be 3.
def max_team_size(n, lowerSkill, higherSkill):
def can_form_team(size):
cnt = 0 # number of members currently on the team
for i in range(n):
# check whether this person can join as the cnt-th member
if lowerSkill[i] >= cnt and higherSkill[i] >= (size - 1 - cnt):
cnt += 1
if cnt == size:
return True
return False
# binary search on the answer
low, high = 0, n
best = 0
while low <= high:
mid = (low + high) // 2
if can_form_team(mid):
best = mid
low = mid + 1
else:
high = mid - 1
return best
MEX
There are n memory blocks, where the size of the ith memory block is given by the array memoryBlocks[i], with 0 ≤ i < n. The following operation can be performed on memoryBlocks any number of times: choose an index x. The size of memoryBlocks[x] can be increased by 1, but only if memoryBlocks[x] is less than n-1. After performing any number of operations, the smallest non-negative integer k that is not in memoryBlocks is called a Valid Size, or MEX (minimum excluded value). The task is to return an array of all the valid sizes achievable through memoryBlocks, sorted in ascending order.
def findAllMEX(n, memoryBlocks):
freq = [0] * (n + 1)
for num in memoryBlocks:
if num <= n:
freq[num] += 1
mex = []
total = 0
for i in range(n + 1):
if total >= i:
mex.append(i)
total += freq[i]
return mex
Discussion
Loading comments…