Стандартные задачи на собеседовании
Часто начинающие программисты получают задачи при приёме на работу. Предлагаем вашему вниманию сборник стандартных вопросов, задаваемых на собеседовании.
Я как человек, который часто ходил на собеседования на протяжении предыдущего года, чаще всего на позицию интерна в компании, занимающиеся разработкой ПО, хочу разделить все заданные мне вопросы на две категории: задачки "на подумать" и алгоритмические задачи.
Однако большинство собеседований, которые я проходил, не включали в себя вопросы первой категории. Практически все компании, в которые я шёл, были компаниями-гигантами, и большая часть вопросов приходилась на задачи на знание алгоритмов.
Задачки "на подумать".
- Вы играете в игру, где вы можете бросить кость 3 раза. Если вы вдруг решите выйти из игры, вы получите число монет, равное числу на кубике после последнего броска. Каково наиболее вероятное максимальное число монет, которое вы можете получить?
- Если вы бросите яйцо с этажа, номер которого больше N в стоэтажном здании, оно разобьётся. Вам нужно найти N, постепенно уменьшая число бросков, после которых яйцо разобьётся, учитывая то, что у вас всего два яйца.
- Сколько на Земле таких мест, отойдя от которых на одну милю в сторону юга, одну милю в сторону востока и одну милю в сторону запада, вы вернётесь туда, где начали?
- Допустим, у вас есть ряд цифр. Найдите сумму всех чисел с N числом цифр, каждая цифра которых принадлежит вашему ряду чисел.
Алгоритмические задачи.
- В матрице размерами N * M, состоящей из чисел от 1 до N * M, найдите путь из верхнего левого угла в правый нижний угол, двигаясь только вправо и вниз, так, чтобы сумма чисел на этом пути минимальна. Учитывайте то, что каждое число в матрице встречается лишь единожды.
- Дано число N типа float, найдите его квадратный корень.
- Имея монеты разного достоинства, найдите минимальное число монет, необходимых, чтобы составить сумму. Любая монета может встречаться любое количество раз.
- Есть строка S и ряд символов. Найдите наименьшую подстроку в строке S, которая содержит в себе данный ряд символов.
- У вас есть неотсортированный массив, в котором каждый элемент находится на дистанции в максимум K мест от своего правильного места в отсортированном массиве. Отсортируйте его.
- У вас есть бинарное дерево. Проверьте, является ли оно бинарным деревом поиска.
- Найдите число чёрных связанных элементов в чёрно-белой матрице. А что, если матрица трёхмерная?
- Допустим, у вас есть N отсортированных массивов, найдите K-ый наименьший элемент.
- У вас есть 4 строки, которые вы можете переставлять любым способом. Ваша задача - сделать максимально длинным наибольшую общий префикс после всех перестановок.
- Есть N точек на 2-мерной плоскости. У каждой точки есть цвет R, B, G. Ваша задача - найти треугольник наибольшей площади с данными точками, чтобы одна из сторон треугольника была параллельна к одной из осей и на каждой вершине точки были разного цвета.
- Найдите триплеты в данном массиве, сумма чисел в которых равна нулю.
- Строка a2b3c5 после разжатия становится строкой aabbbccccc. Сожмите данную вам строку S.
- Сделайте клон связного списка.
- Сделайте клон графа в форме списка смежности.
- Переверните связный список.
- У вас есть программа, написанная на Python. Найдите строку, в которой возникнет Indentation error.
- Допустим, у вас есть словарь и список строковых запросов. Для каждого запроса верните строку из словаря, которая анаграмма запросу.
- У нас есть список целых чисел. Найдите в нём медиану. Реализуйте функцию, которая добавляет новый элемент к этому списку, при этом считаю новую медиану.
Заключение
Хоть я и решил многие задачи, некоторые так и остались для меня нерешёнными, что не дало мне возможности попасть ни в одну заграничную команию.
Если вы зашли на эту статью, если вы интересуетесь подобными задачками, я полагаю, что ваша задача - подготовиться к подобному собеседованию. И несмотря на то что, казалось бы, я ответил на ваш вопрос, я хочу дать вам ещё дельный совет: заходите на сайты вроде glassdoor, geekforgeeks и решайте задачи, читайте бесчисленное количество блогов, разбросанных по Интернету, каждый из которых может помочь вам и дать бесценный опыт. Вы не выучите все возможные варианты задач, однако ваша главная цель - научиться решать их самостоятельно, а не вспоминать ответ судорожно на собеседовании.
В качестве дополнительного материала могу предложить вам InterviewBit.com. Информация на сайте структурирована, и вы почувствуете, что у вас есть собственный тренер.
Другие статьи по теме
Собеседование на должность программиста: вопросы по алгоритмам