Candidate Dominance Count - Count Points Not Dominated by Any Other

Question

## Round 1 - Coding

## Problem

Given a set of candidates, each represented as a point in N-dimensional space, a candidate A *dominates* candidate B if A is strictly better than B in every dimension. Return the count of candidates that are not dominated by any other candidate (the Pareto front).

```python
def count_non_dominated(candidates: list[list[int]]) -> int:
    # candidates[i] = list of scores in each dimension (higher is better)
    # A dominates B if A[d] > B[d] for ALL dimensions d
    # Return count of candidates not dominated by any other
    ...
```

```
Example:
candidates = [
    [3, 1],   # C0
    [1, 3],   # C1
    [2, 2],   # C2
    [1, 1],   # C3
]
# C0 dominates C3 (3>1 and 1>1? No - tie on dim 1)
# Strictly: C2 dominates C3 (2>1 and 2>1)
# C0, C1, C2 are non-dominated
count_non_dominated(candidates) -> 3
```

## Follow-ups

1. What is your time complexity for 2D vs N-dimensional inputs?
2. In 2D, can you solve this in O(n log n)? Describe the approach.
3. How would you return the actual non-dominated set, not just the count?
4. How does the definition change if "better" means lower score (minimization)?

Candidate Dominance Count - Count Points Not Dominated by Any Other

Question Details

Full Details

Topics

More from Pinterest