OA Question 1: Unequal Elements
Given an array skills of length n, where each element denotes a question’s skill type, find the longest subsequence in which there are at most k transitions between different skills.
Python Solution
def max_subsequence_with_k_transitions(skills, k):
n = len(skills)
groups = []
curr, count = skills[0], 1
for x in skills[1:]:
if x == curr:
count += 1
else:
groups.append((curr, count))
curr, count = x, 1
groups.append((curr, count))
max_len = 0
start = 0
transitions = 0
curr_len = groups[0][1]
for end in range(1, len(groups)):
if transitions + 1 k:
curr_len -= groups[start][1]
if groups[start][0] != groups[start + 1][0]:
transitions -= 1
start += 1
transitions += 1
curr_len += groups[end][1]
max_len = max(max_len, curr_len)
# consider no-transition case
max_len = max(max_len, max(cnt for _, cnt in groups))
return max_len
OA Question 2: String Search
You have a source string and a target string. Characters from source are removed one by one in the order specified by the permutation order. Find the maximum number of removals so that target remains a subsequence of the modified source.
Python Solution
def getMaximumRemovals(order, source, target):
def is_subseq(k):
removed = [False] * len(source)
for i in range(k):
removed[order[i]] = True
t = 0
for i, ch in enumerate(source):
if not removed[i] and t < len(target) and ch == target[t]:
t += 1
return t == len(target)
left, right, ans = 0, len(source), 0
while left <= right:
mid = (left + right) // 2
if is_subseq(mid):
ans = mid
left = mid + 1
else:
right = mid - 1
return ans
# Example
source = "abbabaa"
target = "bb"
order = [6, 0, 1, 4, 3, 2, 5]
print(getMaximumRemovals(order, source, target))
Read More
- Snowflake spring 2024 internship OA
- Company: Snowflake – 一亩三分地
- TOP 30+ Snowflake Interview Questions and Answers (2024)
Contact Us
If you need interview assistance or OA ghostwriting services, please contact us.
END
