FastPrep
Problem · String

Get Maximum Information Gain

Learn this problem
● EasyAmazonNEW GRADOA
See Amazon hiring insights

Problem statement

Data analysts at Amazon are analyzing a data set of n strings in the array dataSet[], each consisting of lowercase English letters. Each character in a string corresponds to a particular feature.

The information gain obtained by training a model with two strings, dataSet[i] and dataSet[j], is the difference between the lengths of the strings i.e., |len(dataSet[i]) - len(dataSet[j])|. To avoid too many overlapping features, two strings can be selected only if the number of common features between them does not exceed a given threshold, max_common_features. The number of common features here is equal to the number of common characters between the two strings. For example, "abc" and "bcd" have 2 common features 'b' and 'c'. While "aa" and "aaa" have two common features, the "a" two 'a' characters.

Given dataSet and max_common_features, determine the maximum information gain possible.

Function

getMaxInformationGain(dataSet: String[], max_common_features: int) → int

Complete the function getMaxInformationGain in the editor.

getMaxInformationGain takes the following arguments:

  1. String[] dataSet: the strings of features
  2. int max_common_features: the maximum number of common features allowed between data points

Returns

int: the maximum possible information gain

𓇼 ⋆.˚ 𓆝 𓆡⋆.˚ 𓇼Forever thankful chizzy_elect 🍀

Examples

Example 1

dataSet = ["abofh", "ab", "mo"]max_common_features = 1return = 3
It is optimal to choose the strings "abofh" and "mo". Their number of common features is 1 ('o') and the information gain is |5 - 2| = 3.

Example 2

dataSet = ["a", "bcdef"]max_common_features = 1return = 4
The two strings can be chosen. They do not share any common features and their difference in length is 4.

Constraints

  • 2 ≤ n ≤ 1000
  • 1 ≤ len(dataSet[i]) ≤ 1000
  • 1 ≤ max_common_features ≤ 1000

More Amazon problems

drafts saved locally
public int getMaxInformationGain(String[] dataSet, int max_common_features) {
  // write your code here
}
dataSet["abofh", "ab", "mo"]
max_common_features1
expected3
checking account