Solve 12 coding interview problems

Below are multiple independent coding problems.

Problem 1: Reduce an integer to 0 with $\pm 2^i$

You are given a positive integer $n$. In one operation you may replace $n$ with $n + 2^i$ or $n - 2^i$ for any integer $i \ge 0$.

Task: Return the minimum number of operations needed to make $n = 0$.

Constraints (typical): $1 \le n \le 10^{18}$.

Problem 2: Shortest subarray with at least $k$ distinct integers

You are given an integer array arr of length $n$ and an integer $k$.

A subarray is good if it contains at least $k$ distinct values.

Task: Return the length of the shortest good subarray. If no such subarray exists, return -1.

Constraints (typical): $1 \le n \le 2\times 10^5$.

Problem 3: Apply the first valid discount to the right

You are given an array prices.

For each index i, define the discount as the first index j > i such that prices[j] <= prices[i].

• If such j exists: final[i] = prices[i] - prices[j]
• Otherwise: final[i] = prices[i] (sold at full price)

Task: Output:

1. The sum of all final prices.
2. The list of 0-based indices that are sold at full price, in increasing order.

Constraints (typical): $1 \le n \le 2\times 10^5$.

Problem 4: Max-score jump game with special prime jumps

You are given an integer array arr of length $n$. You start at index 0 and must end at index n-1.

From index i, you may jump to:

• i + 1 , or
• i + p where p is a prime number and p % 10 == 3 (e.g., 3, 13, 23, 43, ...), and i + p < n .

Your score is the sum of arr values on all visited indices (including start and end).

Task: Return the maximum achievable score when reaching n-1. If n-1 is unreachable, return -1.

Constraints (typical): $1 \le n \le 2\times 10^5$, arr[i] may be negative.

Problem 5: Count ancestor endpoints whose path can be permuted into a palindrome

You are given a rooted tree with nodes 0..n-1 (root is node 0). Each node has a lowercase letter.

Input is provided as:

• treeNodes = n
• nodes : a char array of length n , where nodes[i] is the character on node i
• nodeFrom , nodeTo : arrays of length n-1 describing directed parent→child edges ( nodeFrom[i] -> nodeTo[i] ), forming a tree
• queries : array of start nodes

For each query start node u:

• Consider all endpoints v on the path from u up to the root 0 (i.e., v can be u , its parent, ..., 0 ).
• Let the multiset of characters on the path u -> ... -> v (inclusive) be collected.
• This path is counted if its characters can be rearranged into a palindrome (i.e., at most one character has an odd frequency).

Task: For each query u, return how many such endpoints v exist.

Constraints (typical): $n, q \le 2\times 10^5$.

Problem 6: Maximize pipeline throughput under a scaling budget

You have $n$ services connected in a pipeline. The pipeline throughput is:

$T = \min_i throughput[i]$

You may scale service i any number of times. Each scaling:

• increases throughput[i] by 1
• costs scale_cost[i]

Given integer budget, total scaling cost must be $\le budget$.

Task: Return the maximum achievable pipeline throughput T.

Constraints (typical): $n \le 2\times 10^5$, values up to $10^{18}$.

Problem 7: Elevator-then-stairs with energy-dependent stair time

You must go from floor 0 to floor N.

You may take the elevator first from floor 0 to floor x (choose x once, 0 <= x <= N).

• For each elevator floor ascended: gain e1 energy and spend t1 time.
• After elevator: your energy is E = x * e1 .

Then you must climb the remaining N - x floors using stairs. For each stair floor:

• At the start of the floor, if current energy is E , the time spent is ceil(c / E) .
• Then you spend e2 energy: E := E - e2 .
• Energy may never become negative; if E < 0 at any step, that choice of x is invalid.

Task: Choose x to minimize total time. If no x is feasible, return -1.

Constraints (typical): $1 \le N \le 10^6$, parameters are positive integers.

Problem 8: Assign tasks to two people with exactly $k$ tasks for person A

You have n tasks. If task i is done by:

• person A: reward reward1[i]
• person B: reward reward2[i]

Each task must be assigned to exactly one person. Person A must do exactly k tasks.

Task: Return the maximum possible total reward.

Constraints (typical): $n \le 2000$, $0 \le k \le n$.

Problem 9: Score from each start index with energy thresholds

You are given:

• layers[0..n-1] : energy cost to attempt/pass level j
• energyReq[0..n-1] : minimum remaining energy needed after paying the cost to pass level j
• initial energy K

Starting from index i:

• Set E = K .
• For j = i..n-1 :
  1. Pay the level cost: E := E - layers[j] . If E < 0 , stop.
  2. If E >= energyReq[j] , you pass and gain 1 point; otherwise stop (cannot proceed further).

Task: Return an array score of length n where score[i] is the number of points you can earn starting at level i.

Note: An $O(n^2)$ solution will time out; design a faster approach.

Problem 10: Buy the maximum number of consecutive items per query

You are given prices[0..n-1] (positive integers). Each query provides:

• pos (1-based starting index)
• amount (budget)

From index start = pos - 1, you can buy items consecutively to the right while the running sum does not exceed amount.

Task: For each query, return the maximum number of items you can buy.

Constraints (typical): $n, q \le 2\times 10^5$.

Problem 11: Minimum edge reversals so every node can reach the chosen root

You are given n nodes and n-1 directed edges edges[i] = [a, b] meaning a -> b. Ignoring direction, the graph is a tree.

For each node r considered as the root, you may reverse any subset of edges.

Task: Compute res[r] = the minimum number of edge reversals required so that every node has a directed path to r (equivalently, all edges point toward r along the tree). Return res for all r.

Constraints (typical): $n \le 2\times 10^5$.

Problem 12: For each $w$, do values $1..w$ occupy a contiguous block?

You are given a permutation perm[0..n-1] containing each integer from 1 to n exactly once.

For each window size $w = 1..n$, define ans[w] = 1 if the positions of the numbers {1,2,...,w} in perm form a contiguous subarray (in any order). Otherwise, ans[w] = 0.

Equivalently, let pos[x] be the index where value x appears. Then ans[w] = 1 iff:

$\max_{1\le x\le w} pos[x] - \min_{1\le x\le w} pos[x] + 1 = w.$

Task: Return ans[1..n].

Constraints (typical): $n \le 2\times 10^5$.