How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve weighted pick and product except self

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

##### Question LeetCode 528. Random Pick with Weight LeetCode 238. Product of Array Except Self https://leetcode.com/problems/random-pick-with-weight/description/ https://leetcode.com/problems/product-of-array-except-self/description/

Quick Answer: This question evaluates algorithm design and data-structure skills, focusing on weighted random selection and array aggregation for product computations within the Coding & Algorithms domain.

Random Pick with Weight (Deterministic Core)

You are given a 0-indexed array `w` of positive integers, where `w[i]` is the weight of index `i`. In the original problem (LeetCode 528), you implement `pickIndex()` which returns an index in `[0, len(w))` with probability proportional to its weight. The standard technique is to build a prefix-sum array of the weights and, given a uniformly random integer in `[1, total]`, binary-search for the first prefix value `>= target`. To make this testable deterministically, implement that core lookup directly: given the weight array `w` and an integer `target` in the range `[1, sum(w)]`, return the index that `target` lands in. Formally, build prefix sums `P[i] = w[0] + w[1] + ... + w[i]`. Return the smallest index `i` such that `target <= P[i]`. Example: w = [2, 5, 3, 4], target = 8 prefix = [2, 7, 10, 14] target 8 is the first value <= P[2]=10 (P[1]=7 < 8), so return 2. This is exactly the weighted-bucket selection a correct `pickIndex` performs once a random number has been drawn — verifying it confirms the prefix-sum + binary-search logic that the interview is really testing.

Constraints

1 <= len(w) <= 10^4
1 <= w[i] <= 10^5
1 <= target <= sum(w)

Examples

Input: ([1], 1)

Expected Output: 0

Explanation: Single bucket; any target in [1,1] picks index 0.

Input: ([1, 3], 1)

Expected Output: 0

Explanation: prefix=[1,4]; target 1 <= 1 so index 0.

Input: ([1, 3], 2)

Expected Output: 1

Explanation: prefix=[1,4]; target 2 > 1 but <= 4 so index 1.

Input: ([1, 3], 4)

Expected Output: 1

Explanation: prefix=[1,4]; target 4 lands on the last bucket, index 1.

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

Expected Output: 0

Explanation: prefix=[2,7,10,14]; target 1 <= 2 so index 0.

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

Expected Output: 0

Explanation: target 2 lands exactly on P[0]=2, index 0.

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

Expected Output: 1

Explanation: target 7 lands exactly on P[1]=7, index 1.

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

Expected Output: 2

Explanation: P[1]=7 < 8 <= P[2]=10, so index 2.

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

Expected Output: 2

Explanation: target 10 lands exactly on P[2]=10, index 2.

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

Expected Output: 3

Explanation: Last possible target equals total sum, index 3.

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

Expected Output: 1

Explanation: Equal weights; prefix=[5,10,15]; target 6 > 5 <= 10 so index 1.

Hints

Convert each weight into a cumulative range. Index i 'owns' the integers (P[i-1], P[i]].
With prefix sums sorted ascending, finding the owning index for a target is a classic lower-bound binary search: find the first prefix value that is >= target.
Be careful with the binary-search boundary: use a [lo, hi] window that converges to a single index, moving lo = mid+1 only when prefix[mid] < target.

Product of Array Except Self

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`. The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and **without using the division operation** (so you cannot just compute the total product and divide it out — that also fails when zeros are present). Example: nums = [1, 2, 3, 4] answer = [24, 12, 8, 6] (24 = 2*3*4, 12 = 1*3*4, etc.) Example with a zero: nums = [-1, 1, 0, -3, 3] answer = [0, 0, 9, 0, 0]

Constraints

2 <= len(nums) <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums fits in a 32-bit integer.

Examples

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

Expected Output: [24, 12, 8, 6]

Explanation: Standard case: 2*3*4=24, 1*3*4=12, 1*2*4=8, 1*2*3=6.

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

Expected Output: [0, 0, 9, 0, 0]

Explanation: Single zero: only the zero's own position gets a nonzero product (-1*1*-3*3=9); all others include the zero.

Input: ([2, 3],)

Expected Output: [3, 2]

Explanation: Two-element minimum: each gets the other.

Input: ([5],)

Expected Output: [1]

Explanation: Single element edge case: product of an empty set is 1.

Input: ([0, 0],)

Expected Output: [0, 0]

Explanation: Two zeros: every position still includes at least one zero, so all outputs are 0.

Input: ([1, 0],)

Expected Output: [0, 1]

Explanation: One zero: index 0 includes the zero (0); index 1 excludes it (1).

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

Expected Output: [12, 8, 6]

Explanation: All negatives: -3*-4=12, -2*-4=8, -2*-3=6.

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

Expected Output: [1, 1, 1, 1]

Explanation: All ones: every product is 1.

Hints

answer[i] = (product of everything to the left of i) * (product of everything to the right of i). Compute these two pieces separately.
First pass left-to-right: store in result[i] the running product of all elements strictly before i.
Second pass right-to-left: multiply result[i] by a running product of all elements strictly after i. This avoids division and naturally handles zeros.

Quick Overview

This question evaluates algorithm design and data-structure skills, focusing on weighted random selection and array aggregation for product computations within the Coding & Algorithms domain.