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 hard 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 Two Algorithm Challenges | Visa Coding Question

Quick Overview

These two problems evaluate algorithmic skills in array optimization and graph pathfinding: the first focuses on selecting three ordered, non-overlapping variable-length subarrays to maximize the total sum with lexicographic tie-breaking, and the second targets shortest-path computation and optional path reconstruction in a directed weighted graph.

Solve Two Algorithm Challenges

Company: Visa

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

Solve the following independent algorithm problems. ### Problem 1: Maximize three non-overlapping variable-length subarrays You are given an integer array `nums` of length `n` and three positive integers `k1`, `k2`, and `k3`. Choose three non-overlapping contiguous subarrays in this order: - the first subarray has length `k1`, - the second subarray has length `k2`, - the third subarray has length `k3`. Return the starting indices `[i, j, l]` that maximize the total sum: `sum(nums[i : i + k1]) + sum(nums[j : j + k2]) + sum(nums[l : l + k3])` The indices must satisfy: `0 <= i`, `i + k1 <= j`, `j + k2 <= l`, and `l + k3 <= n`. If multiple answers have the same maximum total sum, return the lexicographically smallest list of starting indices. If no valid selection exists, return an empty list. ### Problem 2: Shortest path in a directed weighted graph You are given a directed graph with `n` nodes labeled from `0` to `n - 1`. Each edge is represented as `(u, v, w)`, meaning there is a directed edge from node `u` to node `v` with non-negative weight `w`. Given a `source` node and a `target` node, return the minimum total weight of any path from `source` to `target`. If the target is unreachable, return `-1`. Optionally, also return the actual shortest path.

Quick Answer: These two problems evaluate algorithmic skills in array optimization and graph pathfinding: the first focuses on selecting three ordered, non-overlapping variable-length subarrays to maximize the total sum with lexicographic tie-breaking, and the second targets shortest-path computation and optional path reconstruction in a directed weighted graph.

Part 1: Maximize Three Non-Overlapping Subarrays

Given an integer array nums and three positive integers k1, k2, and k3, choose three non-overlapping contiguous subarrays in this order: first length k1, then length k2, then length k3. Return the starting indices [i, j, l] that maximize the total sum of those three subarrays. The subarrays may touch but must not overlap. If multiple answers have the same maximum total, return the lexicographically smallest index list. If no valid selection exists, return an empty list.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
1 <= k1, k2, k3 <= 200000
A valid answer must satisfy i + k1 <= j, j + k2 <= l, and l + k3 <= len(nums)

Examples

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

Expected Output: [0, 3, 5]

Explanation: The best three length-2 subarrays start at 0, 3, and 5 with sums 3, 8, and 12.

Input: ([4, 5, 10, 6, 11, 17, 4, 5, 2], 1, 2, 3)

Expected Output: [0, 1, 3]

Explanation: The maximum total is achieved by subarrays starting at 0, 1, and 3, giving 4 + 15 + 34 = 53.

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

Expected Output: []

Explanation: The array is too short to fit three non-overlapping subarrays.

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

Expected Output: [0, 1, 2]

Explanation: Many choices have the same total sum, so the lexicographically smallest valid answer is returned.

Hints

Precompute the sum of every window of size k1, k2, and k3 using a sliding window or prefix sums.
For each possible middle subarray start j, quickly find the best first subarray on the left and the best third subarray on the right. Be careful to keep the smallest indices when sums tie.

Part 2: Shortest Path in a Directed Weighted Graph

You are given a directed graph with n nodes labeled from 0 to n - 1. Each edge is represented as (u, v, w), meaning there is a directed edge from u to v with non-negative weight w. Given a source node and a target node, return the minimum total weight of any path from source to target. If the target is unreachable, return -1.

Constraints

1 <= n <= 200000
0 <= len(edges) <= 300000
0 <= u, v < n
0 <= w <= 10^9
0 <= source, target < n

Examples

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

Expected Output: 7

Explanation: One shortest path is 0 -> 1 -> 3 -> 4 with total cost 2 + 2 + 3 = 7.

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

Expected Output: -1

Explanation: Node 3 cannot be reached from node 0.

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

Expected Output: 0

Explanation: The shortest path from a node to itself has cost 0.

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

Expected Output: 5

Explanation: The best route uses the cheaper parallel edge 0 -> 1 with weight 3, then 1 -> 2 -> 3 for a total of 5.

Hints

Since all edge weights are non-negative, think about the classic shortest-path algorithm that uses a priority queue.
Store the best known distance to each node, and when you pop a node with a larger stale distance, skip it.

Quick Overview