How should I practice Decision Tree Classifier from Scratch?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Tiktok online assessment problems in FastPrep.

Is Decision Tree Classifier from Scratch associated with Tiktok?

FastPrep tags this as a Tiktok online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Decision Tree Classifier from Scratch

Learn this problem

● Hard

TiktokNEW GRADOA

See Tiktok hiring insights

Problem statement

Your task is to implement parts of the Decision Tree classification algorithm from scratch (i.e., without importing any libraries or packages). As a reminder, the Decision Tree building comprises four major steps:

Build tree nodes, where inner nodes contain feature index and value based on which the decision should be made, and leaf nodes contain a class label to predict.
Find the best split of samples for each tree node.
Calculate entropy to measure the purity of a split using the following formula.
E = -Σᵢ₌₁ᴺ pᵢ · log₂ pᵢ, where pᵢ = Nᵢ/N
where Nᵢ is the number of occurrences of a specific class label in the labeled data, and N is the number of samples.
Calculate the Information Gain of a split using the following formula.
IG = E_parent - (l/n · E_left + r/n · E_right)
where l is the number of samples in the left child, r is the number of samples in the right child, and n = l + r is the total number of samples.

To predict class labels of unlabeled samples, one needs to traverse the tree according to the information in the nodes and assign the leaf node label.

To validate the algorithm implementation, you will need to use it for some classification tasks. Specifically, you will be given a two-dimensional array of float values x_train as training data, where each sub-array x_train[i] represents a unique case, with one-dimensional array y_train where each element represents the true class label of corresponding sub-array in x_train[i].

FastPrep execution adapter

The source image is cropped before the rest of the callable contract and does not show deterministic split or tie rules. FastPrep considers each non-maximum observed feature value as a threshold, sends values less than or equal to it left, chooses equal-gain splits by smaller feature index and then smaller threshold, stops on non-positive gain, and resolves a tied leaf majority with the smaller label. These are grading-adapter rules, not source-image wording.

Function

decisionTreePredictions(xTrain: double[][], yTrain: int[], xTest: double[][]) → int[]

Examples

Example 1

xTrain = [[0], [1], [2], [3]]yTrain = [0, 0, 1, 1]xTest = [[0.5], [2.5]]return = [0, 1]

FastPrep-authored runnable example (not shown in the source image): Splitting feature 0 at threshold 1 creates two pure children. The first test sample goes left and the second goes right.

Constraints

FastPrep execution-adapter constraints (not shown in the source image):
1 <= xTrain.length == yTrain.length <= 120.
Each sample has between 1 and 8 features.
Every training and test row has the same number of features.
All feature values are finite and every class label is an integer.