← Visa Interview Insights

Visa·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Visa coding round for a Software Engineer role. One problem, LeetCode Hard territory, and I left feeling pretty beaten up about it.

Questions Asked (1)

Q1

Given a list of people where each person has up to two skills (skill 1 and skill 2) and an associated cost, return an array of minimum costs where the K-th element represents the minimum cost to select people such that at least K of them have both skills. Use -1 if it's not possible. Solve for all K from 1 to N.

Algorithms & Data Structures
Author's notes

Felt defeated walking out.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the problem: we need to select a subset of people to maximize the number of people with both skills for each possible K, while minimizing total cost. This is a bicriteria optimization problem that can be solved by dynamic programming over the number of people with both skills, considering the costs of different types of people (those with both skills, those with only skill 1, those with only skill 2, and those with neither).

Pro tip: Start by categorizing people into four groups based on their skills, then sort each group by cost. Use dynamic programming where the state is the number of people with both skills, and transition by adding people from each group in increasing cost order.

1. Clarify the problem and constraints

Restate the problem to ensure understanding: we need to select a subset of people such that at least K have both skills, minimizing total cost, for all K from 1 to N. Ask about input size and constraints to determine the required efficiency.

2. Categorize people by skills

Divide people into four groups: those with both skills, only skill 1, only skill 2, and neither. Sort each group by cost in ascending order. This helps in efficiently considering the cheapest options first.

3. Define DP state and transitions

Let dp[i][j] be the minimum cost to achieve j people with both skills using the first i people (or after considering certain groups). Transition by either including or excluding a person, updating the count of people with both skills based on their skills.

4. Optimize with prefix sums and greedy selection

For each possible number of people with both skills from the 'both' group, use prefix sums to quickly compute the cost of taking the cheapest ones. Then, for the remaining required people with both skills, consider converting people from the single-skill groups by pairing them (one from skill1-only and one from skill2-only) to create a person with both skills.

5. Compute answers for all K and handle impossible cases

After filling the DP table, for each K from 1 to N, find the minimum cost to achieve at least K people with both skills. If no such selection exists, return -1. Ensure the solution is efficient, ideally O(N^2) or better.

Key Points to Mention

  • Categorization of people into four groups based on skills (both, only skill1, only skill2, neither) and sorting by cost.
  • Dynamic programming state definition: dp[i][j] = minimum cost to get j people with both skills using first i people.
  • Transition: when adding a person, if they have both skills, j increases by 1; if they have only one skill, they can be paired with someone with the complementary skill to increase j by 1.
  • Use of prefix sums to efficiently compute the cost of taking the cheapest people from each group.
  • Handling of impossible cases: if the maximum achievable number of people with both skills is less than K, return -1.
  • Time and space complexity analysis: aim for O(N^2) time and O(N) space if possible, or O(N^2) space if using 2D DP.

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