Katkat
Back

Choose 200 of a Million Records to Label, Improving on Uniform Random Sampling

CitadelSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenStatistics & Math

Last updated

Tests the ability to define data informativeness under extreme budget constraints (selecting 200 out of 1,000,000 records) and design a scalable, one-shot sampling strategy that outperforms uniform random sampling in coverage and diversity.

Problem Statement

You are given an unlabeled dataset of N = 1,000,000 tabular records, where each record is represented by a d-dimensional feature vector (d is approximately 20 to 50, containing normalized continuous and ordinal signals from market events). You have a human annotation budget to label exactly k = 200 records.

The selection must be done in a single batch (one-shot): you cannot inspect labels iteratively as in standard sequential active learning.

While uniform random sampling is an unbiased baseline, drawing 200 points from 1,000,000 records leaves vast regions of the feature space completely unobserved and heavily over-samples dense, repetitive clusters of normal market activity.

Your task is to:

  1. Define Objective Criteria: Formalize what makes a sample "useful" or informative in the absence of labels (e.g., geometric coverage, density awareness, outlier suppression).
  2. Design an Algorithm: Propose a computationally tractable algorithm to select the 200 samples that optimize your criteria over the full 1,000,000 records.
  3. Address Scale: Standard pairwise distance matrices require O(N^2) memory and time, which is infeasible for N = 1,000,000. Detail how your approach runs efficiently within reasonable memory (< 8 GB) and time (< 5 minutes).

Assumptions & Constraints

  • The feature space is real-valued: X in R^(N x d), with N = 1,000,000 and d = 30.
  • Features are standardized (e.g., zero mean, unit variance), but the underlying distribution is non-Gaussian, multi-modal, and contains extreme outliers / noise.
  • The downstream goal is training a supervised classification model.
  • The annotation cost per record is fixed; exactly 200 indices must be returned.

Hints

Hint 1

Consider how to balance selecting high-density typical points versus boundary/rare points while avoiding selecting measurement noise and single-point outliers.

Hint 2

Exact k-medoids or greedy facility location requires O(N^2) distance calculations, so look into approximate clustering (like Mini-Batch K-Means with k-means++ initialization) or reservoir-based farthest-point sampling.

Hint 3

Selecting points purely by maximum distance often chooses pure noise or bad data; weighting diversity by local density helps ensure chosen points represent actual populations.

Follow-up questions

  • If certain features are known to have higher predictive value than others, how would you incorporate feature weighting or dimensionality reduction into your selection metric?
  • How does your algorithm defend against selecting corrupted data or telemetry artifacts that appear as isolated outliers in the feature space?
  • If the budget was split into two sequential batches of 100 rather than one batch of 200, how would your strategy adapt once the first 100 labels are revealed?