Сообщение Re[7]: Задачки с Amazon SDE Interview от 16.12.2020 13:45
Изменено 16.12.2020 13:48 MaximVK
Re[7]: Задачки с Amazon SDE Interview
Здравствуйте, Буравчик, Вы писали:
Б>В файле может единственная очень длинная последовательность.
Это вырожденный случай. Тогда и про quicksort можно сказать, что сложность будет N^2.
Честно говоря, я думаю, что в оригинальной задаче было ограничение на длину одной строки.
Иначе задача в принципе не имеет решения, так как строка может просто не влезть в память.
Б>Думаю, что собеседующий предложил рассмотреть константный К только как промежуточный этап решения полной задачи.
Да, судя по всему так оно и есть. Но если мы решаем задачу для K, то потом можно решить для K+1,
сузив поиск для подпоследовательностей содержащих подпоследовательности найденные для K.
MVK>>Так как в качестве входного параметра мы имеем количество последовательностей
Б>Что такое "количество последовательностей"? Приведи свои расчеты
"количество последовательностей" == количество строк
Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Б>В файле может единственная очень длинная последовательность.
Это вырожденный случай. Тогда и про quicksort можно сказать, что сложность будет N^2.
Честно говоря, я думаю, что в оригинальной задаче было ограничение на длину одной строки.
Иначе задача в принципе не имеет решения, так как строка может просто не влезть в память.
Б>Думаю, что собеседующий предложил рассмотреть константный К только как промежуточный этап решения полной задачи.
Да, судя по всему так оно и есть. Но если мы решаем задачу для K, то потом можно решить для K+1,
сузив поиск для подпоследовательностей содержащих подпоследовательности найденные для K.
MVK>>Так как в качестве входного параметра мы имеем количество последовательностей
Б>Что такое "количество последовательностей"? Приведи свои расчеты
"количество последовательностей" == количество строк
Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Re[7]: Задачки с Amazon SDE Interview
Здравствуйте, Буравчик, Вы писали:
Б>В файле может единственная очень длинная последовательность.
Это вырожденный случай. Тогда и про quicksort можно сказать, что сложность будет N^2.
Честно говоря, я думаю, что в оригинальной задаче было ограничение на длину одной строки.
Иначе задача в принципе не имеет решения, так как строка может просто не влезть в память.
Спросил у топикстартера.
Б>Думаю, что собеседующий предложил рассмотреть константный К только как промежуточный этап решения полной задачи.
Да, судя по всему так оно и есть. Но если мы решаем задачу для K, то потом можно решить для K+1,
сузив поиск для подпоследовательностей содержащих подпоследовательности найденные для K.
MVK>>Так как в качестве входного параметра мы имеем количество последовательностей
Б>Что такое "количество последовательностей"? Приведи свои расчеты
"количество последовательностей" == количество строк
Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.
Б>В файле может единственная очень длинная последовательность.
Это вырожденный случай. Тогда и про quicksort можно сказать, что сложность будет N^2.
Честно говоря, я думаю, что в оригинальной задаче было ограничение на длину одной строки.
Иначе задача в принципе не имеет решения, так как строка может просто не влезть в память.
Спросил у топикстартера.
Б>Думаю, что собеседующий предложил рассмотреть константный К только как промежуточный этап решения полной задачи.
Да, судя по всему так оно и есть. Но если мы решаем задачу для K, то потом можно решить для K+1,
сузив поиск для подпоследовательностей содержащих подпоследовательности найденные для K.
MVK>>Так как в качестве входного параметра мы имеем количество последовательностей
Б>Что такое "количество последовательностей"? Приведи свои расчеты
"количество последовательностей" == количество строк
Я исхожу из того, что длинна строки (== последовательности) ограничена и влазит в нашу константную память.
В этом случае предложенное решение будет N^2, где N количество строк, так как обработка одной строки в этом случае становится константой.