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).