PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

This multi-part problem evaluates algorithmic problem-solving skills across bit manipulation and number theory, sliding-window and frequency counting, monotonic-stack patterns, permutation and prefix reasoning, numerical simulation/optimization, and constrained-jump dynamic programming, testing complexity analysis and data-structure selection.

  • medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

Solve these algorithmic problems

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given the following independent coding tasks. For each task, design an algorithm and implement a function that returns the requested output. --- ## 1) Minimum operations to reduce `n` to `0` You are given a positive integer `n`. **Operation:** choose an integer `i >= 0` and replace `n` with `n - 2^i` or `n + 2^i`. Assume you must keep `n >= 0` after each operation. **Goal:** return the minimum number of operations needed to make `n = 0`. **Input:** `n` (fits in 64-bit signed integer) **Output:** minimum operations (integer) --- ## 2) Shortest subarray with at least `k` distinct integers Given an integer array `arr` and integer `k`, call a subarray **good** if it contains **at least `k` distinct** values. **Goal:** 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` → answer is `3` (e.g., subarray `[2,3,1]`). --- ## 3) First discount to the right (next <= price) Given an array `prices`. For each index `i`, find the first index `j > i` such that `prices[j] <= prices[i]`. - If such `j` exists, the final price is `prices[i] - prices[j]`. - Otherwise, the item is sold at full price `prices[i]`. **Return two things:** 1. The **sum** of all final prices. 2. The indices (0-based) of items sold at full price, in increasing order, as a space-separated string (or 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)`, say `k` is **balanced** if there exists some subarray `p[l..r]` that is a permutation of `1..k` (each of `1..k` appears exactly once in the subarray). **Goal:** for every `k = 1..n`, determine if `k` is balanced and return a binary string `s` of length `n` where `s[k-1] = '1'` if balanced else `'0'`. --- ## 5) Elevator + stairs: minimize time difference There are `n` floors to reach from floor 0 to floor `n`. You may take the elevator for exactly `x` floors first (where `0 <= x <= n`), then walk the remaining `n - x` floors. - Elevator: each elevator floor gives you `e1` energy and takes `t1` time. - After the elevator, you start stairs with `curr_energy = x * e1`. - Stairs: for each walked floor: - Time cost for that floor is `ceil(c / curr_energy)` (given constant `c > 0`). - Energy decreases by `e2` after climbing that floor. - Energy must never become negative during the stair process. **Goal:** choose `x` to minimize `|T_elevator(x) - T_stairs(x)|` and return that minimum absolute difference. If for some `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 score `arr[0]`, and must finish at index `n-1`. From index `i`, you may jump to: - `i + 1`, or - `i + d` where `d` is in the set `{3, 13, 23, 33, ...}` **and** `d` is prime (i.e., prime numbers whose last digit is 3). (Only jumps that stay within bounds are allowed.) **Goal:** return the maximum achievable score at `n-1`, or `-1` if `n-1` is unreachable. --- ## 7) Choose a root to minimize edge reversals You are given a directed graph on `n` nodes labeled `0..n-1` with `n-1` edges such that the underlying undirected graph is a tree. You may pick any node as the root. You want to reverse as few directed edges as possible so that **after reversals, every edge points away from the root**. **Goal:** return a root node that achieves the minimum number of reversals (if multiple, returning any one is acceptable). --- ## 8) Purchase optimization queries (consecutive buying from a position) Given an array `prices` (length `n`) and queries 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`. **Goal:** for each query, return the maximum number of items you can buy. Return an array of answers in query order. --- ## 9) Longest subsequence with sum limit (multiple queries) Given an array `nums` and an array `queries`. For each query value `q`, you may pick a subsequence (not necessarily contiguous) of `nums` to maximize the subsequence length such that the sum of chosen elements is `<= q`. **Goal:** return the maximum length for each query. --- ## 10) Maximize pipeline throughput under scaling budget There are `m` services in a pipeline. Service `i+1` consumes the output of service `i`. - Initial throughput is `throughput[i]`. - You may scale service `i` any number of times; each unit increase of throughput costs `scalecost[i]`. - Total spend across all services must be `<= budget`. Assume the end-to-end pipeline throughput equals `min(throughput[i])` after scaling. **Goal:** return the maximum achievable pipeline throughput. --- ## 11) Starting-from-each-level adventure scoring You are given arrays `layers` and `energy` of length `n`, and an initial energy `K`. If you start 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 remaining energy `>= energy[j]`, you pass the level and gain 1 point; otherwise you fail and the run stops immediately. **Goal:** return an array `score` of length `n` where `score[i]` is 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. If task `i` is done by person 1, you gain `reward1[i]`. If done by person 2, you gain `reward2[i]`. Constraint: person 1 must do **exactly** `k` tasks (and person 2 does the rest). **Goal:** maximize total reward and return that maximum. --- ## 13) Count palindromic downward paths ending at queried nodes in a tree You are given a tree of `treeNodes` nodes labeled `0..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 possibly `a = u`) is considered **palindromic-rearrangeable** if the multiset of letters along the path can be permuted to form a palindrome (equivalently: at most one character appears an odd number of times). You are given `queries`, a list of node indices. **Goal:** for each queried node `q`, return the number of ancestors `a` on the path from root to `q` such that the path `a -> ... -> q` is palindromic-rearrangeable. **Input format:** edges are provided by parallel arrays `nodeFrom`, `nodeTo` (undirected edges). **Output:** array of answers aligned with `queries`.

Quick Answer: This multi-part problem evaluates algorithmic problem-solving skills across bit manipulation and number theory, sliding-window and frequency counting, monotonic-stack patterns, permutation and prefix reasoning, numerical simulation/optimization, and constrained-jump dynamic programming, testing complexity analysis and data-structure selection.

Minimum Operations to Reduce n to 0

You are given a non-negative integer `n`. **Operation:** choose an integer `i >= 0` and replace `n` with `n - 2^i` or `n + 2^i`, keeping `n >= 0` after each step. **Goal:** return the minimum number of operations needed to make `n = 0`. The answer equals the number of nonzero digits in the non-adjacent form (NAF) of `n`: scan bits from least significant; on a run of trailing 1s it is cheaper to add 1 (turning the run into a single higher carry) than to clear each bit, so each maximal block of 1s costs at most 2 operations.

Constraints

  • 0 <= n < 2^63
  • n fits in a 64-bit signed integer

Examples

Input: (0,)

Expected Output: 0

Explanation: Already zero, no operations needed.

Input: (1,)

Expected Output: 1

Explanation: Subtract 2^0.

Input: (3,)

Expected Output: 2

Explanation: 3 -> 2 (subtract 2^0) -> 0 (subtract 2^1), two operations.

Input: (7,)

Expected Output: 2

Explanation: Add 1 (7 -> 8 = 2^3) then subtract 2^3, two operations instead of clearing three bits.

Input: (1000000000000,)

Expected Output: 12

Explanation: The non-adjacent form of 10^12 has 12 nonzero digits.

Hints

  1. Each operation adds or subtracts a single power of two, so the answer is the minimum number of signed powers of two that sum to n.
  2. That minimum equals the number of nonzero digits in the non-adjacent form (NAF) of n.
  3. Process bits from the bottom: a lone set bit costs 1; a run of consecutive set bits is cheaper to clear by adding 1 (creating one carry) than by subtracting each bit.

Shortest Subarray With At Least k Distinct Integers

Given an integer array `arr` and an integer `k`, a subarray is **good** if it contains **at least `k` distinct** values. **Goal:** return the length of the shortest good subarray, or `-1` if none exists. Use a sliding window: expand the right edge to gain distinct values, and whenever the window already has `>= k` distinct values, shrink from the left to find the shortest window ending at the current right index.

Constraints

  • 0 <= len(arr) <= 10^5
  • 1 <= k
  • values may repeat and may be negative

Examples

Input: ([1,2,2,3,1,4], 3)

Expected Output: 3

Explanation: [2,3,1] has 3 distinct values and length 3, the shortest possible.

Input: ([1,1,1], 2)

Expected Output: -1

Explanation: Only one distinct value exists, so no subarray has 2 distinct.

Input: ([], 1)

Expected Output: -1

Explanation: Empty array has no good subarray.

Input: ([5], 1)

Expected Output: 1

Explanation: A single element is one distinct value.

Input: ([1,2,1,2,3], 3)

Expected Output: 3

Explanation: The window [1,2,3] (indices 2..4) has 3 distinct values.

Hints

  1. A two-pointer sliding window works because adding elements only increases the distinct count and removing elements only decreases it.
  2. Keep a frequency map; the distinct count rises when a count goes 0 -> 1 and falls when it goes 1 -> 0.
  3. While the window has at least k distinct values, record its length and shrink from the left to find the minimum window ending at the current right pointer.

First Discount to the Right

Given an array `prices`, for each index `i` find the first index `j > i` with `prices[j] <= prices[i]`. - If such `j` exists, the item's final price is `prices[i] - prices[j]`. - Otherwise it is sold at full price `prices[i]`. **Return** a list `[total, full_indices]` where `total` is the sum of all final prices and `full_indices` is a space-separated string of the 0-based indices of items sold at full price (empty string if none). The "next element to the right that is `<=` the current" is a classic monotonic-stack problem solved in one right-to-left pass.

Constraints

  • 0 <= len(prices) <= 10^5
  • prices can be any integers

Examples

Input: ([8,4,6,2,3],)

Expected Output: [15, '3 4']

Explanation: Discounts: 8-4, 4-2, 6-2; index 3 (2) and index 4 (3) have no smaller-or-equal to the right. Sum = 4+2+4+2+3 = 15.

Input: ([10,1,1,6],)

Expected Output: [16, '2 3']

Explanation: 10-1, 1-1, then indices 2 and 3 are full price. Sum = 9+0+1+6 = 16.

Input: ([5],)

Expected Output: [5, '0']

Explanation: Single item, no j to the right, full price 5.

Input: ([],)

Expected Output: [0, '']

Explanation: No items, total 0, no full-price indices.

Input: ([3,3,3],)

Expected Output: [3, '2']

Explanation: Each price has an equal value to the right except the last; 3-3 + 3-3 + 3 = 3, only index 2 full price.

Hints

  1. For each i you need the nearest index to the right whose value is <= prices[i] - this is a next-smaller-or-equal element query.
  2. Sweep from right to left maintaining a stack of candidate indices, popping any whose value is strictly greater than the current price.
  3. After resolving nxt[], sum the discounts and collect indices where no qualifying j exists for the full-price list.

Balanced Prefixes in a Permutation

You are given a permutation `p` of `1..n`. Value `k` is **balanced** if some subarray `p[l..r]` is exactly a permutation of `1..k`. **Goal:** return a binary string `s` of length `n` where `s[k-1] = '1'` if `k` is balanced, else `'0'`. Key insight: since `p` is a permutation, the values `1..k` occupy `k` distinct positions. They form a contiguous subarray iff the span from their minimum position to their maximum position has width exactly `k`.

Constraints

  • 1 <= n <= 10^5
  • p is a permutation of 1..n

Examples

Input: ([1,2,3],)

Expected Output: 111

Explanation: Every prefix 1..k already sits contiguously at the front.

Input: ([2,3,1,5,4],)

Expected Output: 10101

Explanation: k=1 balanced ([1] at index 2); k=2 spans indices 0..2 width 3 != 2; k=3 spans 0..2 width 3; k=4 width 5 != 4; k=5 whole array.

Input: ([1],)

Expected Output: 1

Explanation: Single-element permutation, k=1 is trivially balanced.

Input: ([4,3,2,1],)

Expected Output: 1111

Explanation: A reversed permutation: every value set 1..k forms a contiguous suffix block.

Input: ([2,4,1,3],)

Expected Output: 1001

Explanation: k=1 balanced; k=2 and k=3 not contiguous; k=4 whole array.

Hints

  1. Record pos[v] = the index where value v sits.
  2. For a fixed k, the values 1..k occupy exactly k positions; they form one contiguous block iff (max position - min position + 1) == k.
  3. Sweep k from 1 to n, maintaining running min and max of the positions seen so far - this gives an O(n) one-pass solution.

Elevator and Stairs: Minimize Time Difference

You must reach floor `n` from floor 0. You ride the elevator for `x` floors (`0 <= x <= n`), then walk the remaining `n - x` floors. - Elevator: each floor gives `e1` energy and takes `t1` time, so `T_elevator(x) = x * t1` and you start stairs with `curr_energy = x * e1`. - Stairs: for each walked floor, time cost is `ceil(c / curr_energy)`, then energy drops by `e2`. Energy must never go negative. **Goal:** choose `x` to minimize `|T_elevator(x) - T_stairs(x)|`; skip any `x` whose stair phase becomes infeasible. Return the minimum absolute difference (or `-1` if no `x` is feasible).

Constraints

  • 0 <= x <= n
  • c > 0
  • energy must stay >= 0 throughout the stair phase

Examples

Input: (3, 2, 5, 1, 4)

Expected Output: 1

Explanation: x=1: elevator time 5, stairs ceil(4/2)+ceil(4/1)=2+4=6, diff=1 (minimum over all x).

Input: (2, 5, 1, 2, 10)

Expected Output: 1

Explanation: Best x yields difference 1.

Input: (1, 1, 1, 1, 1)

Expected Output: 1

Explanation: x=0 is infeasible (no stair energy); x=1 gives elevator time 1, no stairs, diff=1.

Input: (0, 3, 7, 2, 5)

Expected Output: 0

Explanation: n=0: only x=0, both times are 0.

Input: (4, 10, 1, 1, 1)

Expected Output: 0

Explanation: Plentiful energy lets a choice of x exactly balance the two phase times.

Hints

  1. Try every elevator count x from 0 to n; each fully determines both the elevator time and the starting stair energy.
  2. Simulate the stair phase floor by floor, adding ceil(c / curr_energy) and subtracting e2; if energy reaches 0 before a floor or drops below 0, that x is infeasible.
  3. Track the minimum |T_elevator - T_stairs| across all feasible x; return -1 if none are feasible.

Maximum Score With Special Jumps

Given an integer array `arr` of length `n`, start at index 0 with score `arr[0]` and finish at index `n-1`. From index `i` you may jump to `i+1`, or to `i+d` where `d` belongs to `{3, 13, 23, 33, ...}` (numbers ending in 3) **and** `d` is prime. Jumps must stay in bounds. **Goal:** return the maximum achievable score at `n-1`, or `-1` if it is unreachable. This is a maximum-weight path on a DAG (edges always go forward), so a left-to-right DP over indices works.

Constraints

  • 1 <= n
  • arr may contain negative values
  • allowed jumps are 1 and primes ending in digit 3

Examples

Input: ([1,2,3,4],)

Expected Output: 10

Explanation: 1->2->3->4 collects all values; the jump of 3 (0->3) gives only 1+4=5.

Input: ([5],)

Expected Output: 5

Explanation: Already at the last index with score 5.

Input: ([10,-5,-5,100],)

Expected Output: 110

Explanation: Jump of length 3 from index 0 to 3 skips the penalties: 10 + 100 = 110.

Input: ([1,2],)

Expected Output: 3

Explanation: Only a +1 step is possible: 1 + 2 = 3.

Input: ([3,-100,-100,-100,7],)

Expected Output: -90

Explanation: 0->3 (jump 3, -100) then ->4 (+1, 7): 3-100+7 = -90, better than stepping through every index.

Hints

  1. The only allowed jump lengths are 1 and primes whose last digit is 3 (3, 13, 23, 43, 53, ...); precompute those below n.
  2. All jumps go strictly forward, so process indices left to right with dp[i] = best score reaching i.
  3. Relax dp[i+s] = max(dp[i+s], dp[i] + arr[i+s]) for every allowed step s; the answer is dp[n-1] or -1 if it stayed unreachable.

Choose a Root to Minimize Edge Reversals

You are given a directed graph on `n` nodes (`0..n-1`) with `n-1` edges whose underlying undirected graph is a tree. Edges are given as a list of `[u, v]` meaning a directed edge `u -> v`. Pick any node as root; reverse as few directed edges as possible so every edge points **away from** the root. **Goal:** return a root achieving the minimum number of reversals (any one if several tie). Compute the cost for root 0 with one traversal, then re-root: moving the root across an edge flips that one edge's contribution, so each node's cost differs from its parent's by exactly +/-1.

Constraints

  • 1 <= n
  • edges form a tree on the underlying undirected graph
  • edges are directed u -> v

Examples

Input: (4, [[0,1],[1,2],[3,2]])

Expected Output: 0

Explanation: Rooting at 0 needs only the edge 3->2 reversed (1 reversal); other roots need more.

Input: (2, [[1,0]])

Expected Output: 1

Explanation: Edge points 1->0, so rooting at 1 needs zero reversals.

Input: (3, [[0,1],[0,2]])

Expected Output: 0

Explanation: Both edges already point away from 0, so 0 is optimal with 0 reversals.

Input: (1, [])

Expected Output: 0

Explanation: A single node is trivially the root with no edges.

Input: (5, [[1,0],[2,1],[3,2],[4,3]])

Expected Output: 4

Explanation: The chain points 4->3->2->1->0, already all away from node 4.

Hints

  1. Build an undirected adjacency list where traversing in the edge's true direction costs 0 and against it costs 1 (a reversal).
  2. A BFS/DFS from node 0 summing those costs gives the reversal count when 0 is the root.
  3. Re-root with a second traversal: crossing an edge from parent to child flips exactly that edge's contribution, so res[child] = res[parent] + (1 - 2*w). Return the argmin.

Consecutive Purchase Queries

Given `prices` of length `n` and queries `[pos, amount]` (`pos` is **1-based**): starting at index `pos-1`, buy items consecutively to the right while the running total cost stays `<= amount`. **Goal:** for each query, return the maximum number of items you can buy. Return the answers in query order. With a prefix-sum array (prices are non-negative so prefix sums are non-decreasing), each query is a binary search for the furthest reach whose cumulative cost stays within budget.

Constraints

  • 1 <= pos <= n
  • amount >= 0
  • prices are non-negative

Examples

Input: ([2,3,1,4], [[1,5],[2,4],[3,100],[4,3]])

Expected Output: [2, 2, 2, 0]

Explanation: From pos 1 budget 5 buys 2+3; from pos 2 budget 4 buys 3+1; from pos 3 budget 100 buys 1+4; from pos 4 budget 3 cannot afford the 4.

Input: ([5], [[1,4],[1,5]])

Expected Output: [0, 1]

Explanation: Budget 4 cannot afford price 5; budget 5 buys exactly one item.

Input: ([1,1,1,1], [[1,0],[1,4],[2,2]])

Expected Output: [0, 4, 2]

Explanation: Budget 0 buys nothing; budget 4 buys all four; from pos 2 budget 2 buys two items.

Input: ([10,20,30], [[1,100]])

Expected Output: [3]

Explanation: Budget 100 covers 10+20+30 = 60, so all three items.

Hints

  1. Precompute prefix sums so the cost of items [start, end) is prefix[end] - prefix[start].
  2. Because prices are non-negative, prefix sums are non-decreasing, enabling binary search.
  3. For each query find the largest end with prefix[end] <= prefix[start] + amount; the count is end - start.

Longest Subsequence With Sum Limit

Given an array `nums` and an array `queries`, for each query value `q` pick a subsequence of `nums` (any subset) maximizing its length subject to the chosen elements summing to `<= q`. **Goal:** return the maximum length for each query. To maximize count under a sum cap you greedily take the smallest elements: sort `nums`, build prefix sums, and binary search each query for how many of the smallest values fit.

Constraints

  • 0 <= len(nums)
  • elements assumed non-negative for the greedy to be optimal
  • queries can be any non-negative values

Examples

Input: ([4,5,2,1], [3,10,21,1])

Expected Output: [2, 3, 4, 1]

Explanation: Sorted [1,2,4,5], prefix [0,1,3,7,12]; q=3 fits {1,2}=2, q=10 fits {1,2,4}=3, q=21 fits all 4, q=1 fits {1}=1.

Input: ([], [0,5])

Expected Output: [0, 0]

Explanation: No elements to pick, every query yields 0.

Input: ([2,3], [1])

Expected Output: [0]

Explanation: Smallest element is 2 > 1, so nothing fits.

Input: ([1,1,1], [0,2,5])

Expected Output: [0, 2, 3]

Explanation: prefix [0,1,2,3]; budget 0 -> 0, budget 2 -> 2, budget 5 -> all 3.

Hints

  1. To maximize the number of chosen elements under a sum budget, always prefer the smallest values.
  2. Sort nums and take a prefix sum; prefix[k] is the smallest possible sum of any k elements.
  3. For each query q, binary search the largest k with prefix[k] <= q.

Maximize Pipeline Throughput Under Budget

A pipeline has `m` services in series; service `i+1` consumes service `i`'s output. Service `i` starts at `throughput[i]`, and each unit increase costs `scalecost[i]`. Total spend must be `<= budget`. End-to-end throughput is `min(throughput[i])` after scaling. **Goal:** return the maximum achievable pipeline throughput. The objective `min(throughput)` is monotonic in the target level `T`: higher `T` costs more. Binary search the largest `T` whose total raising cost stays within budget.

Constraints

  • 1 <= m
  • scalecost[i] >= 1
  • budget >= 0

Examples

Input: ([2,4,3], [1,2,1], 5)

Expected Output: 4

Explanation: Raising all to 4 costs (4-2)*1 + 0 + (4-3)*1 = 3 <= 5; reaching 5 would cost 7.

Input: ([5], [1], 100)

Expected Output: 105

Explanation: One service, every budget unit buys one throughput unit: 5 + 100.

Input: ([1,1], [1,1], 0)

Expected Output: 1

Explanation: No budget, throughput stays at the minimum of 1.

Input: ([3,3,3], [2,2,2], 6)

Expected Output: 4

Explanation: Raising all three from 3 to 4 costs 3*2 = 6 exactly; level 5 would cost 12.

Input: ([10,1], [100,1], 5)

Expected Output: 6

Explanation: Raise the cheap service (cost 1) from 1 to 6 for 5; the bottleneck min becomes 6 without touching the expensive service.

Hints

  1. The achievable throughput is some target level T that every service is raised to (services already above T are left alone).
  2. Cost to reach level T is sum over services with throughput[i] < T of (T - throughput[i]) * scalecost[i]; this is monotonically increasing in T.
  3. Binary search the largest T whose cost is within budget; start the search at the current minimum throughput.

Starting-From-Each-Level Adventure Scoring

Given arrays `layers` and `energy` of length `n` and initial energy `K`: starting at level `i` with energy `K`, for each level `j` from `i` upward you first pay `layers[j]` energy; if the remaining energy is `>= energy[j]` you pass (gain 1 point), otherwise the run stops. Energy must not go negative. **Goal:** return `score[i]` = number of consecutive levels passed starting from level `i`.

Constraints

  • 1 <= n
  • energy must remain >= 0 after paying each layer cost
  • K >= 0

Examples

Input: ([1,2,1], [0,0,0], 3)

Expected Output: [2, 2, 1]

Explanation: From 0: 3-1=2 pass, 2-2=0 pass, 0-1<0 stop -> 2. From 1: pass two. From 2: pass one.

Input: ([2,3], [1,1], 5)

Expected Output: [1, 1]

Explanation: From 0: 5-2=3>=1 pass, 3-3=0<1 stop -> 1. From 1: 5-3=2>=1 pass -> 1.

Input: ([5], [1], 3)

Expected Output: [0]

Explanation: 3-5 = -2 < 0, fail immediately.

Input: ([1,1,1], [0,0,0], 10)

Expected Output: [3, 2, 1]

Explanation: Ample energy passes every remaining level from each start.

Input: ([0,0], [0,0], 0)

Expected Output: [2, 1]

Explanation: Zero-cost zero-requirement levels always pass.

Hints

  1. For each starting level i, simulate forward: subtract layers[j], stop if energy goes negative.
  2. After paying, you pass only if the remaining energy is at least energy[j]; otherwise the run halts immediately.
  3. Count the consecutive passes from i; the straightforward double loop is O(n^2).

Assign Tasks With Exactly k for Person 1

There are `n` tasks. Task `i` gives `reward1[i]` if done by person 1, or `reward2[i]` if done by person 2. Person 1 must do **exactly** `k` tasks and person 2 does the rest. **Goal:** maximize total reward and return it. Start from giving every task to person 2 (`sum(reward2)`), then moving task `i` to person 1 changes the total by `reward1[i] - reward2[i]`. Pick the `k` largest such deltas.

Constraints

  • 0 <= k <= n
  • rewards may be any integers

Examples

Input: ([3,2,1], [1,2,3], 1)

Expected Output: 8

Explanation: Base sum(reward2)=6; deltas [2,0,-2], take the top one (2): 6+2=8.

Input: ([1,1], [1,1], 2)

Expected Output: 2

Explanation: All deltas 0; total stays at the base 2.

Input: ([5,1], [1,5], 0)

Expected Output: 6

Explanation: k=0, everything goes to person 2: 1+5=6.

Input: ([10,20,30], [5,5,5], 2)

Expected Output: 55

Explanation: Base 15; deltas [5,15,25], take top two (25+15=40): 15+40=55.

Input: ([1,2,3], [3,2,1], 3)

Expected Output: 6

Explanation: k=3 forces all to person 1: 1+2+3=6.

Hints

  1. Assign every task to person 2 first; the baseline total is sum(reward2).
  2. Reassigning task i to person 1 changes the total by exactly reward1[i] - reward2[i].
  3. To honor the 'exactly k' constraint while maximizing, pick the k largest deltas (even if some are negative).

Palindromic Downward Paths in a Tree

You are given a tree of `treeNodes` nodes (`0..treeNodes-1`) rooted at node 0, with lowercase labels in string `nodes`. Edges come as parallel arrays `nodeFrom`, `nodeTo` (undirected). A downward path ending at node `u` and starting at an ancestor `a` on the root-to-`u` path is **palindromic-rearrangeable** if its letters can form a palindrome (at most one letter has odd count). **Goal:** for each query node `q`, return how many ancestors `a` (including `q` itself) make the path `a -> ... -> q` palindromic-rearrangeable. Encode each path's letter parities as a 26-bit mask; a path is rearrangeable iff its mask has at most one set bit.

Constraints

  • 1 <= treeNodes
  • labels are lowercase a-z
  • edges given as undirected pairs forming a tree rooted at 0

Examples

Input: (3, 'aba', [0,1], [1,2], [0,1,2])

Expected Output: [1, 1, 2]

Explanation: Node 2 path a-b-a: paths ending at 2 that rearrange to a palindrome are 'a' (just node 2) and 'aba' (the whole path), giving 2.

Input: (1, 'a', [], [], [0])

Expected Output: [1]

Explanation: Single node, the length-1 path is trivially a palindrome.

Input: (4, 'aabb', [0,0,1], [1,2,3], [3])

Expected Output: [2]

Explanation: Path to node 3 is a-a-b; 'aab' rearranges to 'aba' and the single 'b' both qualify -> 2.

Input: (2, 'ab', [0], [1], [0,1])

Expected Output: [1, 1]

Explanation: Each node's only palindromic path is its own single letter; 'ab' has two odd-count letters.

Hints

  1. Represent the multiset of letters on a path by a 26-bit parity mask; the path can be rearranged into a palindrome iff the mask has 0 or 1 bits set (mask & (mask-1) == 0).
  2. Let pref[v] be the XOR of label bits from root to v. The path from ancestor a down to q has mask pref[q] XOR pref[parent(a)].
  3. During a DFS down to q, the candidate parent(a) masks are exactly the prefix masks of q's ancestors plus a virtual 0 for the root's parent; count how many make pref[q] XOR mask a near-power-of-two.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Deep Equality of Two Records - Uber (medium)
  • Shortest Path in a Grid with Blocked Cells - Uber (medium)
  • Design and Implement an LRU Cache - Uber (medium)
  • Reconstruct the Alphabet Order of an Alien Language - Uber (medium)
  • Maximize Throughput and Count Trigger Components - Uber (medium)