Сообщение Re[9]: Задачки с Amazon SDE Interview от 16.12.2020 15:19
Изменено 16.12.2020 15:20 MaximVK
Re[9]: Задачки с Amazon SDE Interview
Здравствуйте, Буравчик, Вы писали:
Б>Как мы запомним подпоследовательности из предыдущего К? Ведь память должна быть O(1)
В этом случае надо будет несколько проходов.
Ты можешь отсортировать подпоследовательности и запихать столько в память, сколько влезет. Это позволит уменьшить кол-во чтений файла.
MVK>>Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
MVK>>В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Б>Что-то я запутался.
Б>Пусть P — длина строки, N — количество строк. Превратить длину строки P в константу мы всегда сможем, а сейчас предлагаю ее учитывать.
Б>Как работает алгоритм и какова его сложность?
Сходу только в брутфорсном варианте когда мы для для каждой подстроки считаем количество вхождений скандируя весь файл (считаем, что поиск подстроки стоит нам O(P)):
для i = 2..P (i = длинна подпоследовательности)
N * (N-1) * (P-i) * P
получаем
O(N^2*P^3)
В умном варианте надо подумать, сходу не скажу. Постараюсь вечером прикинуть.
Б>Как мы запомним подпоследовательности из предыдущего К? Ведь память должна быть O(1)
В этом случае надо будет несколько проходов.
Ты можешь отсортировать подпоследовательности и запихать столько в память, сколько влезет. Это позволит уменьшить кол-во чтений файла.
MVK>>Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
MVK>>В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Б>Что-то я запутался.
Б>Пусть P — длина строки, N — количество строк. Превратить длину строки P в константу мы всегда сможем, а сейчас предлагаю ее учитывать.
Б>Как работает алгоритм и какова его сложность?
Сходу только в брутфорсном варианте когда мы для для каждой подстроки считаем количество вхождений скандируя весь файл (считаем, что поиск подстроки стоит нам O(P)):
для i = 2..P (i = длинна подпоследовательности)
N * (N-1) * (P-i) * P
получаем
O(N^2*P^3)
В умном варианте надо подумать, сходу не скажу. Постараюсь вечером прикинуть.
Re[9]: Задачки с Amazon SDE Interview
Здравствуйте, Буравчик, Вы писали:
Б>Как мы запомним подпоследовательности из предыдущего К? Ведь память должна быть O(1)
В этом случае надо будет несколько проходов.
Ты можешь отсортировать подпоследовательности и запихать столько в память, сколько влезет. Это позволит уменьшить кол-во чтений файла.
MVK>>Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
MVK>>В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Б>Что-то я запутался.
Б>Пусть P — длина строки, N — количество строк. Превратить длину строки P в константу мы всегда сможем, а сейчас предлагаю ее учитывать.
Б>Как работает алгоритм и какова его сложность?
Сходу только в брутфорсном варианте когда мы для для каждой подстроки считаем количество вхождений скандируя весь файл (считаем, что поиск подстроки стоит нам O(P)):
для i in 2..P (i = длинна подпоследовательности)
N * (N-1) * (P-i) * P
получаем
O(N^2*P^3)
В умном варианте надо подумать, сходу не скажу. Постараюсь вечером прикинуть.
Б>Как мы запомним подпоследовательности из предыдущего К? Ведь память должна быть O(1)
В этом случае надо будет несколько проходов.
Ты можешь отсортировать подпоследовательности и запихать столько в память, сколько влезет. Это позволит уменьшить кол-во чтений файла.
MVK>>Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
MVK>>В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Б>Что-то я запутался.
Б>Пусть P — длина строки, N — количество строк. Превратить длину строки P в константу мы всегда сможем, а сейчас предлагаю ее учитывать.
Б>Как работает алгоритм и какова его сложность?
Сходу только в брутфорсном варианте когда мы для для каждой подстроки считаем количество вхождений скандируя весь файл (считаем, что поиск подстроки стоит нам O(P)):
для i in 2..P (i = длинна подпоследовательности)
N * (N-1) * (P-i) * P
получаем
O(N^2*P^3)
В умном варианте надо подумать, сходу не скажу. Постараюсь вечером прикинуть.