Сегодня завалил (скорее всего) первое своё интервью в AWS.
Было четыре раунда по часу, первые два достаточно простые, потом началась жесть.

Кому интересно, предлагаю подумать над следующими задачками. Я сам пока решений не знаю (решения простым перебором, понятно, не рассматриваются):

1. Дан список строк S[1..N], нужно вернуть список R всех возможных списков таких, что:
R[i][j] ∈ S
string.Join("", R[i]) ∈ S
R[i].Count >= 2

Пример:
вход [a, b, ab, cd, abcd, fgh, f, g, h]
выход [[a, b], [a, b, cd], [ab, cd], [f, g, h]]

Я предлагал решение в виде построения дерева где листья являются подстроками корневого узла, потом через dynamic programming для каждого узла найти все возможные комбинации листьев, которые при конкатенации совпадут со значением узла. Не уложился во время, интервьюер в итоге сказал, что так решить можно, но есть решение проще через dynamic programming без построения дерева.

2. Дан список последовательностей чисел
Найти самую часто встречающуюся непрерывную подпоследовательность и сколько раз она встречается.
Облегчённый вариант, с которым я также не справился: длина подпоследовательности задана, рассматривать только подпоследовательности этой длины.
Очевидное решение с Dictionary, где ключом является сама подпоследовательность не подходит по требуемой памяти, даже в "облегчённом" варианте. Предполагается, что список читается из файла и в память не влезет.

Пример:
вход [[1, 2, 3, 4], [4, 2, 3, 1]]
выход [2, 3], 2

вход [[1, 2, 3, 4], [4, 2, 3, 2, 3]]
выход [2, 3], 3