temkahap Aug 19 2018 at 22:40

Обзор задач по алгоритмам для собеседований — генерация множеств

7 min

61K

VK corporate blogPython*Algorithms*IT-emigrationIT career

From sandbox

+28

Comments 15

x893 Aug 19 2018 at 22:58

Зачем стремиться в Яндекс и пр. если можно купить коинов и через месяц их продать?
И пусть Яндекс живёт спокойно, занимаясь своей фигнёй.

-13

UFO just landed and posted this here

x893 Aug 19 2018 at 23:59

Там думать надо. А коины — тупо. Купил — продал. Разницу просрал.

-8

immaculate Aug 20 2018 at 04:25

Слово в слово как запомнившееся мне интервью эпохи расцвета МММ. Говорил какой-то парнишка: «Зачем работать, если можно вложиться в МММ? Пускай дураки работают».

Zuy Aug 20 2018 at 06:55

Интересно, а на какие позиции в гугл и яндекс такие задачи дают?

temkahap Aug 20 2018 at 11:58

В большинстве случаев на те, кто будет software заниматься — инфраструктура, БД, иногда могут и на другие позиции давать, например на ML-специалистов.
Однако есть одно но:
1) В чистом виде такие задачи встретятся далеко не факт (хотя разговаривал с чуваком, который в Яндекс собеседовался — попросили сгенерить все перестановки), в большинстве случаев будут несложные модификации таких задачек (например, сгенерить все перестановки строки).
2) Собес по алгоритмам — далеко не единственный собес, будет куча и других:)

ladutsko Aug 20 2018 at 14:11

В работе пригодится?

temkahap Aug 20 2018 at 14:11

Смотря где, хотя это холивар конечно.

v2kochetov Aug 20 2018 at 17:52

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

QtRoS Aug 29 2018 at 19:16

Я бы в этом случае задал имхо важный на собеседовании вопрос — "сами будете писать или эталон загуглите?" (это не призыв к холивару, это прагматичный подход).

g0rd1as Sep 9 2018 at 19:39

Я загуглю. Покурю, конечно, код немного, чтоб фигню не копипастить, подпилю под свои нужды и вперед! :)

DarkGenius Aug 20 2018 at 18:02

Как выводится оценка сложности рекурсивного алгоритма для задачи 1?

temkahap Aug 20 2018 at 18:08

Числа Каталана

Знаем, что количество последовательностей равно определенному числу Каталана. Чтобы сгенерировать одну последовательность, нужно один раз пройтись по списку.
Следовательно, сложность равна число Каталана * длину списка.

yarazny Feb 22 2021 at 19:22

А где следующий пост про динамику??

webhamster Nov 1 2023 at 22:24

Я никогда не понимал таких объяснений. Мне всегда кажется, что люди специально так объясняют, чтобы объяснение было, но никто ничего не понял.

Чтобы получить следующую лексикографическую последовательность, нужно найти самую правую открывающуюся скобку, перед которой стоит
закрывающаяся, чтобы при их перестановке местами скобочная
последовательность оставалась правильной.

До этого момента понятно.

Поменяем их местами и сделаем суффикс самым лексикографическим младшим

Что имеется в виду под суфиксом? Говоря по-русски, это что-то другое, нечто противоположное, чем префикс. Префикс - это по-нашенски приставка. Тогда что такое суффикс? То же самое что и в русском языке? Или имеется в виду окончание?

Если суффикс как русский суффикс, то имеется в виду какая-то последовательность в середине последовательности. Если суффикс как окончание, то имеется в виду какая-то последовательность на конце последовательности. Что же на самом деле имеется в виду?

Но даже если волшебным образом понять, какой вид суффикса имеется в виду, то почему-то не сказано, откуда этот суффикс начинается (и где заканчивается).

Далее, выражение "сделаем суффикс самым лексикографическим младшим" вообще непонятно. Как его "сделать"? Что должно с суффиксом произойти? По сравнению с чем он должен стать лексикографически младшим? Что с ним нужно сделать? Сделать внутренние перестановки? А какие? Поставить его впереди последовательности? Развернуть задом наперед? Может, что-то еще?

для этого нужно на каждом шаге вычислять разницу между количеством скобок.

И? Что нам даст это число? Как мы его будем использовать?