Прежде всего, я хотел бы поблагодарить восторженного и полезного одноклассника Цуй, который терпеливо объяснил мне стиль интервью в библиотеке вопросов об обезьянах, так что я могу только спокойно подготовить алгоритм и дизайн системы. Однако алгоритм не готов.Недавно я просто нормально отмахивался от вопросов, системный дизайн только что пересматривал проект Sogou. Это как быть голым. . . К счастью, других вопросов я не задавал и, наконец, получил предложение о стажировке.

одна сторона

Интервьюеру с одной стороны вроде бы меньше 30. Это должен быть обычный НИОКР, и, конечно, это, скорее всего, квази-ментор. Вошли в комнату и представили процесс собеседования и компанию, после чего попросили меня задавать вопросы. Я думаю, что это не точно, но спрашивать не о чем, поэтому я задал несколько вопросов о процессе собеседования.

алгоритм

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

Связанный список, своп двух элементов

Дан головной узел head односвязного списка, два значения v1, v2, найти эти два узла в связном списке и поменять их местами.

Информация для уточнения у интервьюера:

с или без пред.
Структура узла (val, next)
возвращаемое значение

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

Как только я собирался писать, интервьюер остановил меня и сказал, что я могу сначала рассказать о своих идеях. Я очень благодарен, что могу говорить первым,Не является...". Интервьюер убедился, что я написал код после этого.

Алгоритм очень простой, просто посмотрите на код:

// define of Node(val, next)
public Node swap(Node head, int v1, int v2) {
  // no need to swap
  if (head == null || head.next == null) {
    return head;
  }
  // no need to swap
  if (v1 == v2) {
    return head;
  }

  Node dummy = new Node(0, head);
  Node prev1 = dummy;
  Node prev2 = dummy;
  Node prev = dummy;
  while (prev.next != null) {
    if (prev.next.val == v1) {
      prev1 = prev;
    }
    if (prev.next.val == v2) {
      prev2 = prev;
    }
  }

  // no need to swap
  if (prev1 == dummmy || prev2 == dummmy) {
    return head;
  }

  internalSwap(prev1, prev2);
  return dummy.next;
}

private void internalSwap(Node prev1, Node prev2) {
  if (prev1.next == prev2) {
    internalSwapNextTwo(prev1);
    return;
  }
  if (prev2.next == prev1) {
    internalSwapNextTwo(prev2);
    return;
  }

  Node next1 = prev1.next;
  Node next2 = prev2.next;
  prev1.next = next2;
  prev2.next = next1;
  Node tmp = next1.next;
  next1.next = next2.next;
  next2.next = tmp;
  return;
}

private void internalSwapNextTwo(Node first) {
  Node second = first.next;
  Node third = second.next;
  second.next = third.next;
  third.next = second;
  first.next = third;
  return;
}

После написания кода на собеседовании меня также попросили рассказать о моих идеях с кодом. Эта часть в основном предназначена для того, чтобы избавить интервьюера от необходимости внимательно читать код, и интервьюеру также удобно изучить модульность вашего кода и даже имена некоторых переменных и функций. Основная часть алгоритма была упомянута только что, поэтому я привел ее в одном предложении, сосредоточившись на граничных условиях в методе подкачки, а затем интервьюер сам начал смотреть код. Затем позвольте мне рассказать о принципе метода internalSwap.Я также сначала расскажу об основной части алгоритма, а затем расскажу о граничных условиях.

Вращение матрицы

Интервьюер сказал, что этот вопрос очень распространен, но я только слышал о нем и пожалел, что не прочитал его в то время.

учитываяn*nМатрица целых чисел, которая вращает матрицу.

Информация для уточнения у интервьюера:

Выводить ли элементы матрицы в повернутом порядке или изменить исходную матрицу
возвращаемое значение

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

Сначала я не очень хорошо изложил этот вопрос и не спросил возвращаемое значение, думая, что мне просто нужно вывести элементы матрицы в повернутом порядке (контролируя порядок цикла). После обсуждения идеи интервьюер понял, что я неправильно понял смысл вопроса, и терпеливо сказал мне вернуть матрицу. Но я не спешил отрицать свой метод, а спросил меня о временной и пространственной сложности этого метода. Это все O (n ^ 2), и интервьюер сказал, что исходную матрицу также можно изменить, чтобы уменьшить сложность пространства.

Я думал об этом какое-то время и думал, что обратная операция, как правило, O (1), и она часто может достигать магических эффектов за счет различных комбинаций реверсов. Поэтому я подумал о том, чтобы сначала двигаться задним ходом по диагонали главной диагонали, то есть поворачиваться по диагонали — почти, а затем двигаться задним ходом по вертикальной оси, то есть переворачиваться и держаться за траву.

я использую3*3После того, как я объяснил свои идеи интервьюеру, интервьюер попросил меня снова поэкспериментировать.4*4Матрица, я думал, что проблема, и результат оказался правильным после рисования. Интервьюер сказал: «Ну, эксперимент удался. На самом деле это математическая проблема, она связана с природой матрицы, можете ли вы это доказать?» Я совсем забыл об этом, поэтому просто позволил мне написать код.

Код:

public int[][] transfer(int[][] matrix) {
  if (matrix == null || matrix.length <= 1) {
    return matrix;
  }
  if (matrix[0] == null || matrix[0].length <= 1) {
    return matrix;
  }

  xiefan(matrix);
  duifan(matrix);
  return matrix;
}

private void xiefan(int[][] matrix) {
  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < i; j++) {
      swap(matrix, i, j, j, i);
    }
  }
}

private void duifan(int[][] matrix) {
  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length / 2; j++) {
      swap(matrix, i, j, i, matrix[0].length - 1 - j);
    }
  }
}

private swap(int[][] matrix, int x1, int y1, int x2, int y2) {
  int tmp = matrix[x1][y1];
  matrix[x1][y1] = matrix[x2][y2];
  matrix[x2][y2] = matrix[x1][y1];
}

Следующий процесс аналогичен предыдущему вопросу, анализу временной сложности и пространственной сложности.

Более популярное решение в Интернете — повернуть его напрямую, я тоже думал об этом во время интервью, но я думаю, что это непросто вывести, и это не является универсальным в природе обратного. Тем не менее, я чувствую, что мне нужно освоить это использование, и мне не нужно запоминать его.Я прочитал ключевой момент один раз, и я могу быстро представить его во время интервью. Ссылаться наLeetCode: Повернуть изображениерешение 2.

простой проект чата

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

две стороны

Интервьюер со второй стороны очень красивый, это напомнило мне интервью в Ницце в сентябре прошлого года, но в середине интервью я подошла к встрече и попросила меня подождать 20 минут, и в итоге я ждала в течение часа. Посередине есть более смущающие вещи, но это не важно и не намеренно, интервью важнее всего.

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

алгоритм

Нерекурсивная версия сортировки слиянием

Я взял только один алгоритмический вопрос, и интервьюер закончил говорить смысл вопроса.Увидев, что у меня нет идей, я ушел первым, оставив мне 20 минут на размышление + код.

Вы знаете сортировку слиянием? Сортировка слиянием обычно реализуется с рекурсией, но как ее реализовать без рекурсии?

Информация для уточнения у интервьюера:

возвращаемое значение

Да, я не видел этот вопрос раньше, когда я начал чистить вопрос. Но через некоторое время я понял, что использовать цикл для имитации процесса выполнения рекурсивной версии сортировки слиянием, Алгоритм описан следующим образом:

Подать заявку на массив B с размером A.length
Установите для segLen значение 1 и определите подмассив длины segLen как 1 seg.
Каждые два сегмента представляют собой группу, выполняйте двустороннее слияние соответственно.
скопировать массив B обратно в A
segLen = segLen * 2
Если segLen меньше A.length, вернуться к шагу 3, иначе продолжить
возвращаемый массив А

Поскольку интервьюер отсутствовал на совещании, я написал код напрямую:

public int[] mergeSort(int[] array) {
  if (array == null || array.length <= 1) {
    return array;
  }

  int[] arrA = array;
  int[] arrB = new int[arrA.length];
  for (int seg = 1; seg < arrA.length; seg *= 2) {
    for (int i = 0; (i + 1) * seg < arrA.length; i++) {
      merge(arrA, i * seg, (i + 1) * seg, seg, arrB);
    }
    System.arrayCopy(arrB, arrA);
  }

  return arrA;
}

private void merge(int[] arrA, int start1, int start2, int seg,
              int[] arrB){
  int l = start1;
  int r = start2;
  int i = start1;
  while (l < start1 + seg && r < start2 + seg
         && l < arrA.length && r < arrA.length) (
    if (arrA[l] <= arrA[r]) {
      arrB[i] = arrA[l];
      l++;
    } else {
      arrB[i] = arrA[r];
      r++;
    }
    i++;
  )
  while (l < start1 + seg && l < arrA.length) {
    arrB[i] = arrA[l];
    l++;
    i++;
  }
  while (r < start2 + seg && r < arrA.length) {
    arrB[i] = arrA[r];
    r++;
    i++;
  }
  return;
}

Последнее также является анализом временной сложности и пространственной сложности. Обратите внимание, как проанализировать временную сложность этой задачи: внешний цикл — O(logn), внутренний цикл — O(n), а копирование массива — O(n), поэтому общий алгоритм — O(nlogn).

system design

Фон не указан, и краткое описание выглядит следующим образом:

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

Информация для уточнения у интервьюера:

Что такое рейтинг в таблице лидеров - объем работы
Объем работ заключается в подсчете количества рабочих мест или общей сумме - всего

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

К титулу предъявляются четыре требования:

Все запросы в режиме реального времени
Студенты могут просматривать свои собственные рейтинги
Поддерживать топ-100 лидеров
Нагрузка обнуляется каждый день и пересчитывается

Не интересен пункт 4. Это нормально для подбазы и подтаблицы, или даже для очистки базы данных один раз в день, что можно игнорировать. Для систем с высокой степенью параллелизма можно резюмировать два требования:

Студенты могут проверять свои рейтинги в режиме реального времени.
Таблицы лидеров могут обновляться в режиме реального времени.

Решение, которое я разработал, основано на корзине — причина, по которой я подумал о корзине, заключалась главным образом в том, что я все еще просматривал исходный код ConcurrentHashMap перед интервью. ConcurrentHashMap — это артефакт в пакете java.util.concurrent, а также обычный тестовый сайт для интервью.Знаете ли вы, как реализован его метод size()? Я забыл, но в моих заметках в книге обсуждаются три варианта:

Поддерживайте переменную размера; каждый раз, когда сегмент обновляется, переменная размера изменяется синхронно. Узким местом параллелизма является блокировка переменной размера, что эквивалентно возврату к последовательным обновлениям.
Переменная size не поддерживается, но сохраняется segSize каждого сегмента; каждый раз, когда сегмент обновляется, изменяется только segSize; каждый раз, когда вызывается метод size(), все segSize суммируются. Различные стратегии суммирования segSize могут быть выбраны в соответствии с требованиями согласованности: если требуется полная согласованность, все сегменты находятся на момент расчета, тогда узкое место параллелизма будет сгенерировано при вызове метода size(); если требуется слабая согласованность , сумма может быть непосредственно добавлена.
Сохраняйте переменную размера; при изменении segSize установите размер равным -1; при вызове метода size(), если размер равен -1, пересчитайте размер, как указано выше; если размер не -1, это означает что сегмент не был изменен в течение периода, размер возврата напрямую. Схема 3 в основном предназначена для схемы 2, которая эквивалентна кэшированию значения размера, так что нет необходимости повторно вычислять размер, когда segSize не изменяется.

Чтобы хорошо понять эти три схемы, мой дизайн основан на схеме 2.

Требование 1

Для требования 1 это эквивалентно вызову метода size() в ConcurrentHashMap. Отличие в том, что учеников может быть несколько десятков миллионов, и поддерживать размер каждого ученика явно нецелесообразно, и только схема 2 не требует сохранения размера.

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

当前学生的排名 = 当前学生之前所有桶的size之和 + 当前学生在其桶内的排名

Требования к реальному времени требования 1, как правило, не такие высокие, потому что пользователи смотрят только на свои собственные рейтинги, даже если есть определенная задержка, это не повлияет на пользовательский опыт, поэтому допустимо рассчитывать потребление каждый раз. пользователь просматривает рейтинги. Конечно, мы можем дополнительно оптимизировать, например поддерживать общий рейтинг R до начала каждого абзаца, но для этого потребуется добавить сервис для поддержания общего рейтинга R' абзаца после абзаца в реальном времени, что может быть невозможно. стоит выигрыш.

Требование 2

Ковши с высокой рабочей нагрузкой называются ковшами большого конца, а ковши с низкой рабочей нагрузкой — ковшами малого конца. Для требования 2 это эквивалентно сохранению первых 100 учащихся в большой корзине. Поскольку предполагается, что количество домашних заданий ограничено, вы можете начать обход с ведра, где находится максимальное количество домашних заданий, пока не будет пройдено непустое ведро, и не будут пройдены 100 учеников в порядке убывания количества домашних заданий. , и таблица лидеров возвращается.

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

Оптимизация может продолжаться — поскольку нас интересует исправление 100 лучших студентов, лучше поддерживать maxHeap напрямую. Для таблицы лидеров, очевидно, есть только операции вставки и запроса (взять первые 100). Базовая модель эквивалентна вставке O (1) и запросу O (nlogn) или сортировке вставками, тогда вставка O (n) и запрос — O(1) ), в то время как максимальная вставка кучи — O(logn), а запрос — O(1).

Поскольку студентов с высокой нагрузкой всегда очень мало, параллелизм больших сегментов намного меньше, чем у других сегментов.Стоимость поддержки maxCnt и maxHeap очень мала, но преимущества значительны.

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

follow up

После того, как основная структура была представлена, интервьюер задал несколько дополнительных вопросов:

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

Что касается вопроса 1, я поставил на него решение высокой доступности Hadoop. Интервьюер, похоже, не понял содержания Hadoop и подумал, что я ответил на него хорошо. По вопросу 2 я четко проанализировал, что ведро и сервис не должны храниться в одной памяти, а должны попытаться сделать сервис без состояния, а ведро должно быть передано на уровень хранилища, и нет необходимости заботиться о структуре ведра. Преобразован вопрос 2 в вопрос 3 «Как исправить единую точку отказа в хранилище».

Во-первых, схема HA все еще действует. Но старый скучен, поэтому я сказал, что его можно изменить. Сервер имеет несколько экземпляров.Клиент монтирует список экземпляров сервера, и позволяет клиенту поддерживать консистентность данных сервера при записи данных (все записи считаются успешными), и попутно решает проблему балансировки нагрузки при чтении данных ; использовать идентификатор транзакции Решить проблему согласованности, вызванную сбоем записи клиента.

Теперь, когда я пишу сутру, я понимаю, что ответ здесь нехороший. Нагрузка записи в этой схеме слишком высока, а проблемы с синхронизацией часто связаны с параллельной записью, что еще более проблематично. Если он по-прежнему основан на клиентском решении, вы можете обратиться к стратегии NRW, и вам нужно только убедиться, что R+W>N может обеспечить строгую согласованность. Тем не менее, я все еще чувствую, что он недостаточно хорош, например, этот дизайн не учитывает масштабируемость, и он все еще далек от настоящей распределенной системы хранения.

PS:

N представляет количество реплик данных.

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

W представляет собой минимальное количество реплик, которое необходимо записать для завершения операции записи, то есть минимальное количество узлов, участвующих в операции записи.

Суммировать

Эй, уже 7:30 после интервью. Начиная с 4:30 дня, 3 часа, это было еще довольно утомительно и утомительно, но я был очень доволен, чтобы получить предложение на месте.

Наконец, попросите интервьюера оценить меня:

Быстрый ответ - может быть, потому что я видел, что я не сделал последние два вопроса, но я разобрался сам.
Код хорошо написан - польщен, так смущен! ! !
Дизайн системы также хорош. Учитывая основные проблемы, я могу четко спроектировать осуществимое решение. Хотя у меня может не быть большого контакта с отраслевым решением, мое собственное решение относительно завершено.

Интервьюером со второй стороны был директор департамента (директора стартап-компаний все достаточно молоды) Эта оценка должна быть несколько преувеличена. Однако направление должно быть достойным ссылки, чтобы помочь вам развить сильные стороны и избежать слабых сторон.

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

Совет себе:

Послушно чистите вопросы, количество вопросов слишком мало, и вы будете быстры, когда столкнетесь с новыми вопросами.
Прислушиваться к практике и выражению Мастера Цяна, особенно в проектировании системы, как быть ясным по порядку, четко формулировать и демонстрировать свои способности, это очень важно.
Старайтесь не оголяться, на этот раз благодаря тому, что мне довелось прочитать соответствующий контент перед интервью, иначе могу повесить трубку
Курица, не пухни! Не вздувайся! Не вздувайся!

Ссылка на эту статью:[Мяньцзин] Ape Question Bank — 25 августа 2017 г., случайный набор стажеров
автор:обезьяна 007
Источник:monkeysayhi.github.io
Эта статья основана наCreative Commons Attribution-ShareAlike 4.0Выпущено по международному лицензионному соглашению, приветствуется перепечатка, вывод или использование в коммерческих целях, но авторство и ссылка на эту статью должны быть сохранены.