FastPrep
Problem · Dynamic Programming

Get Largest Index Length

Learn this problem
● MediumAmazonOA
See Amazon hiring insights

Problem statement

Some data analysts at Amazon are analyzing the outliers in data that contains two co-related features. The features are represented as two arrays of n integers each, feature1, and feature2. A data set is considered free of outliers if for any two indices i and j where 0 ≤ i < j < n if feature1[i] > feature1[j], then feature2[i] > feature2[j] or if feature1[i] < feature1[j], then feature2[i] < feature2[j]. Note that if feature1[i] = feature1[j], then the data set is not considered to be free of outliers. Given the arrays, feature1 and feature2, find the length of the largest array of indices i1, i2, i3 ... ik such that data formed by these indices i.e. {feature1[i1], feature1[i2],...feature1[ik]} and {feature2[i1], feature2[i2],...feature2[ik]} is free of outliers.

Function

getLargestIndexLen(feature1: int[], feature2: int[]) → int

Complete the function getLargestIndexLen in the editor.

getLargestIndexLen takes the following arguments:

  1. 1. int feature1[n]: the values of the first feature
  2. 2. int feature2[n]: the values of the second feature

Examples

Example 1

feature1 = [4, 5, 3, 1, 2]feature2 = [2, 1, 3, 4, 5]return = 2

It is optimal to choose the indices [3, 4]. The data for feature1 is [1, 2] and for feature2 is [4, 5]. Here feature1[0] < feature1[1] and feature2[0] < feature2[1], therefore the condition holds true. Since it is not possible to select a larger subset without violating the conditions, the answer is 2 i.e. the size of the chosen subset.

More Amazon problems

drafts saved locally
public int getLargestIndexLen(int[] feature1, int[] feature2) {
  // write your code here
}
feature1[4, 5, 3, 1, 2]
feature2[2, 1, 3, 4, 5]
expected2
checking account