Один, который меня попросили решить в заключительном раунде собеседования по кодированию в ведущей компании, специализирующейся на продуктах.
Я учусь на бакалавриате по специальности Компьютерные науки в NITK, Surathkal. Во время кампании по размещению в кампусе в начале 2019 года мне удалось устроиться на летнюю стажировку в Flipkart, индийском гиганте электронной коммерции.
Мне пришлось пройти 4 раунда собеседований по решению проблем, и четвертый раунд довольно запоминающийся - короткий 20-минутный раунд, где я столкнулся с проблемой на основе связанного списка, которую я нашел довольно сложной и интересно.
Давай прогуляемся по переулку памяти.
Сейчас около 22:00. Интервью начались в 18 часов вечера. Трое из нас прошли первые два раунда.
Один был выбран сразу, и мы остались вдвоем - ждем, усталые, истощенные и слабо улыбающиеся друг другу.
В третьем раунде другой кандидат ушел, и мне сказали подождать, поэтому я сидел и яростно барабанил пальцами по ручке стула, фантазируя, как это будет, когда меня выберут.
HR, называющий меня по имени, выводит меня из задумчивости. Меня жестом проводят в комнату, и мой интервьюер встает, чтобы поприветствовать меня.
Интервьюер: « Довольно долгий день, а? Ты должно быть устал."
Я: « Да, сэр. Я очень устал, но еще и загорелся перед собеседованием ».
Я, наверное, этого не говорил, но давайте вернемся.
Интервьюер: Давай поскорее с этим покончим. Давайте рассмотрим только одну проблему и попробуем найти эффективное решение.
Услышав только одну проблему, часть меня почувствовала облегчение, а часть стала очень тревожной.
Интервьюер: берет ручку и бумагу, что-то нацарапывает и приступает к объяснению мне постановки проблемы.
Проблема
Существует множество заголовков связанных списков, которые могут пересекаться, а могут и не пересекаться друг с другом. Цель состоит в том, чтобы сгруппировать записи массива таким образом, чтобы, если два связанных списка пересекались друг с другом, они принадлежали к одной группе.
Когда я посмотрел на проблему и набросал пример, проблема стала для меня понятной. Если кто-то не понял проблему, вот пример, чтобы проиллюстрировать проблему.
Пример. Вот массив размером 8, каждая запись которого содержит указатель на заголовок связанного списка.
И мы видим, что 0,1 и 2 пересекаются друг с другом и, следовательно, образуют группу. Поскольку 3 и 7 не пересекаются с другими списками, они находятся в отдельных группах. 4, 5 и 6 пересекаются друг с другом и, следовательно, образуют другую группу.
А теперь вернемся к разговору
Интервьюер: Надеюсь, проблема ясна.
Я: Да, за исключением некоторых сомнений.
Я продолжаю спрашивать и проясняю свои сомнения.
На первый взгляд проблема кажется чрезвычайно сложной.
Мой разум забегает, когда я пытаюсь атаковать проблему со всех сторон в надежде найти способ ее решить.
Я начинаю с того, что называю указатели связанного списка некоторыми алфавитами.
А затем перечислите каждый список отдельно.
Мой мозг работал на полную мощность, пока я сохранял самообладание и разговаривал с интервьюером. За первые десять минут произошло следующее:
While True: Me: *Comes up with a new approach to the problem* Me: *Explains the approach to the interviewer* Interviewer: *Shakes his head in disapproval and drops hints* Me: *Goes back to brainstorming and thinking out loud*
Когда я яростно скрежетал зубами и смотрел на бумагу, мои глаза расширились от волнения, когда я кое-что заметил. Было такое ощущение, будто меня ударила молния!
Последние указатели всех пересекающихся связанных списков должны быть одинаковыми!
Я: * высказывает свое наблюдение *
Интервьюер: * смотрит на газету, тонко улыбается и просит меня написать псевдокод. *
После этого наблюдения формулировка алгоритма и написание псевдокода было куском пирога.
Алгоритм
- Инициализировать пустую хеш-карту. Эта хэш-карта будет использоваться для хранения пар ключ: значение указателей: индекс.
- Инициализируйте набор массивов, в каждом из которых хранится каждая группа. Назовите это arrg.
- Для каждого индекса массива просмотрите связанный список в этом индексе до конца и попробуйте добавить указатель хвоста в хэш-карту.
- Если указатель уже присутствует в хэш-карте, добавьте текущий индекс в соответствующий набор.
- В противном случае добавьте указатель на хэш-карту и добавьте индекс в новый массив в arrg.
- Количество массивов в arrg соответствует количеству групп, и каждый массив символизирует группу.
Код Python
Интервьюер: Выглядит правильно и довольно эффективно. Какая будет временная сложность?
Я: если размер самого длинного связанного списка равен M, а размер массива равен N, то это O (MN).
Затем мы перешли к разговору о компании, его положении в компании, балансе между работой и личной жизнью, роде работы и т. Д.
Результат: выбран.
Спасибо за чтение
Уровень кодирования
Спасибо, что стали частью нашего сообщества! Подпишитесь на наш канал YouTube или присоединитесь к Интервью по программированию Skilled.dev.
