Кажется, что собеседования по кодированию становятся только сложнее, и подготовка к ним — непростая задача. Нет предела тому, какие вопросы могут быть заданы вам на собеседовании, и многие из них непросты. «Самые сложные» вопросы будут разными для каждого человека. То, что вам легко дается, может оказаться чрезвычайно трудным для кого-то другого, и наоборот.
Независимо от того, какие у вас «самые сложные» вопросы, очень важно подготовиться к собеседованию по кодированию. Мы поговорили с младшими и старшими разработчиками, чтобы они ответили на самые сложные вопросы собеседования по программированию, и составили список из пяти лучших. Сегодня мы рассмотрим этот список более подробно и дадим вам несколько советов, как подготовиться.
Как спроектировать сборщик мусора
Если вы никогда об этом не слышали, проблема со сборщиком мусора, как известно, очень сложна. Сборка мусора — это тема, которую большинство людей не изучают в школе, и связанные с ней материалы чрезвычайно плотны. Изучение сборки мусора требует много теоретических знаний, которые могут быть ошеломляющими. Независимо от того, на каком языке вы работаете, важно знать все тонкости предпочитаемого вами языка, чтобы эффективно решить эту проблему.
Не бойтесь задавать вопросы интервьюеру, работая над этой проблемой. Помните, что ваш интервьюер готов помочь вам и хочет, чтобы вы преуспели. Интервьюеры часто дают вам небольшие семена информации, которые помогут вам двигаться в правильном направлении.
Примечание. Вопросы о сборке мусора особенно часто встречаются на собеседованиях по основному и продвинутому Java, но они также важны для других языков программирования.
Проблема обмена монет
Проблема обмена монет часто встречается на интервью в Facebook и Amazon. Вам выдаются монеты разного достоинства и общая сумма денег. Исходя из этого, вам нужно написать функцию для вычисления наименьшего количества монет, которое вам нужно, чтобы составить эту сумму. Если вы не можете получить указанную сумму денег с помощью любой комбинации монет, вы вернетесь −1.
Вот три способа решить эту проблему:
- Грубая сила
- Нисходящее динамическое программирование с мемоизацией
- Восходящее динамическое программирование с табуляризацией
Давайте посмотрим на восходящее динамическое программирование с решением для табличной обработки на C ++:
#include <iostream>using namespace std;int countChange(int denoms[], int denomsLength, int amount) {// Edge casesif(amount <= 0 || denomsLength <= 0)return 0;int i, j, x, y;// We need n+1 rows as the table// is constructed in bottom up// manner using the base case 0// value case (n = 0)int lookupTable[amount + 1][denomsLength];// Fill the enteries for 0// value case (n = 0)for (i = 0; i < denomsLength; i++)lookupTable[0][i] = 1;// Fill rest of the table entries// in bottom up mannerfor (i = 1; i < amount + 1; i++) {for (j = 0; j < denomsLength; j++) {// Count of solutions including denoms[j]x = (i — denoms[j] >= 0) ? lookupTable[i — denoms[j]][j] : 0;// Count of solutions excluding denoms[j]y = (j >= 1) ? lookupTable[i][j — 1] : 0;// total countlookupTable[i][j] = x + y;}}return lookupTable[amount][denomsLength — 1];}// Driver Codeint main() {int denoms[4] = {25,10,5,1};cout << countChange(denoms, 4, 10) << endl;}
Для каждой итерации внутреннего цикла мы получаем решение denoms[j]и сохраняем его в x. Мы также получаем раствор denoms[j]и храним его в нем y. Таким образом мы можем ссылаться на более ранние решения, чтобы избежать дублирования вычислений.
Для каждой монеты номинала может быть только две возможности: включить ее или исключить. Мы знаем, что если монета, denom[j]больше, чем amount, то xустанавливается в 0, так как включение ее в рассмотрение невозможно.
Временная сложность равна * O (amount * denomsLength), что является количеством итераций цикла for.
Примечание. Каждый из этих трех методов включает временную сложность, а это означает, что временная сложность является важным понятием, которое необходимо понять, чтобы добиться успеха в проблеме смены монеты.
Проблема обедающих философов (многопоточность)
Проблема обедающих философов обычно используется при разработке параллельных алгоритмов для демонстрации проблем с синхронизацией и методов их решения. В задаче говорится, что за круглым столом сидят пять философов. Философы должны альтернативно думать и есть.
Перед каждым философом стоит миска с едой, и им требуется по вилке в каждой руке, чтобы поесть. Однако доступно всего пять вилок. Вам необходимо разработать решение, в котором каждый философ сможет есть свою пищу, не создавая тупиковой ситуации.
С этой проблемой разработчики часто упускают из виду, что на самом деле она не спрашивает о реальном сценарии, а скорее иллюстрирует типы проблем, с которыми вы можете столкнуться при выполнении многопоточных программ и / или небрежном обращении с блокировками. Идея состоит в том, чтобы заставить вас задуматься об ограничениях и правильном порядке для выполнения этой задачи наиболее эффективным способом.
Чтобы подготовиться к этому вопросу, вам следует глубже погрузиться в синхронизацию, управление параллелизмом и семафоры.
Вот два возможных способа решить эту проблему:
- Ограничение философов, которые собираются есть
- Повторный заказ вилочного подборщика
Давайте посмотрим, как переупорядочить решение для вилочного захвата в Java:
public class DiningPhilosophers2 {private static Random random = new Random(System.currentTimeMillis());private Semaphore[] forks = new Semaphore[5];public DiningPhilosophers2() {forks[0] = new Semaphore(1);forks[1] = new Semaphore(1);forks[2] = new Semaphore(1);forks[3] = new Semaphore(1);forks[4] = new Semaphore(1);}public void lifecycleOfPhilosopher(int id) throws InterruptedException {while (true) {contemplate();eat(id);}}void contemplate() throws InterruptedException {Thread.sleep(random.nextInt(500));}void eat(int id) throws InterruptedException {// We randomly selected the philosopher with// id 3 as left-handed. All others must be// right-handed to avoid a deadlock.if (id == 3) {acquireForkLeftHanded(3);} else {acquireForkForRightHanded(id);}System.out.println(«Philosopher » + id + » is eating»);forks[id].release();forks[(id + 1) % 5].release();}void acquireForkForRightHanded(int id) throws InterruptedException {forks[id].acquire();forks[(id + 1) % 5].acquire();}// Left-handed philosopher picks the left fork first and then// the right one.void acquireForkLeftHanded(int id) throws InterruptedException {forks[(id + 1) % 5].acquire();forks[id].acquire();}}
В этом решении вы заставляете любого из философов сначала брать левую вилку, а не правую. Неважно, какого философа вы выберете левшой и заставите его первым подобрать левую вилку. В нашем решении мы выбрали философа с id = 3 в качестве философа-левши.
Зачем использовать эти передовые методы программирования
Изучая программирование, вы обычно изучаете некоторые » лучшие практики «. Наиболее эффективные разработчики внедряют определенные методы в свой процесс кодирования, что помогает им гарантировать, что их код является наилучшим как по функциям, так и по форме.
Имея многолетний опыт программирования, вы, как правило, знаете, какие методы следует избегать и какие следует применять. Вы можете иметь общее представление о том, почему одни практики лучше других, но споткнетесь, когда пришло время объяснить причины.
Вот несколько примеров передового опыта:
- Часто комментируйте свой код
- Распознавать и удалять повторяющийся код
- Группировка по функциям в React
- Избегайте скрытых структур в Ruby
Лучший способ подготовиться к этим вопросам — освежить в памяти полезные практики, которых можно избежать, и их доводы. Помните, что во время собеседования вы можете обсудить эти вопросы со своим интервьюером.
Реализовать кеш LRU
Вопрос о реализации кэша Least Recently Used (LRU) задается в некоторых интервью Google, Microsoft и Amazon, но это не очень распространенный вопрос. Этот вопрос требует от вас более глубокого размышления и объединения двух или более существующих структур данных.
Важно внимательно прочитать проблему и убедиться, что вы понимаете, о чем от вас просят. Эти вопросы обычно просят вас сделать несколько вещей. После того, как вы внимательно прочитали проблему, вы можете попросить интервьюера подтвердить, что вы идете в правильном направлении.
Прежде чем приступить одной из этих проблем, убедитесь, что вы понимаете, что кэш является. LRU — это общая стратегия кэширования, которая определяет политику удаления элементов из кеша, чтобы освободить место для новых, когда кеш заполнен. Это означает, что сначала отбрасываются наименее использованные элементы.
Следующие шаги по подготовке к собеседованию
Вопросы, которые мы рассмотрели сегодня, — это лишь некоторые из множества сложных вопросов на собеседовании по кодированию. Предполагается, что вопросы будут сложными, и они могут поставить в тупик даже самых опытных разработчиков. Важно начать подготовку к собеседованию как можно раньше, чтобы у вас была возможность подготовиться как можно больше. Еще несколько сложных проблем:
- Найдите медиану из потока данных
- Искать в повернутом отсортированном массиве
- Минимальные ходы конем
- И многое другое
Начните подготовку к собеседованию по кодированию сегодня с учебного курса по подготовке к собеседованию на основе текста, Decode the Coding Interview. Наша команда экспертов объединила наиболее часто задаваемые вопросы на собеседовании в ведущих технологических компаниях в тщательно разработанный набор сценариев, на которых вы можете учиться. Вы можете практиковаться в практических средах программирования прямо в браузере. Наш курс собеседования по программированию помог разработчикам подготовиться к собеседованию с ведущими технологическими компаниями, такими как Netflix, Facebook, Microsoft, Amazon и Google.
