← Visa Interview Insights

Visa·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Visa SWE interview had at least one algorithmic problem that looked straightforward but needed a bit of greedy thinking to get right. Pretty standard coding round vibe.

Questions Asked (1)

Q1

You're given two arrays of equal length and an integer k. Each index contributes min(a[i], b[i]) to a running total. You can choose up to k indices to double the value of b[i], which changes that index's contribution to min(a[i], 2*b[i]). Return the maximum possible total sum.

Algorithms & Data Structures
Author's notes

My first instinct was to just double the k largest b values, which is wrong.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by computing the base sum of min(a[i], b[i]) for all indices. For each index, calculate the potential gain from doubling b[i] as min(a[i], 2*b[i]) - min(a[i], b[i]). Then, select up to k indices with the largest positive gains and add them to the base sum. This greedy approach works because the gains are independent and we want to maximize the total increase.

Pro tip: Emphasize that the greedy choice is optimal because the gains are independent and non-negative; sorting by gain ensures we pick the best k. Also, mention that you only consider indices where the gain is positive, as doubling b[i] might not always increase the contribution.

1. Understand the problem

Restate the problem: we have two arrays a and b of length n, and an integer k. The base sum is sum of min(a[i], b[i]). We can double b[i] for up to k indices, changing the contribution to min(a[i], 2*b[i]). We need to maximize the total sum.

2. Compute base sum and gains

Calculate the base sum by summing min(a[i], b[i]) for all i. For each index, compute the gain if we double b[i]: gain[i] = min(a[i], 2*b[i]) - min(a[i], b[i]).

3. Select best indices

Sort the gains in descending order. Take the top k gains that are positive (or all positive gains if fewer than k). Add the sum of these gains to the base sum.

4. Return the maximum sum

The maximum possible total sum is the base sum plus the sum of the selected gains. Return this value.

Key Points to Mention

  • Time complexity: O(n log n) due to sorting, which is efficient for large n.
  • Space complexity: O(n) to store gains, or O(1) if we sort in place or use a heap.
  • Greedy choice property: selecting the largest gains is optimal because gains are independent and non-negative.
  • Edge cases: k=0, k >= n, all gains negative or zero, large values causing integer overflow (use 64-bit integers).
  • Alternative approach: use a min-heap of size k to find top k gains in O(n log k) time, which is better if k is small.
  • Proof of correctness: exchange argument showing that any optimal solution can be transformed to include the top k gains without decreasing the sum.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.