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

What role is this question designed for?

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

Solve Three Array Coding Problems | Visa Coding Question

Quick Overview

This multi-part question evaluates algorithmic problem-solving skills in array manipulation, optimization (maximizing capped contributions), modular combinatorics (counting divisible-sum triplets), and sequence selection/dynamic decision-making for longest selectable non-decreasing subarrays.

Solve Three Array Coding Problems

Company: Visa

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

An online assessment contains the following three independent coding problems. For each problem, write a function that returns the requested value. Use 64-bit integers where sums or counts may overflow 32-bit integers. ### Problem 1: Maximize the capped contribution after boosting values You are given two integer arrays `a` and `b` of the same length `n`, and an integer `k`. For every index `i`, the default contribution to the total score is: `min(a[i], b[i])` You may choose at most `k` distinct indices. For each chosen index `i`, you double `b[i]` once, so that the contribution at that index becomes: `min(a[i], 2 * b[i])` Each index can be chosen at most once. Return the maximum possible total score after choosing up to `k` indices. Constraints may be assumed as: - `1 <= n <= 200000` - `0 <= k <= n` - `0 <= a[i], b[i] <= 10^9` ### Problem 2: Count triplets with a divisible sum You are given an integer array `nums` and a positive integer `d`. Return the number of index triplets `(i, j, k)` such that: - `0 <= i < j < k < nums.length` - `(nums[i] + nums[j] + nums[k])` is divisible by `d` Constraints may be assumed as: - `3 <= nums.length <= 200000` - `1 <= d <= 200000` - `-10^9 <= nums[i] <= 10^9` ### Problem 3: Find the longest selectable non-decreasing subarray You are given two integer arrays `A` and `B` of the same length `n`. For a contiguous subarray of indices `[l, r]`, you may choose exactly one value at each index `i`: either `A[i]` or `B[i]`. The chosen values must form a non-decreasing sequence: `chosen[l] <= chosen[l + 1] <= ... <= chosen[r]` Return the maximum possible length of such a contiguous subarray. Constraints may be assumed as: - `1 <= n <= 200000` - `-10^9 <= A[i], B[i] <= 10^9`

Quick Answer: This multi-part question evaluates algorithmic problem-solving skills in array manipulation, optimization (maximizing capped contributions), modular combinatorics (counting divisible-sum triplets), and sequence selection/dynamic decision-making for longest selectable non-decreasing subarrays.

Part 1: Maximize the Capped Contribution After Boosting Values

You are given two integer arrays `a` and `b` of equal length `n`, and an integer `k`. At index `i`, the default contribution is `min(a[i], b[i])`. You may choose at most `k` distinct indices. For each chosen index `i`, you double `b[i]` once, so that the contribution at that index becomes `min(a[i], 2 * b[i])`. Return the maximum possible total contribution after applying this operation to up to `k` indices.

Constraints

`1 <= len(a) == len(b) <= 200000`
`0 <= k <= n`
`0 <= a[i], b[i] <= 10^9`
Use 64-bit arithmetic for the total.

Examples

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

Expected Output:

Explanation: Base score = 3 + 4 + 6 = 13. Improvements are 2, 4, and 0. Take the best two: 4 + 2, giving 19.

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

Expected Output:

Explanation: No boosts are allowed, so the answer is just `min(7,10) + min(1,0) = 7`.

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

Expected Output:

Explanation: Without boosting, contribution is 3. After doubling `b[0]`, contribution becomes `min(4, 6) = 4`.

Input: ([0, 10, 2, 9], [0, 3, 2, 5], 3)

Expected Output:

Explanation: Base score is 10. Only indices 1 and 3 improve, by 3 and 4 respectively, so the best total is 17.

Hints

For each index, compute how much the score improves if you double `b[i]`.
The choice at one index does not affect any other index, so you only need the largest `k` improvements.

Part 2: Count Triplets With a Divisible Sum

You are given an integer array `nums` and a positive integer `d`. Return the number of index triplets `(i, j, k)` such that: - `0 <= i < j < k < len(nums)` - `(nums[i] + nums[j] + nums[k]) % d == 0` The answer can be large, so use 64-bit arithmetic.

Constraints

`3 <= len(nums) <= 200000`
`1 <= d <= 200000`
`-10^9 <= nums[i] <= 10^9`
Use 64-bit arithmetic for the count.

Examples

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

Expected Output:

Explanation: The valid triplets are formed by indices (0,1,2), (0,2,4), (1,2,3), and (2,3,4).

Input: ([10, -7, 5], 1)

Expected Output:

Explanation: Every integer is divisible by 1, so the only triplet is valid.

Input: ([3, 6, 9, 12], 3)

Expected Output:

Explanation: All numbers are congruent to 0 mod 3, so every choice of 3 indices works. There are C(4,3) = 4.

Input: ([-1, 2, 4, 7], 4)

Expected Output:

Explanation: Only the triplet `(-1, 2, 7)` has sum 8, which is divisible by 4.

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

Expected Output:

Explanation: The only triplet has sum 3, which is not divisible by 5.

Hints

Only the remainders modulo `d` matter. Count how many numbers fall into each remainder class.
You can count ordered triples by using convolution on the remainder frequencies, then correct for repeated indices and divide by 6.

Part 3: Find the Longest Selectable Non-Decreasing Subarray

You are given two integer arrays `A` and `B` of equal length `n`. For a contiguous subarray `[l, r]`, you must choose exactly one value at each index `i`: either `A[i]` or `B[i]`. The chosen values must form a non-decreasing sequence. Return the maximum possible length of such a contiguous subarray.

Constraints

`1 <= len(A) == len(B) <= 200000`
`-10^9 <= A[i], B[i] <= 10^9`

Examples

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

Expected Output:

Explanation: Choose `[1, 2, 3, 4]`, which is non-decreasing across the whole array.

Input: ([5], [1])

Expected Output:

Explanation: A single element always forms a valid non-decreasing subarray.

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

Expected Output:

Explanation: Every value at index 0 is greater than every value at index 1, so no length-2 subarray works.

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

Expected Output:

Explanation: Choose `[-5, -2, 3, 6]`.

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

Expected Output:

Explanation: The best contiguous segment is indices `[1, 2]`, where you can choose `[1, 4]` or `[2, 3]`.

Hints

At each index, keep two DP values: the best length ending here if you choose `A[i]`, and if you choose `B[i]`.
Because the subarray must be contiguous, transitions only depend on index `i - 1`.

Quick Overview