Take-Home Project: Algorithmic Challenges

This take-home project consists of a series of independent coding tasks. For each task, you are required to design an algorithm and implement a function that returns the specified output.

1. Minimum Operations to Reduce n to 0

Given a positive integer n, determine the minimum number of operations required to transform n to 0. An operation involves choosing an integer i >= 0 and replacing n with either n - 2^i or n + 2^i. It must be ensured that n remains non-negative after each operation.

• Input: n (a 64-bit signed integer)
• Output: Minimum operations (integer)

2. Shortest Subarray with at Least k Distinct Integers

Given an integer array arr and an integer k, identify a "good" subarray as one that contains at least k distinct values. Your goal is to return the length of the shortest good subarray. If no such subarray exists, return -1.

• Example: arr = [1, 2, 2, 3, 1, 4], k = 3 → The answer is 3 (e.g., the subarray [2,3,1]).

3. First Discount to the Right (Next <= Price)

Given an array prices, for each index i, you need to find the first index j > i such that prices[j] <= prices[i].

• If such a j exists, the final price for item i is prices[i] - prices[j].
• Otherwise, the item i is sold at its full price prices[i].

Your function should return two values:

1. The sum of all final prices.
2. The 0-based indices of items sold at full price, in increasing order, as a space-separated string (or an empty string if none).

4. Balanced Prefixes in a Permutation

You are given a permutation p of 1..n.

For a given k (1 <= k <= n), k is considered balanced if there exists some subarray p[l..r] that is a permutation of 1..k (meaning each integer from 1 to k appears exactly once within that subarray).

Your task is to determine for every k = 1..n if k is balanced. Return a binary string s of length n, where s[k-1] = '1' if k is balanced, and '0' otherwise.

5. Elevator + Stairs: Minimize Time Difference

To travel from floor 0 to floor n, you can take an elevator for exactly x floors (where 0 <= x <= n), and then walk the remaining n - x floors using stairs.

• Elevator: Each floor traveled by elevator costs t1 time and grants e1 energy.
• Stairs: After the elevator, you start the stairs with curr_energy = x * e1. For each walked floor:
  • The time cost for that floor is ceil(c / curr_energy) (where c > 0 is a given constant).
  • Your energy decreases by e2 after climbing that floor.
  • Energy must never become negative during the stair process.

Your goal is to choose x such that the absolute difference between the total elevator time T_elevator(x) and the total stairs time T_stairs(x) is minimized. Return this minimum absolute difference. If for any x the stairs part is infeasible due to energy dropping below 0, that x cannot be chosen.

6. Maximum Score to Reach End with Special Jumps

Given an integer array arr of length n, you start at index 0 with a score equal to arr[0] and must reach index n-1.

From index i, you can jump to:

• i + 1, or
• i + d, where d is in the set {3, 13, 23, 33, ...} and d is a prime number (i.e., prime numbers whose last digit is 3).

Only jumps that stay within the array bounds are allowed.

Return the maximum achievable score at index n-1, or -1 if n-1 is unreachable.

7. Choose a Root to Minimize Edge Reversals

You are given a directed graph with n nodes labeled 0 to n-1 and n-1 edges. The underlying undirected graph is a tree.

You may select any node as the root. Your objective is to reverse the minimum number of directed edges such that, after reversals, every edge points away from the chosen root.

Return the label of a root node that achieves this minimum number of reversals. If multiple such roots exist, any one is acceptable.

8. Purchase Optimization Queries (Consecutive Buying from a Position)

Given an array prices (length n) and a list of queries, each of the form (pos, amount):

• pos is 1-based.
• Starting at index pos-1, you can buy items consecutively to the right as long as the total cost does not exceed amount.

For each query, return the maximum number of items you can buy. The answers should be returned in an array, in the order of the input queries.

9. Longest Subsequence with Sum Limit (Multiple Queries)

Given an array nums and an array queries.

For each query value q, you need to select a subsequence (not necessarily contiguous) of nums such that its length is maximized and the sum of its chosen elements is <= q.

Return an array containing the maximum length for each query, in query order.

10. Maximize Pipeline Throughput Under Scaling Budget

There are m services in a pipeline, where service i+1 consumes the output of service i.

• Each service i has an initial throughput throughput[i].
• You can scale service i any number of times; each unit increase of throughput costs scalecost[i].
• The total expenditure across all services must not exceed budget.

Assume that the end-to-end pipeline throughput is determined by the minimum throughput of any service after scaling.

Your goal is to return the maximum achievable end-to-end pipeline throughput.

11. Starting-from-Each-Level Adventure Scoring

You are given arrays layers and energy, both of length n, and an initial energy K.

If you start an adventure at level i with current energy K:

• To attempt level j (starting from j=i and increasing):
  1. You must pay layers[j] energy.
  2. After paying, if your remaining energy is >= energy[j], you pass the level and gain 1 point; otherwise, you fail, and the adventure run stops immediately.

Return an array score of length n, where score[i] represents the number of consecutive levels you can pass starting from level i.

12. Assign Tasks to Two People with Exactly k Tasks for Person 1

There are n tasks. For each task i, if it is done by person 1, you gain reward1[i]. If it is done by person 2, you gain reward2[i].

Constraint: Person 1 must perform exactly k tasks, and person 2 will perform the remaining tasks.

Your objective is to maximize the total reward and return that maximum value.

13. Count Palindromic Downward Paths Ending at Queried Nodes in a Tree

You are given a tree with treeNodes nodes labeled 0 to treeNodes-1, rooted at node 0. Each node u has a lowercase letter label nodes[u].

A downward path that ends at node u and starts at some ancestor a on the root-to-u path (including a = u) is considered palindromic-rearrangeable if the multiset of letters along the path can be permuted to form a palindrome. (This is equivalent to saying at most one character appears an odd number of times in the path's multiset of letters).

You are given queries, a list of node indices.

For each queried node q, return the number of ancestors a on the path from the root to q such that the path a -> ... -> q is palindromic-rearrangeable.

• Input format: Edges are provided by parallel arrays nodeFrom and nodeTo (representing undirected edges).
• Output: An array of answers aligned with the queries.