Solve four algorithmic problems
Take-Home Project: Algorithmic Challenges
This project consists of four independent algorithmic problems. You are expected to provide optimal solutions for each.
1. Count Extendable Prefixes for '10' Subsequences
Given a binary string s and an integer k, you are allowed to append '0' or '1' to the end of s any number of times. A non-empty prefix p of s is considered valid if there exists a sequence of appends to p such that the total number of "10" subsequences in the resulting string is exactly k. A "10" subsequence is defined as a pair of indices (i, j) where i < j, s[i] = '1', and s[j] = '0'. Your task is to return the total count of such valid non-empty prefixes of s.
2. Maximize Alternating Four-Segment Sum
Given an integer array a of size n, you need to choose three cut indices i1, i2, and i3 such that 1 ≤ i1 ≤ i2 ≤ i3 ≤ n+1. These cuts divide the array into four contiguous segments: s1 = a[1..i1-1], s2 = a[i1..i2-1], s3 = a[i2..i3-1], and s4 = a[i3..n]. Note that segments can be empty if cuts coincide or are at the array ends. The objective is to maximize the value = sum(s1) - sum(s2) + sum(s3) - sum(s4). Return the maximum possible value. The array size n is at most 3 * 10^3.
3. Select the Largest Agreeable Developer Team
You are given n developers, where each developer i (for 1 ≤ i ≤ n) has a unique skill level i. You are also provided with two arrays: lowerSkill[1..n] and higherSkill[1..n]. Your task is to select the largest possible subset T of developers such that for every developer i chosen to be in T, the following conditions are met:
- At most
lowerSkill[i]members ofThave a skill level less thani. - At most
higherSkill[i]members ofThave a skill level greater thani. Return the size of the largest such subsetT.
4. Find All Achievable MEX Values with Bounded Increments
You are given n memory blocks, represented by an array memoryBlocks[0..n-1]. You can repeatedly perform an operation: choose an index x and increase memoryBlocks[x] by 1, but only if memoryBlocks[x] < n - 1. After any number of these operations, the MEX (Minimum Excluded Value) of the array is defined as the smallest non-negative integer that is not present in the array. Your goal is to find and return all distinct MEX values that can be achieved, listed in ascending order.
AI interview prep
Core dilemma
Demonstrating broad command of algorithmic techniques, problem-solving strategies, and optimization skills across diverse problem types, while managing time effectively for a multi-problem take-home project.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Solve four algorithmic problems
Take-Home Project: Algorithmic Challenges
This project consists of four independent algorithmic problems. You are expected to provide optimal solutions for each.
1. Count Extendable Prefixes for '10' Subsequences
Given a binary string s and an integer k, you are allowed to append '0' or '1' to the end of s any number of times. A non-empty prefix p of s is considered valid if there exists a sequence of appends to p such that the total number of "10" subsequences in the resulting string is exactly k. A "10" subsequence is defined as a pair of indices (i, j) where i < j, s[i] = '1', and s[j] = '0'. Your task is to return the total count of such valid non-empty prefixes of s.
2. Maximize Alternating Four-Segment Sum
Given an integer array a of size n, you need to choose three cut indices i1, i2, and i3 such that 1 ≤ i1 ≤ i2 ≤ i3 ≤ n+1. These cuts divide the array into four contiguous segments: s1 = a[1..i1-1], s2 = a[i1..i2-1], s3 = a[i2..i3-1], and s4 = a[i3..n]. Note that segments can be empty if cuts coincide or are at the array ends. The objective is to maximize the value = sum(s1) - sum(s2) + sum(s3) - sum(s4). Return the maximum possible value. The array size n is at most 3 * 10^3.
3. Select the Largest Agreeable Developer Team
You are given n developers, where each developer i (for 1 ≤ i ≤ n) has a unique skill level i. You are also provided with two arrays: lowerSkill[1..n] and higherSkill[1..n]. Your task is to select the largest possible subset T of developers such that for every developer i chosen to be in T, the following conditions are met:
- At most
lowerSkill[i]members ofThave a skill level less thani. - At most
higherSkill[i]members ofThave a skill level greater thani. Return the size of the largest such subsetT.
4. Find All Achievable MEX Values with Bounded Increments
You are given n memory blocks, represented by an array memoryBlocks[0..n-1]. You can repeatedly perform an operation: choose an index x and increase memoryBlocks[x] by 1, but only if memoryBlocks[x] < n - 1. After any number of these operations, the MEX (Minimum Excluded Value) of the array is defined as the smallest non-negative integer that is not present in the array. Your goal is to find and return all distinct MEX values that can be achieved, listed in ascending order.