Я предлагал решение в виде построения дерева где листья являются подстроками корневого узла, потом через dynamic programming для каждого узла найти все возможные комбинации листьев, которые при конкатенации совпадут со значением узла. Не уложился во время, интервьюер в итоге сказал, что так решить можно, но есть решение проще через dynamic programming без построения дерева.
2. Дан список последовательностей чисел
Найти самую часто встречающуюся непрерывную подпоследовательность и сколько раз она встречается.
Облегчённый вариант, с которым я также не справился: длина подпоследовательности задана, рассматривать только подпоследовательности этой длины.
Очевидное решение с Dictionary, где ключом является сама подпоследовательность не подходит по требуемой памяти, даже в "облегчённом" варианте. Предполагается, что список читается из файла и в память не влезет.
Здравствуйте, Chriso, Вы писали:
C>1. Дан список строк S[1..N], нужно вернуть список R всех возможных списков таких, что: C>R[i][j] ∈ S C>string.Join("", R[i]) ∈ S C>R[i].Count >= 2
C>Пример: C>вход [a, b, ab, cd, abcd, fgh, f, g, h] C>выход [[a, b], [a, b, cd], [ab, cd], [f, g, h]]
Извиняюсь за эзотерическую julia, но я сейчас на ней пытаюсь мыслить:
julia> s = ["a", "b", "ab", "cd", "abcd", "fgh", "f", "g", "h"]
9-element Array{String,1}:
"a"
"b"
"ab"
"cd"
⋮
"f"
"g"
"h"
julia> pairs = map(outer->outer=>filter(inner->inner != outer && occursin(inner, outer), s), s) |> x->filter(e->!isempty(last(e)),x)
3-element Array{Pair{String,Array{String,1}},1}:
"ab" => ["a", "b"]
"abcd" => ["a", "b", "ab", "cd"]
"fgh" => ["f", "g", "h"]
julia> function sbreak(outer::String, inner::Vector{String})::Vector{Vector{String}}
function sbreak2(outer::String, inner::Vector{String})::Vector{Vector{String}}
#println(outer, inner)if isempty(outer)
[[""]]
else
vcat([
let new_outer = outer[length(e)+1:end]; new_inner = filter(e2->e != e2, inner); new_sbreak = sbreak2(new_outer, new_inner)
map(x->[e;x], new_sbreak)
end
for e in inner if startswith(outer, e)
]...)
end
end
[e[1:end-1] for e in sbreak2(outer, inner)]
end
julia> sbreak("abcd",["a", "b", "ab", "cd"])
2-element Array{Array{String,1},1}:
["a", "b", "cd"]
["ab", "cd"]
julia> vcat(map(p->sbreak(first(p), last(p)), pairs)...)
4-element Array{Array{String,1},1}:
["a", "b"]
["a", "b", "cd"]
["ab", "cd"]
["f", "g", "h"]
C>2. Дан список последовательностей чисел C>Найти самую часто встречающуюся непрерывную подпоследовательность и сколько раз она встречается. C>Облегчённый вариант, с которым я также не справился: длина подпоследовательности задана, рассматривать только подпоследовательности этой длины. C>Очевидное решение с Dictionary, где ключом является сама подпоследовательность не подходит по требуемой памяти, даже в "облегчённом" варианте. Предполагается, что список читается из файла и в память не влезет.
C>Пример: C>вход [[1, 2, 3, 4], [4, 2, 3, 1]] C>выход [2, 3], 2
C>вход [[1, 2, 3, 4], [4, 2, 3, 2, 3]] C>выход [2, 3], 3
Если длина задача, то для каждой последовательности считаете вхождения пос-ти данной длины. Пусть длина 2, сначала 12, пргоняете по всем последовательном и считаете, потом 23, потом 34,42,23(возможно уже быда), 31 . По памяти О(1).
Вообще на ютубе полно видео разбора задач с интервью Амазонка, гугла и т.д.
Здравствуйте, Chriso, Вы писали:
C>Сегодня завалил (скорее всего) первое своё интервью в AWS. C>Было четыре раунда по часу, первые два достаточно простые, потом началась жесть.
C>Кому интересно, предлагаю подумать над следующими задачками. Я сам пока решений не знаю (решения простым перебором, понятно, не рассматриваются):
Ну так к интервью на кодинг надо готовиться. leetcode, hackerrank всякие... На ютубе тоже полно, целые каналы
Вторая задача вторая возможно на структуры данных (trie вместо dictionary с числом повторений в узлах не подойдет?)
Здравствуйте, Chriso, Вы писали:
C>Пример: C>вход [a, b, ab, cd, abcd, fgh, f, g, h] C>выход [[a, b], [a, b, cd], [ab, cd], [f, g, h]]
C>Я предлагал решение в виде построения дерева где листья являются подстроками корневого узла, потом через dynamic programming для каждого узла найти все возможные комбинации листьев, которые при конкатенации совпадут со значением узла. Не уложился во время, интервьюер в итоге сказал, что так решить можно, но есть решение проще через dynamic programming без построения дерева.
Для решения нам нужно найти такие строки, которые можно составить из других подстрок (из двух и более).
При этом, для составлении можем использовать подстроки несколько раз (это упрощает задачу).
Решение с помощью динамического программирования — запоминаются все разбиения хвостов слов на подстроки.
from functools import lru_cache
from typing import List
def find_solve(strings: List[str]) -> List[List[str]]:
@lru_cache
def split_word(word: str) -> List[List[str]]:
"""Находит все варианты разбиения слова word на подстроки из strings"""
result = []
for subword in strings:
if not word.startswith(subword):
continue
if word == subword:
result.append([subword])
continue
new_word = word[len(subword):]
for rest_combination in split_word(word=new_word):
result.append([subword, *rest_combination])
return result
result = []
for word in strings:
for combination in split_word(word):
if len(combination) >= 2:
result.append(combination)
return result
Сложность тоже интересно посчитать (не получилось сразу, не буду выкладывать)
Здравствуйте, Chriso, Вы писали:
C>2. Дан список последовательностей чисел C>Найти самую часто встречающуюся непрерывную подпоследовательность и сколько раз она встречается. C>Облегчённый вариант, с которым я также не справился: длина подпоследовательности задана, рассматривать только подпоследовательности этой длины. C>Очевидное решение с Dictionary, где ключом является сама подпоследовательность не подходит по требуемой памяти, даже в "облегчённом" варианте. Предполагается, что список читается из файла и в память не влезет.
C>Пример: C>вход [[1, 2, 3, 4], [4, 2, 3, 1]] C>выход [2, 3], 2
C>вход [[1, 2, 3, 4], [4, 2, 3, 2, 3]] C>выход [2, 3], 3
Думаю, так:
Надо объединить все входящие последовательности в одну большую, заменяя промежутки между последовательностями специальным символом ($).
Теперь у нас стоит задача поиска наиболее часто повторяющейся подстроки в строке.
Для этого нужно построить суффиксное дерево (что само по себе не просто).
При построении дерева нужно для каждого узла запоминать количество его вхождений в строку.
Потом найти в дереве наиболее глубокий узел по количеству символов, считая от корня. Это и будет ответ.
P.S. Да уж, задачи — жесть. В условиях малого времени сделать сложно
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Chriso, Вы писали:
Б>Думаю, так:
Б>Надо объединить все входящие последовательности в одну большую, заменяя промежутки между последовательностями специальным символом ($). Б>Теперь у нас стоит задача поиска наиболее часто повторяющейся подстроки в строке.
Б>Для этого нужно построить суффиксное дерево (что само по себе не просто).
Так вроде ограничения по памяти O(1). Или дерево влезть? Мне казалось, что при заданной длине подпоследовательности простейшим перебором можно все решить.
Здравствуйте, Sharov, Вы писали:
S>Так вроде ограничения по памяти O(1). Или дерево влезть? Мне казалось, что при заданной длине подпоследовательности простейшим перебором можно все решить.
Дерево требует O(N) памяти, где N — количество символов.
За O(1) по памяти — сомневаюсь, что можно так решить.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Sharov, Вы писали:
S>>Так вроде ограничения по памяти O(1). Или дерево влезть? Мне казалось, что при заданной длине подпоследовательности простейшим перебором можно все решить.
Б>Дерево требует O(N) памяти, где N — количество символов.
Б>За O(1) по памяти — сомневаюсь, что можно так решить.
Постановки была с идеей, что списки читаются из файла (типа парсятся логи).
O(N) по памяти точно не подходит, но вероятно предполагалось, что можно сделать несколько проходов.
Здравствуйте, Sharov, Вы писали:
S>Если длина задача, то для каждой последовательности считаете вхождения пос-ти данной длины. Пусть длина 2, сначала 12, пргоняете по всем последовательном и считаете, потом 23, потом 34,42,23(возможно уже быда), 31 . По памяти О(1).
Как-то уж слишком брутфорсно получается, но ничего лучше я не могу тоже придумать.
Возможно, если задать отношение порядка для подпоследовательностей и искать вхождения подпоследовательностей от меньшей к большей, то можно избежать повторений.
Тогда будет выглядеть так:
За первый проход ищем минимальную подпоследовательность.
На следующих проходах считаем две величины: количество вхождений заданной подпоследовательности и следующую по порядку подпоследовательнось.
Но в пределе все равно квадрат, а для среднего что-то не могу вероятности сходу посчитать.
Здравствуйте, Sharov, Вы писали:
S>Если длина задача, то для каждой последовательности считаете вхождения пос-ти данной длины. Пусть длина 2, сначала 12, пргоняете по всем последовательном и считаете, потом 23, потом 34,42,23(возможно уже быда), 31 . По памяти О(1).
По памяти О(1), но по времени как минимум O(N^3) или даже O(N^4).
Кубическая сложность это очень долго даже на маленьких файлах, которые точно влезли бы в память (например, 1 млн байт). Не говоря уже про чтение с диска.
Здравствуйте, Буравчик, Вы писали:
Б>По памяти О(1), но по времени как минимум O(N^3) или даже O(N^4). Б>Кубическая сложность это очень долго даже на маленьких файлах, которые точно влезли бы в память (например, 1 млн байт). Не говоря уже про чтение с диска.
Откуда у тебя там куб и тем более четвертая степень наросла?
Здравствуйте, MaximVK, Вы писали:
MVK>Откуда у тебя там куб и тем более четвертая степень наросла?
Всего элементов — N. Длина рассматриваемой последовательности K (в нашем примере 2).
1. Выбор оригинальной последовательности — (N-K) вариантов
2. Поиск дубликата для это оригинальной последовательности — (N-K) вариантов
3. Сравнение двух последовательностей — K действий
СУММА (по K от 1 до N) K*(N-K)*(N-K)
Получится что-то от N^3 до N^4.
Б>Всего элементов — N. Длина рассматриваемой последовательности K (в нашем примере 2).
Б>1. Выбор оригинальной последовательности — (N-K) вариантов Б>2. Поиск дубликата для это оригинальной последовательности — (N-K) вариантов Б>3. Сравнение двух последовательностей — K действий
Б>СУММА (по K от 1 до N) K*(N-K)*(N-K) Б>Получится что-то от N^3 до N^4.
Хм, но если скобки раскроем, то получится N^2
Но вообще, в данном случае у тебя N — это количество символов в одной последовательности.
Количество символов в последовательности — это не то, что мы увеличиваем в этой задаче. Условно, я бы считал это за константу.
Так как в качестве входного параметра мы имеем количество последовательностей, то я бы отвечал на вопрос: "Как увеличится количество операций, при увеличении количества строк(последовательностей) в файле, при условии, что макс длинна последовательности остаётся неизменной".
В этом случае твои 1,2,3 можно ограничить константой сверху рассчитанной для максимальной последовательности.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, MaximVK, Вы писали:
MVK>>Откуда у тебя там куб и тем более четвертая степень наросла?
Б>Всего элементов — N. Длина рассматриваемой последовательности K (в нашем примере 2).
Б>1. Выбор оригинальной последовательности — (N-K) вариантов Б>2. Поиск дубликата для это оригинальной последовательности — (N-K) вариантов Б>3. Сравнение двух последовательностей — K действий
Б>СУММА (по K от 1 до N) K*(N-K)*(N-K) Б>Получится что-то от N^3 до N^4.
Б>ДОБАВЛЕНО: Б>https://www.wolframalpha.com/input/?i=lim+%28SUM+k*%28n-k%29*%28n-k%29%2C+k%3D1+to+n%29+as+n+-%3E+infinity
Здравствуйте, MaximVK, Вы писали:
MVK>Хм, но если скобки раскроем, то получится N^2
Для K близких к N/2, получим N^3.
А когда просуммируем по всем К получим N^4
MVK>Но вообще, в данном случае у тебя N — это количество символов в одной последовательности.
N-количество символов во всем файле.
В файле может единственная очень длинная последовательность.
MVK>Количество символов в последовательности — это не то, что мы увеличиваем в этой задаче. Условно, я бы считал это за константу.
К — длина искомой последовательность. Я говорю про исходную задачу, когда K неизвестен.
Думаю, что собеседующий предложил рассмотреть константный К только как промежуточный этап решения полной задачи.
MVK>Так как в качестве входного параметра мы имеем количество последовательностей
Что такое "количество последовательностей"? Приведи свои расчеты
Здравствуйте, Буравчик, Вы писали:
Б>Думаю, так:
Б>Надо объединить все входящие последовательности в одну большую, заменяя промежутки между последовательностями специальным символом ($). Б>Теперь у нас стоит задача поиска наиболее часто повторяющейся подстроки в строке.
Б>Для этого нужно построить суффиксное дерево (что само по себе не просто). Б>При построении дерева нужно для каждого узла запоминать количество его вхождений в строку. Б>Потом найти в дереве наиболее глубокий узел по количеству символов, считая от корня. Это и будет ответ.
Б>P.S. Да уж, задачи — жесть. В условиях малого времени сделать сложно
Можно так сделать:
Начинаем с подпоследовательности длинной n=2:
1. Cтроим суффиксное дерево для подпоследовательность длинной n
2. Выбираем те подпоследовательности у которых макс. число вхождений
3. Ищем последовательности длинной n+1 которые содержат подпоследовательности выбранные на шаге 2, т.е. вида ?abc и abc?
4. Повторяем пока максимальное количество вхождений не начнет уменьшаться
В этом случае мы ограничим рост дерева, вот только сложность я не могу пока посчитать. Вечером подумаю.
Б>В файле может единственная очень длинная последовательность.
Это вырожденный случай. Тогда и про quicksort можно сказать, что сложность будет N^2.
Честно говоря, я думаю, что в оригинальной задаче было ограничение на длину одной строки.
Иначе задача в принципе не имеет решения, так как строка может просто не влезть в память.
Спросил у топикстартера.
Б>Думаю, что собеседующий предложил рассмотреть константный К только как промежуточный этап решения полной задачи.
Да, судя по всему так оно и есть. Но если мы решаем задачу для K, то потом можно решить для K+1,
сузив поиск для подпоследовательностей содержащих подпоследовательности найденные для K.
MVK>>Так как в качестве входного параметра мы имеем количество последовательностей Б>Что такое "количество последовательностей"? Приведи свои расчеты
"количество последовательностей" == количество строк
Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Здравствуйте, Chriso, Вы писали:
C>2. Дан список последовательностей чисел C>Найти самую часто встречающуюся непрерывную подпоследовательность и сколько раз она встречается. C>Облегчённый вариант, с которым я также не справился: длина подпоследовательности задана, рассматривать только подпоследовательности этой длины. C>Очевидное решение с Dictionary, где ключом является сама подпоследовательность не подходит по требуемой памяти, даже в "облегчённом" варианте. Предполагается, что список читается из файла и в память не влезет.
Уточняющий вопрос по этой задаче.
А длинна одной последовательности ограничена?
