Virtu·Data Scientist·Online Assessment (OA)·Intermediate

Intermediate

Jul 2026

Summary

Got a coding problem at Virtu for a Data Scientist role that was more competitive programming than anything data science related. One question, pretty involved, and I left unsure if my approach was even close to optimal.

Questions Asked (1)

You have n cards, each with a cost and a multiplier. Starting from some initial point value, you can buy any subset of cards in any order, as long as you can afford each card when you buy it. Buying a card subtracts its cost then multiplies your remaining points by its multiplier. Find the order and subset of cards that maximizes your final points.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was greedy, sort by multiplier descending and buy whatever you can afford.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and constraints, then propose a dynamic programming or greedy approach with sorting by some criterion. Discuss trade-offs between optimality and complexity, and consider edge cases like negative multipliers or zero costs.

Pro tip: Mention that this is similar to scheduling with precedence constraints or the 'buy low, sell high' problem, and that sorting by cost/(multiplier-1) might be optimal under certain conditions. Always validate with brute force on small n.

1. Clarify the problem

Ask about constraints: n size, range of costs, multipliers, initial points, and whether multipliers can be less than 1 or negative. Confirm if you can skip cards and if order matters.

2. Identify the objective and constraints

We want to maximize final points = (initial - sum costs of bought cards in order) * product of multipliers, but affordability constraint means at each step remaining points >= cost of next card.

3. Propose an algorithmic approach

Consider dynamic programming over subsets (if n small) or greedy with sorting. For greedy, sort cards by some ratio (e.g., cost/(multiplier-1)) and buy if affordable. Discuss why greedy may not always be optimal.

4. Analyze complexity and trade-offs

Compare DP O(2^n) vs greedy O(n log n). Discuss when greedy works (e.g., all multipliers >1) and when DP is needed. Mention potential for branch and bound or integer programming.

5. Test with examples and edge cases

Walk through a small example, e.g., initial=10, cards: (cost=5, mult=2), (cost=3, mult=3). Show order matters. Discuss edge cases: multipliers <1, zero cost, negative multipliers.

Key Points to Mention

Affordability constraint: you must have enough points before each purchase.
Order matters: buying a multiplier card earlier amplifies later points.
Greedy sorting by cost/(multiplier-1) is optimal if all multipliers >1 and no affordability issues, but not generally.
Dynamic programming over subsets works for small n, but exponential.
Potential reduction to knapsack or scheduling with precedence.
Edge cases: multipliers <1, zero cost, negative multipliers, initial points too low.

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