Собеседование в Apple — непростая задача. В этой статье вы найдёте вопросы, которые чаще всего задают соискателям, и советы по прохождению собеседования.
Содержание:
Как проходит собеседование в Apple
Алгоритмы, которые нужно знать: поиск в глубину, поиск в ширину, бинарный поиск, быстрая сортировка, сортировка слиянием, динамическое программирование, парадигма «Разделяй и властвуй».
https://tproger.ru/experts/do-programmers-need-cv/
Решение
В этом коде мы сортируем массив. Затем фиксируем один элемент e и находим пару — (a, b), среди оставшихся элементов массива, такую что required_sum - e = a + b.
Мы начинаем с первого элемента массива — e, и пытаемся найти такую пару значений (a, b) в оставшемся массиве (например от A[i + 1] до A[n — 1]), которая удовлетворяет условию a+b = required_sum — e. Если мы её нашли, то выходим из цикла.
В противном случае мы повторяем описанные шаги для всех элементов с индексами от 1 до n — 3 до тех пор, пока не найдём соответствующую пару.
Вычислительная сложность: квадратичная, O(n²).
Эффективность алгоритма: константная, O(1).
Формулировка: Дан массив (список) пар интервалов, где каждый интервал это timestamp, отсортированный по первому значению. Объедините пересекающиеся интервалы и верните полученный массив.
В данном примере интервалы: (1, 5), (3, 7), (4, 6),( 6, 8) пересекаются и должны быть объединены в интервал (1, 8). Интервалы (10, 12) и (12, 15) должны быть объединены в (10, 15).
Решение
Эту задачу можно решить с помощью алгоритма linear scan.
Для каждого интервала из списка:
.
Эффективность: линейная, O.
Решение
Мы используем обход в глубину и создаем копию каждого узла в процессе обхода графа. В хэш-таблице сохраняем каждый скопированный узел, чтобы не скопировать его дважды. Ключ в хэш-таблице — это узел в оригинальном графе и его значение, соответствующее значению в скопированном графе.
Сложность: линейная, O.
Эффективность: логарифмическая, O, где n — это количество вершин графа.
https://tproger.ru/translations/linked-list-for-beginners/
Решение
Допустим, что мы хотим сложить 9901 и 237. В результате должно получиться 10138.
Для облегчения задачи числа хранятся в инвертированных связных списках. Самая значимая цифра числа это последний элемент списка. Мы начинаем сложение с голов списков.
На каждой итерации мы складываем текущие числа и добавляем результат в хвост итогового списка. Для каждого шага нужно учитывать переполнение.
Нам нужно сделать это для каждого узла обоих списков. Если один из них кончится раньше, мы продолжаем действия для оставшегося. Когда списки закончатся, и не будет чисел, которые переносятся, алгоритм заканчивается.
Сложность: линейная, O.
Эффективность: линейная, O.
Решение
Указатели на голову и хвост итогового списка сохраняются. Его голова будет результатом сравнения первых узлов объединяемых списков.
Для всех последующих узлов, выбираем наименьший текущий и добавляем его в хвост итогового списка. Затем сдвигаем текущий указатель этого списка на шаг в перед.
Если один из списков кончился, то оставшиеся элементы другого добавляются в хвост итогового списка. Изначально итоговый список — Null.
Сравниваем значения первых двух узлов и создаём узел с меньшим значением в голове итогового списка. В примере это 4 в head1. Пока в списке только один узел, то он будет также и хвостом. Затем сдвигаем голову head1 на один шаг вперёд.
Сложность: линейная, O(m+n), где m и n — это длины первоначальных списков.
Эффективность: константная, O(1).
Решение
Эта задача решается с помощью рекурсии. Рекурсия останавливается, если хотя бы один из сравниваемых узлов равен null.
Деревья A и B идентичны если:
Сложность: линейная, O.
Эффективность: O(h) для лучшего случая, или O(logn) для сбалансированного дерева, или O для худшего случая.
Решение
Мы используем обратный обход бинарного дерева. Меняем местами левого и правого потомка каждого узла. Используем обход в глубину — перед возвращением из узла все его потомки пройдены и отзеркалены.
Сложность: линейная, O.
Эффективность: линейная, в худшем случае O.
Решение
От каждой буквы из входной строки начинаем расширятся влево и вправо, проверяя на палиндромы подстроки чётной и нечетной длины. Затем, если палиндрома нет, переходим на следующую букву.
Сложность: квадратичная, O(n²).
Эффективность: константная, O(1).
Решение
Решение состоит из двух этапов: переворот строки и обход строки и переворот каждого слова.
Сложность: линейная, O.
Эффективность: константная, O(1).
Решение
Мы используем для решения алгоритм Кадане. Идея алгоритма в том, чтобы просканировать весь массив и для каждой позиции найти наибольшую сумму для отрезка массива, который кончается в этой позиции. Это достигается сохранением текущей максимальной суммы (current_max) для текущего индекса и global_max (максимальной для всего массива).
Код алгоритма:
Решение
Сложность: линейная, O.
Эффективность: константная, O(1).
Решение
Для наиболее эффективного решения этой задачи мы используем алгоритм «Разделяй и властвуй». На стадии разделения мы рекурсивно делим n на 2 пока не достигнем условия выхода.
На стадии объединения мы получаем результат подпроблемы r и вычисляем результат текущей проблемы, используя следующие правила:
Эффективность: логарифмическая, O(logn).
Вывод должен быть либо в форме массива массивов, либо списка списков, где каждый элемент это одна комбинация. Вот пример для числа 5:
1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 1, 1, 1, 1
Решение
Мы рекурсивно перебираем все возможные комбинации сумм и печатаем подходящую комбинацию.
Каждый вызов рекурсии содержит цикл, который работает от start до target (start изначально равен 1). current_sum это переменная, которая увеличивается с каждым вызовом рекурсии.
Каждый раз, когда значение добавляется в current_sum, оно также добавляется в список result. Когда current_m = target мы знаем, что список result содержит комбинацию, которая добавляется в финальный список output. Вот пример:
//Условие выхода из рекурсии:
if current_sum == target {
print(output)
}
Перед каждым рекурсивным вызовом в result добавляется элемент. После вызова этот элемент удаляется, для очистки списка.
Сложность: экспоненциальная, O².
Эффективность: линейная, O.
Вот массив до сдвига:
Вот массив поле сдвига на 6 позиций:
Решение
Для решения мы использовали немного модифицированный бинарный поиск. Отметим, что как минимум одна половина массива всегда отсортирована. Если число n находится в этой половине, тогда проблема решается бинарным поиском.
Сложность: логарифмическая, O(logn).
Эффективность: логарифмическая, O(logn).
Для примера возьмём кэш, в который помещаются 4 элемента. В нем находятся 4 элемента.
Теперь мы добавим туда элемент — 5.
Решение
Кэширование — это техника хранения данных в более быстром хранилище (обычно в оперативной памяти), для того чтобы иметь к ним быстрый доступ. Обычно кэш ограничен в объёме. Поэтому при заполнении кэша нужно удалять из него данные.
LRU — очень простой и популярный алгоритм для этого. Мы удаляем самые старые данные, чтобы освободить место для новых.
Чтобы реализовать LRU кэш, нам понадобятся две структуры данных: хэш-таблица и двусвязный список. Двусвязный список помогает поддерживать порядок удаления из кеша, а хэш-таблица используется для поиска кэшированных элементов.
Вот описание алгоритма:
Если элемент существует в хэш-таблице
передвинуть его в хвост связного списка
Иначе
если кэш заполнился
удалить головной элемент из списка и запись о нём в хэш-таблице
Добавить новый элемент в хвост списка и в таблицу.
Получить элемент из кэша и вернуть
Замечание: Элемент, находящийся в конце списка — последний использовавшийся. Новые элементы также добавляются в конец списка.
Сложность:
, где n — размер кэша.
Источник статьи: https://tproger.ru/translations/sobesedovanie-v-apple-top-30-voprosov-i-otvetov/
Содержание:
Как проходит собеседование в Apple
- Массивы и графы
- Связные списки
- Деревья
- Строки
- Динамическое программирование
- Математика, статистика и поиск с возвратом
- Поиск и проектирование
- Поведенческие вопросы
- Советы по прохождению собеседования
Как проходит собеседование в Apple
Взаимодействие с компанией обычно состоит из следующих шагов:- Предварительный разговор с рекрутером: в среднем ответ на резюме занимает около недели. Обычно с вами связываются по email или LinkedIn, чтобы договориться о телефонном звонке. Звонок длится от 15 минут до получаса. На этом этапе не будет серьёзных технических вопросов. Вас могут спросить о том, почему вы хотите работать в этой компании или какой ваш любимый продукт Apple.
- Техническое собеседование по телефону: обычно назначается через неделю. Таких собеседований может быть одно или два. В течение часа вам будут задавать вопросы о вашем резюме, алгоритмах и структурах данных. Из них полчаса будет отведено на выполнение заданий.
- Собеседование в офисе: такое собеседование длится примерно шесть часов. С вами пообщаются около десяти сотрудников компании. В процессе собеседования с вами обсудят ваши знания, зададут поведенческие вопросы и дадут задания с кодом. Каждое интервью длится около часа. Поведенческие вопросы особенно важны если вы собеседуетесь на роль менеджера.
Алгоритмы, которые нужно знать: поиск в глубину, поиск в ширину, бинарный поиск, быстрая сортировка, сортировка слиянием, динамическое программирование, парадигма «Разделяй и властвуй».
https://tproger.ru/experts/do-programmers-need-cv/
Массивы и графы
Поиск трёх чисел в массиве
Формулировка: Дан массив целых чисел и значение, определите, есть ли в этом массиве три числа, сумма которых равна этому значению.Решение
В этом коде мы сортируем массив. Затем фиксируем один элемент e и находим пару — (a, b), среди оставшихся элементов массива, такую что required_sum - e = a + b.
Мы начинаем с первого элемента массива — e, и пытаемся найти такую пару значений (a, b) в оставшемся массиве (например от A[i + 1] до A[n — 1]), которая удовлетворяет условию a+b = required_sum — e. Если мы её нашли, то выходим из цикла.
В противном случае мы повторяем описанные шаги для всех элементов с индексами от 1 до n — 3 до тех пор, пока не найдём соответствующую пару.
Вычислительная сложность: квадратичная, O(n²).
Эффективность алгоритма: константная, O(1).
Объединение пересекающихся интервалов
Цель этого задания — объединить все пересекающиеся интервалы в списке, чтобы получить список, в котором останутся только непересекающиеся интервалы.Формулировка: Дан массив (список) пар интервалов, где каждый интервал это timestamp, отсортированный по первому значению. Объедините пересекающиеся интервалы и верните полученный массив.
В данном примере интервалы: (1, 5), (3, 7), (4, 6),( 6, 8) пересекаются и должны быть объединены в интервал (1, 8). Интервалы (10, 12) и (12, 15) должны быть объединены в (10, 15).
Решение
Эту задачу можно решить с помощью алгоритма linear scan.
Для каждого интервала из списка:
- Если интервал из входного списка пересекается с последним интервалом из результирующего списка, то они объединяются, и результат заменяет последний интервал в результирующем списке.
- В противном случае, интервал из входного списка добавляется в итоговый список.
.Эффективность: линейная, O
.Клонировать ориентированный граф
Формулировка: Есть корневой узел ориентированного графа, нужно клонировать граф с помощью глубокого копирования. Клонированный граф должен иметь такие же ребра и узлы.
Решение
Мы используем обход в глубину и создаем копию каждого узла в процессе обхода графа. В хэш-таблице сохраняем каждый скопированный узел, чтобы не скопировать его дважды. Ключ в хэш-таблице — это узел в оригинальном графе и его значение, соответствующее значению в скопированном графе.
Сложность: линейная, O
.Эффективность: логарифмическая, O
, где n — это количество вершин графа.https://tproger.ru/translations/linked-list-for-beginners/
Связные списки
Сложение двух чисел
Формулировка: Даны указатели на головы двух связных списков, где каждый список это целое число (каждый узел это цифра). Сложите их и верните результат.
Решение
Допустим, что мы хотим сложить 9901 и 237. В результате должно получиться 10138.
Для облегчения задачи числа хранятся в инвертированных связных списках. Самая значимая цифра числа это последний элемент списка. Мы начинаем сложение с голов списков.
На каждой итерации мы складываем текущие числа и добавляем результат в хвост итогового списка. Для каждого шага нужно учитывать переполнение.
Нам нужно сделать это для каждого узла обоих списков. Если один из них кончится раньше, мы продолжаем действия для оставшегося. Когда списки закончатся, и не будет чисел, которые переносятся, алгоритм заканчивается.
Сложность: линейная, O
.Эффективность: линейная, O
.Слияние двух отсортированных связных списков
Формулировка: Даны два отсортированных связных списка, объедините их так, чтобы итоговый список остался отсортированным.Решение
Указатели на голову и хвост итогового списка сохраняются. Его голова будет результатом сравнения первых узлов объединяемых списков.
Для всех последующих узлов, выбираем наименьший текущий и добавляем его в хвост итогового списка. Затем сдвигаем текущий указатель этого списка на шаг в перед.
Если один из списков кончился, то оставшиеся элементы другого добавляются в хвост итогового списка. Изначально итоговый список — Null.
Сравниваем значения первых двух узлов и создаём узел с меньшим значением в голове итогового списка. В примере это 4 в head1. Пока в списке только один узел, то он будет также и хвостом. Затем сдвигаем голову head1 на один шаг вперёд.
Сложность: линейная, O(m+n), где m и n — это длины первоначальных списков.
Эффективность: константная, O(1).
Деревья
Проверить два бинарных дерева на идентичность
Формулировка: Даны два бинарных дерева. Нужно проверить их на идентичность, то есть у них должны быть одинаковые структуры и данные в каждом узле.
Решение
Эта задача решается с помощью рекурсии. Рекурсия останавливается, если хотя бы один из сравниваемых узлов равен null.
Деревья A и B идентичны если:
- Данные в корневых узлах этих деревьев идентичны или равны null.
- Левое поддерево A идентично левому поддереву B.
- Правое поддерево A идентично правому поддереву B.
Сложность: линейная, O
.Эффективность: O(h) для лучшего случая, или O(logn) для сбалансированного дерева, или O
для худшего случая.Отзеркаливание узлов бинарного дерева
Формулировка: Дано бинарное дерево. Нужно поменять местами левых и правых потомков каждого узла.Решение
Мы используем обратный обход бинарного дерева. Меняем местами левого и правого потомка каждого узла. Используем обход в глубину — перед возвращением из узла все его потомки пройдены и отзеркалены.
Сложность: линейная, O
.Эффективность: линейная, в худшем случае O
.Строки
Найти все палиндромы в строке
Формулировка: Дана строка, найдите все возможные подстроки палиндромы длиной больше одного символа. Строка — «aabbbaa».Решение
От каждой буквы из входной строки начинаем расширятся влево и вправо, проверяя на палиндромы подстроки чётной и нечетной длины. Затем, если палиндрома нет, переходим на следующую букву.
Сложность: квадратичная, O(n²).
Эффективность: константная, O(1).
Смена порядка слов в предложении
Формулировка: Обратите порядок слов в предложении (хранящемся в массиве символов). Строка — «Hello world!».Решение
Решение состоит из двух этапов: переворот строки и обход строки и переворот каждого слова.
Сложность: линейная, O
.Эффективность: константная, O(1).
Динамическое программирование
Поиск подотрезка массива с максимальной суммой элементов
Формулировка: Найдите подотрезок в массиве, используя динамическое программирование и алгоритм Кадане. В приведённом ниже массиве такой отрезок имеет индексы (3, 6).
Решение
Мы используем для решения алгоритм Кадане. Идея алгоритма в том, чтобы просканировать весь массив и для каждой позиции найти наибольшую сумму для отрезка массива, который кончается в этой позиции. Это достигается сохранением текущей максимальной суммы (current_max) для текущего индекса и global_max (максимальной для всего массива).
Код алгоритма:
Решение
Сложность: линейная, O
.Эффективность: константная, O(1).
Математика и статистика
Возведение числа в степень
Формулировка: Даны два числа, x (double) и y (integer), напишите функцию, которая возводит x в степень y.Решение
Для наиболее эффективного решения этой задачи мы используем алгоритм «Разделяй и властвуй». На стадии разделения мы рекурсивно делим n на 2 пока не достигнем условия выхода.
На стадии объединения мы получаем результат подпроблемы r и вычисляем результат текущей проблемы, используя следующие правила:
- Если n — чётное, результат — r * r (где r — это результат подпроблемы)
- Если n — нечётное, результат — x * r * r (где r — это результат подпроблемы)
Эффективность: логарифмическая, O(logn).
Найти комбинации чисел дающие указанную сумму
Формулировка: Дано положительное целое число target, выведите все возможные комбинации положительных целых чисел, сумма которых равна target.Вывод должен быть либо в форме массива массивов, либо списка списков, где каждый элемент это одна комбинация. Вот пример для числа 5:
1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 1, 1, 1, 1
Решение
Мы рекурсивно перебираем все возможные комбинации сумм и печатаем подходящую комбинацию.
Каждый вызов рекурсии содержит цикл, который работает от start до target (start изначально равен 1). current_sum это переменная, которая увеличивается с каждым вызовом рекурсии.
Каждый раз, когда значение добавляется в current_sum, оно также добавляется в список result. Когда current_m = target мы знаем, что список result содержит комбинацию, которая добавляется в финальный список output. Вот пример:
//Условие выхода из рекурсии:
if current_sum == target {
print(output)
}
Перед каждым рекурсивным вызовом в result добавляется элемент. После вызова этот элемент удаляется, для очистки списка.
Сложность: экспоненциальная, O².
Эффективность: линейная, O
.Поиск и проектирование
Поиск в циклически сдвинутом массиве
Формулировка: Нужно найти конкретное число в отсортированном массиве (с уникальными элементами), который был циклически сдвинут на некоторое число, учитывая, что массив не содержит дубликатов. Верните -1 если такого числа не найдено.Вот массив до сдвига:
Вот массив поле сдвига на 6 позиций:
Решение
Для решения мы использовали немного модифицированный бинарный поиск. Отметим, что как минимум одна половина массива всегда отсортирована. Если число n находится в этой половине, тогда проблема решается бинарным поиском.
Сложность: логарифмическая, O(logn).
Эффективность: логарифмическая, O(logn).
Реализовать LRU-кэш
Формулировка: Алгоритм LRU заключается в том, что для добавления новых элементов из кэша удаляются элементы, которые дольше всего не использовались.Для примера возьмём кэш, в который помещаются 4 элемента. В нем находятся 4 элемента.
Теперь мы добавим туда элемент — 5.
Решение
Кэширование — это техника хранения данных в более быстром хранилище (обычно в оперативной памяти), для того чтобы иметь к ним быстрый доступ. Обычно кэш ограничен в объёме. Поэтому при заполнении кэша нужно удалять из него данные.
LRU — очень простой и популярный алгоритм для этого. Мы удаляем самые старые данные, чтобы освободить место для новых.
Чтобы реализовать LRU кэш, нам понадобятся две структуры данных: хэш-таблица и двусвязный список. Двусвязный список помогает поддерживать порядок удаления из кеша, а хэш-таблица используется для поиска кэшированных элементов.
Вот описание алгоритма:
Если элемент существует в хэш-таблице
передвинуть его в хвост связного списка
Иначе
если кэш заполнился
удалить головной элемент из списка и запись о нём в хэш-таблице
Добавить новый элемент в хвост списка и в таблицу.
Получить элемент из кэша и вернуть
Замечание: Элемент, находящийся в конце списка — последний использовавшийся. Новые элементы также добавляются в конец списка.
Сложность:
- get (hashset): константная,O(1).
- set (hashset): константная,O(1).
- Удаление головы при добавлении нового элемента: константная,O(1).
- Поиск для удаления и добавления в хвост: линейная,O.
, где n — размер кэша.Поведенческие вопросы на собеседовании в Apple
- Расскажите про ваш самый лучший и самый худший день, за последние 4 года.
- Расскажите про ваш любимый продукт или сервис Apple. Объясните почему.
- Опишите достижение, которым вы особенно гордитесь.
- Были ли у вас разногласия с менеджерами по рабочим вопросами. Опишите ситуацию и то, как вы разрешили конфликт.
- Как вы преодолевали неудачу? Что вы из этого вынесли?
- Почему вы хотите работать в Apple?
- Что первое вы замечаете, когда заходите в Apple Store?
- Опишите самую сложную проблему в разработке, с которой вы сталкивались. Как вы её решили?
- Если вас примут в Apple, то будете ли вы скучать по чёму-то с прошлой работы? По чёму вы будете скучать больше\меньше всего?
- Занимаетесь ли вы улучшением своих навыков вне работы?
- Опишите случай, когда вы сделали для клиента всё возможное.
- Объясните 8-ми летнему ребёнку, что такое модем\роутер и его функции.
- Как должность, на которую вы претендуете, сочетается с вашим 5-ти летним карьерным или жизненным планами?
- Над чем вы хотели бы работать, если мы вас наймём?
- Как бы вы тестировали ваше любимое приложение?
- Как бы вы повели себя, если бы в поддержку обратился клиент с устаревшим продуктом?
- Опишите ситуацию.
- Опишите задачу.
- Опишите шаги которые нужно предпринять для её решения.
- Опишите достигнутый результат.
Советы для подготовки к собеседованию в Apple
- Работайте с разными инструментами. Хорошая идея сочетать использование маркерной доски, онлайн курсов, и имитации собеседования. Очень важно тренироваться говорить вслух о том, как вы решаете задачу.
- Напишите план обучения. Рекомендуется написать детальный план на 3-6 месяцев, чтобы ничего не упустить.
- Избегайте заучивания. Также не заучивайте вопросы. Вместо этого практикуйтесь в создании реальных продуктов, которые могла бы использовать Apple. Это идеальный способ подготовиться к собеседованию: вы изучаете концепции, практикуетесь в решении проблем и обретаете уверенность, проектируя для Apple.
Источник статьи: https://tproger.ru/translations/sobesedovanie-v-apple-top-30-voprosov-i-otvetov/