Problem
Naive Bayes assumes features are independent given the class and picks the class with the highest score:
score(c) = P(c) × P(x₁ | c) × P(x₂ | c) × … × P(xₙ | c)
Features are categories encoded as integers. Estimate the probabilities from the training data:
- P(c) = (number of samples of class c) / (number of samples)
- P(xⱼ = v | c) = (count of samples of class c whose feature j equals v + 1) / (number of samples of class c + Kⱼ)
where Kⱼ is the number of distinct values of feature j among the training samples and the query. The +1 (Laplace smoothing) keeps an unseen value from making a score 0.
Return the class with the highest score; if scores tie, return the smaller class. Multiplying many small probabilities can underflow, so add logarithms instead.
Implement naive_bayes_predict(features, labels, query).
Input
features: One row of n categorical features per training sample.
labels: The class of each training sample.
query: The n features of the sample to classify.
Output
Return the predicted class.
Constraints
1 ≤ samples ≤ 1,000, 1 ≤ n ≤ 20
0 ≤ each feature value and label ≤ 100
Examples
Input:
query = [0, 1]
labels = [1, 1, 0, 0, 1]
features = [
[0, 1],
[0, 0],
[1, 1],
[1, 0],
[0, 1]
]
Expected output:
expected = 1Input:
std::vector<long long> query = {0, 1};
std::vector<long long> labels = {1, 1, 0, 0, 1};
std::vector<std::vector<long long>> features = {
{0, 1},
{0, 0},
{1, 1},
{1, 0},
{0, 1}
};
Expected output:
long long expected = 1;Input:
long[] query = new long[] {0, 1};
long[] labels = new long[] {1, 1, 0, 0, 1};
long[][] features = new long[][] {
new long[] {0, 1},
new long[] {0, 0},
new long[] {1, 1},
new long[] {1, 0},
new long[] {0, 1}
};
Expected output:
long expected = 1;Explanation
Class 1 has 3 samples and class 0 has 2. Feature 1 has values {0, 1} (K = 2), feature 2 has {0, 1} (K = 2). score(1) = 3/5 × (3+1)/(3+2) × (2+1)/(3+2) = 0.6 × 0.8 × 0.6 = 0.288. score(0) = 2/5 × (0+1)/(2+2) × (1+1)/(2+2) = 0.4 × 0.25 × 0.5 = 0.05. Class 1 wins.
Input:
query = [2]
labels = [0, 0, 1]
features = [
[0],
[0],
[1]
]
Expected output:
expected = 0Input:
std::vector<long long> query = {2};
std::vector<long long> labels = {0, 0, 1};
std::vector<std::vector<long long>> features = {
{0},
{0},
{1}
};
Expected output:
long long expected = 0;Input:
long[] query = new long[] {2};
long[] labels = new long[] {0, 0, 1};
long[][] features = new long[][] {
new long[] {0},
new long[] {0},
new long[] {1}
};
Expected output:
long expected = 0;Explanation
Value 2 never appears, so K = 3 (values 0, 1 and 2). score(0) = 2/3 × (0+1)/(2+3) ≈ 0.133 and score(1) = 1/3 × (0+1)/(1+3) ≈ 0.083. Thanks to smoothing neither is 0, and the more common class 0 wins.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Score each class by combining its prior with feature likelihoods under the independence assumption.
Hint 2
Use frequency counts with Laplace smoothing, and compare classes in log space to avoid tiny products.
Hint 3
Include the query values when determining each feature’s distinct value count, and break ties by choosing the smaller class.
Expected complexity
O(m × n) time, O(m × n) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.