Coding interview

[assassello]

Есть у кого любимые задачки, которые вы спрашиваете на интервью? Мне нужно что-то относительно несложное, минут на 10 подумать и минут за 15 закодировать. Но и чтобы не совсем тривиальное, не сортировка пузырьком.

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

Вопрос желательно из области general programming или algorithms. Язык неважен.

[ion tichy]

Надо лететь из города A в город Z с N пересадками. В наличии пачка N+1 билетов на перелет. Пачка билетов упала, рассыпалась и перетасовалась. Отсортировать поднятые с пола билеты в порядке пересадок.

[assassello]

Надо лететь из города A в город Z с N пересадками. В наличии пачка N+1 билетов на перелет. Пачка билетов упала, рассыпалась и перетасовалась. Отсортировать поднятые с пола билеты в порядке пересадок.

Неплохо. 👍

[assassello]

Или все таки слишком простая?..
Засунули в хэш-мап все билеты с ключом "откуда", потом достали из хэш-мапа по ключу "куда" - вот и отсортировали. O(N).

[Bobeg]

Или все таки слишком простая?..
Засунули в хэш-мап все билеты с ключом "откуда", потом достали из хэш-мапа по ключу "куда" - вот и отсортировали. O(N).

это принципиально не может работать.
и вообще у hash map только один ключ.

qsort тут ответ. и лучше ответа тут нет даже теоретически.

[kolbasof]

Или все таки слишком простая?..
Засунули в хэш-мап все билеты с ключом "откуда", потом достали из хэш-мапа по ключу "куда" - вот и отсортировали. O(N).

это принципиально не может работать.
и вообще у hash map только один ключ.

qsort тут ответ. и лучше ответа тут нет даже теоретически.

Вах! Это задачка из семейства задачек на ассоциативные массивы или adjacency matrix, когда для каждого элемента вычисляется натуральное число которое потом является индексом этого массива. Засада в том что соответствие должно быть one-to-one и натуральное число может быть большим и значит массив тоже большим. Но в данном случае А -> 0, B -> 1, ... Z -> 26. Решение в два прохода: один раз размещаем билеты в массиве по значению "откуда", во второй проход пробегаем по графу от значения А, которое есть первый элемент в массиве, т.е. временная сложность О(N), а вот пространственная может быть большой. Засада с закольцованностью. Но тогда задача не корректна и надо дополнительное измерение например время вылета и получается adjacency cube. Ну и так далее. Мне похожую задачку дали лет 6 назад причем у доски. Справился, потому что знал подход, а вот слету да в стрессе нелегко мозги повернуть.

[Kommi]

Если А->0 то Z->25

[mikeG]

Если нужно восстановить изначальную последовательность, то это в общем случае не решается, та как их может быть несколько. А найти какую-нибудь последовательность из A в Z - это обычный поиск пути в графе.
N городов, E билетов. O(N+E)

[Bobeg]

Если нужно восстановить изначальную последовательность, то это в общем случае не решается, та как их может быть несколько. А найти какую-нибудь последовательность из A в Z - это обычный поиск пути в графе.
N городов, E билетов. O(N+E)

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

действовать надо так.
сортинг будет по городу отправления и времени.
надо так же задефайнать точку отправления: СТАРТ = город+время

Код: Выделить всё

на входе: эррей с билетами, СТАРТ
на выходе: резалт_лист

заложить все билеты в сортед эррей если памяти мало. сорт ордер: город + время
если памяти много заложить в хешмап. хеш ки - город + время

найти СТАРТ. добавить его в резалт_лист.

если СТАРТ найти не удалось, то облом: экзит виз мизерабл феильюр, инвалид старт

КАРРЕНТ = СТАРТ

ПОВТОРЯТЬ КАК ДЯТЕЛЬ:
    искать НЕКСТ по (КАРРЕНТ->дестинейшен | KARRENT->эрравал)
    если НЕКСТ нифига не найден:
           если длина(резалт_лист) == длина(билет_мап) то экзит - саксесс, вернуть резалт_лист
           иначе: облом (экзит - потеряный билет, ничо низзя сделать)
    добавить НЕКСТ в резалт_лист
    КАРРЕНТ = НЕКСТ
КОНЕЦ ЦИКЛА

[Bobeg]

слабость алгоритма: ассьюмает что прилет и вылет происходят в один и тот же день.
а это ниобязательно так. на самом деле все шо мы знаем это то што вылет должен быть
опосля прилета. при чем при поиске вылетов из этого города опосля прилета может быть много.
но тогда надо использовать ближайший.

сие потребует ревижена алгоритма, но не архистрашного.
понадобица операция типа: найди ближайший вылет после этой дейт из этого города.
то есть мы вместо == для дейт матчинга будем использовать >=

[mikeG]

Если есть время вылета, то достаточно по нему и отсортировать. Но в условии нет времени.

[Bobeg]

на билетах время вылета и проджектед время прилета есть всегда, я никогда не видел билетов без времени и дейта.
но приравнивать эти времена низзя. потому што время прилета < времени вылета, и может быть в разных сутках.
при чем может они хочут в каком-то городе пробыть Н дней. мы низнаем. предполагать что разница между 0 и 1 невалидно тож.

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

[assassello]

Давайте исходить из предположения, что задача имеет физический смысл и изначальный маршрут построен без самопересечений (в том числе и не кольцевой). Тогда он весь восстанавливается за O(N) операций с использованием дополнительной O(N) памяти.
Весь трюк в том, чтобы сообразить, что сортировка тут не нужна.

В принципе нормальная задача, но есть что-нибудь еще? Мне надо до пятницы подобрать. Вечером полезу на ЛитКод, если ничего не найдется. Мне бы еще и в идеале, чтобы все программировалось без использования фичей языка и библиотек (типа stl), на чем-нибудь совершенно базовом типа стандартного Си.

[Uzito]

Хорошая задача про билеты, показывает что иногда имеет смысл дать на нее взглянуть стороннему человеку и получить его перспективу. Сортировать по дате и времени вылета вместо того, чтобы мудрить с пунктами назначения, это неочевидное и очень простое решение.
Давать такие задачи домой не нужно, их нужно обсуждать с кандидатом чтобы видеть его ход мысли.

[assassello]

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

Только в условии нет и не будет даты и времени. Только пункты вылета и прилета.
Если кандидат начнет втирать, что в реальном билете всегда есть дата, то пойдет сразу на выход. :)

[Uzito]

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

Только в условии нет и не будет даты и времени. Только пункты вылета и прилета.
Если кандидат начнет втирать, что в реальном билете всегда есть дата, то пойдет сразу на выход. :)

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

Это как пресловутая задача кандидату "нарисуй мне на бумажке дом". Если кандидат сразу бросается рисовать, то это совершенно негодный кандидат, который не потрудился получить более точного описания задачи. Может нужен дом для слепого жирафа, а он для людей дом рисует.

[Bobeg]

в теории хеш канешно лутше.
в практике все зависит от хешинга и филл фактора.

если работать с тупо несортированым массивом:

паскоку время лукапа каждой следующей остановки будет равно в среднем N/2 или О(N)
а лукапать придется N раз.
поэтому с неотсортированым массивом это будет иметь потипу квадратичный комплексити N^2

в случае сортированого массива или бинарного дерева будет иметь комплексити N*Log2(N) + N*Log2(N)
(Потому что надо отсортировать а потом прогнать алгоритм)

в случае хеша будет иметь комплексити N + N

[Bobeg]

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

Только в условии нет и не будет даты и времени. Только пункты вылета и прилета.
Если кандидат начнет втирать, что в реальном билете всегда есть дата, то пойдет сразу на выход. :)

разумееца пойдет ты ж не хочеш нанять кандидатов которые умнее тебя.

[assassello]

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

Это не наш случай.

Это как пресловутая задача кандидату "нарисуй мне на бумажке дом". Если кандидат сразу бросается рисовать, то это совершенно негодный кандидат, который не потрудился получить более точного описания задачи. Может нужен дом для слепого жирафа, а он для людей дом рисует.

Я даю кодинг вопрос в стиле ЛитКода: сначала текстовая формулировка, там могут фигурировать и билеты, и дома, и машины, и все что угодно, но в конце все сводится к "дана вот такая структура данных, нужно получить вот такой результат". Изменения условий не предусматривается.

[assassello]

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

Только в условии нет и не будет даты и времени. Только пункты вылета и прилета.
Если кандидат начнет втирать, что в реальном билете всегда есть дата, то пойдет сразу на выход. :)

разумееца пойдет ты ж не хочеш нанять кандидатов которые умнее тебя.

Какой-то ты нервный. Выдыхай, бобер! бобег! :)