Amazon | SDE Intern 6m OA | Minimum Variance

Round 1

Questions: Within the Amazon Real Estate Analytics Toolset, an investor is evaluating a series of buildings of varying heights. The investor aims to find a group of buildings that adhere to two key conditions:

1. The selected buildings must form a valid group.
   • A group of buildings is considered valid if it meets the following criteria:
     • It is a contiguous subsegment of the original array with a size of at least 2.
     • The heights of the first and last buildings in this subsegment are the same.
2. The group variance should be as minimal as possible.

The investor's goal is to find such a valid group of buildings with the minimal possible variance in height among the buildings in the group. The variance of a group is the difference between the size of the group and the occurrences of the first element height in the group. For example, the variance of the group (4, 2, 5, 4) is 4 - 2 = 2.

Formally, given an array height of size n, the height of each building, find the minimum possible variance of a valid group of buildings. It is guaranteed that there is at least one valid group. An array a is a subsegment of an array b if a can be obtained from b by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. For example, [3, 1], and [4] is a subsegment of array [1, 3, 1, 4] while [1, 1], and [1, 4] is not.