Amazon SDE intern OA Question 1

Round 1

Questions: In an Amazon content analysis project, there is a dataset of strings, each representing distinct attributes. The goal is to determine the dominance of the most influential attribute prefix for various lengths.

The dominance of a prefix, denoted as t, is measured by the number of instances in the dataset where t serves as a prefix. For example, in the dataset ["abab","ababc","abab"], the dominance of the prefix "ab" is 3, and the dominance of the prefix "aba" is 3.

The most influential prefix of a specific length len is identified as the prefix with the highest dominance among all strings of the same length. If there are multiple prefixes of the same length with equivalent dominance, any prefix from that set may be considered the most influential.

Formally, given the dataset 𝓧 consisting of n strings, each of length m, the objective is to determine, for each prefix of length len ranging from 1 to m, the dominance of the most influential prefix of that length.

Example Input:

n = 3
s = ["abab", "ababc", "abab"]

For the given dataset:

• The prefix "a" has a dominance of 3.
• The prefix "ab" has a dominance of 3.
• The prefix "aba" has a dominance of 3.

For each length from 1 to m, find the dominance of the most influential prefix.