[Mean Jing] Toutiao-30 августа 2017 г., случайный набор стажеров

интервью алгоритм Hadoop HDFS Yarn

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

одна сторона

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

проект

Оба проекта представляют собой краткие введения без подробных вопросов.

База

параллелизм

  • Внутри условной переменной есть блокировка.Почему внешний слой должен быть заблокирован при ожидании условной переменной (на коленях)
  • Кроме того, чтобы уведомить, при каких обстоятельствах можно ждать пробуждения (на коленях)

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

алгоритм

Проверить, является ли бинарное дерево бинарным деревом поиска

Тема очень знакомая, но тоже писалась.

Я немного не могу вспомнить определение бинарного дерева поиска (BST), поэтому сначала кратко подтвердил его интервьюеру. Далее уточняйте тему у интервьюера:

  • Предполагая отсутствие повторяющихся значений
  • Дайте четкое определение BST:
    1. я лучше всех
    2. г это BST
    3. удовлетворитьl < root < r

Скажите интервьюеру использовать разделяй и властвуй и начинай писать код. На полпути интервьюер сказал мне, что можно рассмотреть предварительный порядок, порядок и последующий обход бинарного дерева. Я отреагировал на прямой обход по порядку, при обходе определяя, увеличивается ли последовательность. Обсудив идею, я спросил у интервьюера, могу ли я сначала написать свое оригинальное решение, чтобы мне не пришлось менять свои идеи и сохранять ошибки. После того, как интервьюер объединился, я продолжил писать:

private class Result {
  public boolean isBST;
  public int min;
  public int max;
  public Result(boolean isBST, int min, int max) {
    this.isBST = isBST;
    this.min = min;
    this.max = max;
  }
}

public isBST(TreeNode root) {
  if (root == null) {
    return true;
  }

  Result result = dc(root);
  return result.isBST;
}

private Result dc(TreeNode root) {
  if (root == null) {
    return null;
  }
  if (root.left == null && root.right == null) {
    return new Result(true, root.val, root.val);
  }

  Result lResult = dc(root.left);
  Result rResult = dc(root.right);
  if (lResult != null && (!lResult.isBST || lResult.max >= root.val) {
    return new Result(false, 0, 0);
  }
  if (rResult != null && (!rResult.isBST || rResult.min >= root.val)) {
    return new Result(false, 0, 0);
  }

  // 忘记了这里的check，no face, no bug free
  int min = root.val;
  int max = root.val;
  if (lResult != null) {
    min = lResult.min;
  }
  if (rResult != null) {
    max = rResult.max;
  }
  return new Result(true, min, max);
}

Код по принципу «разделяй и властвуй» немного долго писать, но вы должны его придерживаться.стиль кодированияиbug free.

Но, когда писал первый раз, баг все-таки был, и вспомнил о нем, как только отдал бумагу интервьюеру - последнее предложение return не проверял на нулевой указатель, блин, тупо. К счастью, интервьюер не возражал, спасибо.

В случае обхода по порядку простая операция может полностью сохранить последовательность и перепроверить ее, но это пустая трата места, сложную операцию приходится проходить и проверять одновременно, я не разобрался достаточно краткий способ написать это. (Быть добавленным)

две стороны

проект

Холодное сжатие и хранение данных — гриф

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

  • Зачем полагаться на внешнюю конфигурацию и не интегрироваться с HDFS

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

Мониторинг кластера Hadoop — ястреб

Указывает на то, что сам проект очень простой, и сложно определить точное значение отслеживаемых показателей.

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

  • что это значит точно

Я говорил о случае, когда ContainerExitStatus=137.

исходный код

Как реализована федерация в HDFS

Маунт клиента, как мапить балабалу.

Как правило, HA также используется в Федерации, давайте поговорим о принципе HA.

Zookeeper гарантирует, что в каждый момент времени существует не более одного активного узла; единственный активный узел записывает данные в журналNode, а другой резервный узел читает данные из журналаNode.

Какой контент синхронизируется между двумя узлами в HA (колено)

Сначала я подумал, что это то же самое, что и механизм SecondaryNameNode, но потом хорошенько обдумал: так как standby может читать данные из journalNode, ему не нужно тянуть лог редактирования из актива, как SecondaryNameNode, и, естественно, он это делает. не нужно сливать лог на резервный и синхронизировать его обратно на активный.

Итак, признаюсь, что я не видел этот кусок контента, и у меня нет никаких идей.

Какой исходный код Yarn вы знаете лучше?

Конечный автомат, планирование событий

Как запускается контейнер

Это довольно грубо:

  1. НМ получает заказ
  2. Создайте конечный автомат контейнера, инициализируйте ресурсы и т. д.
  3. Служба ContainerLaucher получает событие LAUNCH_CONTAINER
  4. Создайте скрипт launch_container
  5. Создайте скрипт container_executor, который запустит процесс Java.

Работа контейнера требует загрузки некоторых ресурсов, вы понимаете этот процесс?

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

Системный дизайн

Недостатки реализации Federation с монтированием на стороне клиента

  • Таблица монтирования настраивается на стороне клиента, поэтому после изменения таблицы монтирования клиент также должен делать синхронные модификации, и у пользователя не может быть никакого восприятия или низкого восприятия.
  • Федерация также имеет целью балансировку нагрузки при расширении NameNode, но монтирование клиента эквивалентно ручному поддержанию балансировки нагрузки, и любые изменения в трафике не могут поддерживать баланс.

Просто хочу придумать эти два момента.быть улучшенным.

Как реализовать федерацию (полустоя на коленях) без использования монтируемого стола

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

Ядром федерации является отношение отображения из каталога в NameNode.. Существенным недостатком монтирования на стороне клиента является то, что отношения сопоставления сохраняются на клиенте, поэтому выполнение всех функций зависит от клиента. Таким образом, первым шагом оптимизации является сохранение отношения сопоставления на сервере. Ниже приведены два варианта:

  • Сохраните карту на сервере. Кроме того, если вы хотите получить доступ к каталогу /logdata, создайте файл /logdata и сохраните NameNode, сопоставленный с каталогом /logdata, в файле. Каждый раз, когда клиент впервые обращается к файлу /logdata, получает сопоставленный NameNode, а затем обращается к каталогу /logdata на NameNode. Эффект эквивалентен перемещению монтирования клиента на сервер.
  • Служба Proxy устанавливается перед NameNode, и Proxy поддерживает отношение сопоставления в памяти. Даже новые балансировщики и автоматические монтирования могут быть реализованы на основе прокси-сервера для достижения балансировки данных и балансировки трафика разных стандартов (между NameNode, одним и тем же NameNode).

То, что я ответил, было не совсем тем, что хотел интервьюер - интервьюер спросил меня, видел ли я исходный код Hdaoop 3.0, я сказал, что вообще его не видел, а интервьюер сказал, что если бы я его не видел, я бы не суметь ответить.

Если вы используете прокси-решение, оцените количество запросов в секунду

1w узлов, каждый узел40核+256G, все запускают MR, каждый контейнер1核+2G. Оцените количество запросов в секунду, которое должен выдержать прокси.

Предполагая, что AM запущен, он применяется ко всем контейнерам кластера, и все они запускают сопоставитель, и AM можно игнорировать. Предполагая, что каждому сопоставителю необходимо посетить NameNode 5 раз в течение 1 минуты (60 с), ему необходимо посетить прокси (получив карту) не менее 5 раз. но:

qps = (10E4 * 40 / 1) * 5次/60s = 3.67 * 10E4 次/s

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

База

Параллельный (полустоя на коленях)

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

  • Как можно использовать блокировки в Java

Синхронизирован, ReentrantLock, запись блокировки с помощью AQS.

Здесь я также написал параллельные инструменты Condition и CountDownLatch, позже я подумал, что они более синхронны, поэтому удалил их. Это принадлежитОбычные вопросы с частичными понятиями, вам нужно почистить лицо, чтобы узнать стандартный ответ.

  • Как сделать замки «реентри» (полуна коленях)

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

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

  • Расскажите о параллелизме, с которым вы знакомы

Сравните HashTable и ConcurrentHashMap.

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

Чтобы задать простой вопрос, какие методы есть в классе Object (полуприседая)

  • wait, notify, notifyAll
  • toString
  • hashCode, equals

Тогда нельзя говорить.

Теперь он добавляется следующим образом:

public class Object {
    private static native void registerNatives();
    static {
        registerNatives();
    }

    public final native Class<?> getClass();

    public native int hashCode();
    public boolean equals(Object obj) {
        return (this == obj);
    }

    protected native Object clone() throws CloneNotSupportedException;

    public String toString() {
        return getClass().getName() + "@" + Integer.toHexString(hashCode());
    }

    public final native void notify();
    public final native void notifyAll();
    public final native void wait(long timeout) throws InterruptedException;
    public final void wait(long timeout, int nanos) throws InterruptedException {...}
    public final void wait() throws InterruptedException {
        wait(0);
    }
    protected void finalize() throws Throwable { }
}

Основной недостающий ответ — клон, getClass. доработайте, зарегистрируйте туземцев, тоже постарайтесь запомнить.

На что обратить внимание при переопределении hashCode

В основном, когда необходимо оценить равенство, например, метод get HashMap, существуют требования к порядку вызова hashCode и equals:

if (table[pos].key.hashCode() == key.hashCode 
  && (table[pos].key == key || table[pos].equals(key))) {
  return table[pos];
}

Только когда hashCode равен, equals может быть равным, то есть «после переопределения, если equals равны, тогда hashCode также должен быть равен».

При этом для HashMap также необходимо следить за тем, чтобы hashCode ключа был равен до и после вставки.

Обобщенно следующим образом:

  1. Если равные равны, то hashCode также должен быть равным
  2. Для одного и того же объекта до и после его вставки в HashMap hashCode неизменяем.

инженерный код

Внедрить новую хэш-таблицу по запросу (на коленях)

Мы знаем, что сопоставление BlockId с BlockInfo сохраняется в NameNode для быстрого поиска. Если он реализован непосредственно с помощью HashMap (конечно, на самом деле это не HashMap, а Google LightWeightGSet), поскольку HashMap реализован с застежкой-молнией, каждый узел имеет не более двух указателей, предполагая, что каждый указатель занимает 2 байта, тогда 100 миллионов блоков будет занимать не менее 400 миллионов байт, если предположить, что это вызовет много пустого пространства. Вам нужно реализовать новую хеш-таблицу, определение интерфейса:

interface SimpleMap<K, V> {
 K get(K key);
 V put(K key, V value);
 V remove(K key);
}

Требовать:

  • Максимальное использование пространства
  • Некоторой производительностью можно пожертвовать

Сразу подумал о линейном обнаружении, перефразировании и других методах, я думал, что это так просто, после подтверждения того, что линейное обнаружение можно использовать, я начал набрасывать, а затем расшифровывать. Следует отметить, что идея метода del состоит в том, чтобы заполнить хвостовой узел удаленной позицией после удаления. Написав, сдал ответ — понял опять большой баг, и идея была неверна, также нашел бесконечный цикл в методе put. Однако эти два пункта относятся к моему базовому мышлению, поэтому я не буду показывать неправильный код.

Вернитесь и подумайте про себя, теперь добавьте правильный код, нереализованный неосновной код относится к HashMap:

public class LinearProbingHashMap<K, V> implements SimpleMap<K, V> {

  @Override
  public V get(Object key) {
    if (key == null) {
      return null;
    }

    int pos = indexFor(hash(key));
    for (int i = 0;
         i < table.length && table[pos] != null;
         i++, pos = (pos + 1) % table.length) {
      if (table[pos] == Entry.DELETED_ENTRY) {
        continue;
      }
      if (table[pos].keyHash == key.hashCode()
          && (table[pos].key == key || table[pos].key.equals(key))) {
        return table[pos].value;
      }
    }
    return null;
  }

  @Override
  public V put(K key, V value) {
    if (key == null) {
      return null;
    }

    int pos = indexFor(hash(key));
    int lastEmptyPos = -1;
    for (int i = 0;
         i < table.length && table[pos] != null;
         i++, pos = (pos + 1) % table.length) {
      if (table[pos] == Entry.DELETED_ENTRY) {
        lastEmptyPos = pos;
      }
      if (table[pos].keyHash == key.hashCode()
          && (table[pos].key == key || table[pos].key.equals(key))) {
        V oldValee = table[pos].value;
        table[pos].value = value;
        return oldValee;
      }
    }

    if (size + 1 < threshold) {
      if (lastEmptyPos == -1) {
        // assert table[pos] == null;
        lastEmptyPos = pos;
      }
      table[lastEmptyPos] = new Entry<>(key, value);
      size++;
      return null;
    }

    LinearProbingHashMap<K, V> newMap = new LinearProbingHashMap<>(table.length * 2);
    for (Entry<K, V> entry : table) {
      // TODO: 2017/8/31 remove extra cost on copy entry
      if (entry != null && entry != Entry.DELETED_ENTRY) {
        newMap.put(entry.key, entry.value);
      }
    }
    init(newMap); // update table, size, loadFactor, threshold, and etc.
    put(key, value);

    return null;
  }

  @Override
  public V remove(Object key) {
    if (key == null) {
      return null;
    }

    int pos = indexFor(hash(key));
    for (int i = 0;
         i < table.length && table[pos] != null;
         i++, pos = (pos + 1) % table.length) {
      if (table[pos] == Entry.DELETED_ENTRY) {
        continue;
      }
      if (table[pos].keyHash == key.hashCode()
          && (table[pos].key == key || table[pos].key.equals(key))) {
        V oldValue = table[pos].value;
        table[pos] = (Entry<K, V>) Entry.DELETED_ENTRY;
        size--;
        return oldValue;
      }
    }

    return null;
  }
}

задавать вопросы

  • Если вам посчастливилось устроиться на работу, за что вы можете нести ответственность после поступления на работу
  • Всего несколько раундов интервью
  • Оценка интервью

Ну, я думал, что сессия вопросов и ответов была последним раундом технических интервью.Когда я задал вопрос 1, интервьюер сказал, что он будет только трехсторонним. Всего есть три раунда собеседований, один и два примерно одного уровня, а три — технические лидеры.

Положительные отзывы:

  • В целом хорошая производительность
  • хороший стиль кода

негативный комментарий:

  • Последний вопрос имеет бесконечный цикл - большая проблема(То есть мышление можно простить, но нельзя простить бесконечный цикл)
  • Этот вопрос кажется простым, но ни один из людей, у которых я брал интервью, не мог писать без проблем. Вы должны подумать об этом позже
  • Если вы хотите быть распределенным, параллелизм — это основа. Первоначально последний вопрос также хотел проверить ваш параллелизм, но если вы скажете, что не разбираетесь в параллелизме, я вас не проверял.

Три стороны (сторона HR)

Интервьюер, который ждал три стороны, долго не приходил, я не выдержал, написал записку и оставил дверь открытой, чтобы сходить в туалет. . . Результат вернулся - женщина-интервьюер держит траву! Посмотри на лицо еще раз, подержи траву и накрасься! Как ни посмотри, это не похоже на технического лидера, ты узнаешь, что это HR, только когда спросишь. HR сказал, что технический руководитель был на совещании, и я только что встретил его Он сказал, что оценки двух предыдущих интервьюеров были хорошими, и ему не нужно интервью, поэтому он перешел сразу к интервью HR.

Не могу сказать, хорошие это новости или плохие. Я слышал, что этому руководителю 90 лет, он начал работать после окончания Университета Тианда, привел группу пост-80-х и 90-х. Сзади обычное собеседование с HR, но я чувствую, что HR Toutiao много спрашивает, всевозможные хобби, оценки, семья и так далее. В первый раз, когда я испытал эту битву, я учился и учился.

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

Суммировать

После интервью я поболтал со своими однокурсниками из колледжа (летняя стажировка Тутяо) и Таошэнем соответственно.Они оба ответили, что Тутяо находился под большим давлением, но в то же время он также проявил инициативу, чтобы сказать, что столовая была хорошей. . Кажется, что до тех пор, пока компания готова платить высокие цены, сверхурочную работу и давление можно отложить в сторону. выучил выучил.

Три принципа в резюме интервьюера Али в прошлый раз были очень полезными, и на этот раз общение, очевидно, было намного более гладким. Есть одно преимущество собеседования Toutiao, вы уведомите, хотите вы этого или нет, но вам придется ждать несколько дней письма с отказом и предложением, сестра отдела кадров сказала, что постарайтесь уведомить до этой пятницы, я надеюсь, все будет хорошо! !

Совет себе:

  • без ошибок! без ошибок! без ошибок!
  • Терпеливо изучайте теоретические знания о распределенных системах,Изучите больше замечательных примеров распределенных систем
  • полноКазалось бы, простые вопросы, не относитесь к ним легкомысленно, терпеливо подумайте, прежде чем писать
  • Не выбрасывайте то, что выучили.Оказывается, чтение хоть и быстрое, но трудно усваиваемое.В это время рекомендуется меньше читать и закреплять знания практикой.Особенно часть параллелизма, это базовый навык работы с распределенным, и его нужно съесть желудком.!

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

Категории