Заголовок сегодняшней итоговой записи интервью

интервью

содержание

предисловие

Недавно я участвовал в интервью с бэкенд-инженером в Toutiao, и оно было жалким, и оно просто умерло.

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

1. Найдите расстояние до самого дальнего узла бинарного дерева

Это оригинальный вопрос LeetCode,Ссылка на оригинальное название

Найдите узлы между самыми дальними узлами бинарного дерева. Сначала резюмируем несколько правил:

  1. Диаметр дерева либо полностью находится в его левом поддереве, либо полностью находится в его правом поддереве, либо проходит через корневой узел.
  2. Диаметр дерева = Возьмите каждый узел дерева в качестве корневого узла и найдите максимальный диаметр прохождения через корневой узел, а максимальное значение всех узлов - это диаметр дерева.
  3. Чтобы найти диаметр, проходящий через корневой узел, его можно разложить на: найти самый глубокий лист левого поддерева + самый глубокий лист правого поддерева.

Итак, мы делаем:

  1. Рекурсивно найти каждый узелПередача диаметра корневого узла (найти самый глубокий лист левого поддерева текущего узла и самый глубокий лист правого поддерева), принять его максимальное значение.
  2. Поиск самого глубокого листа узла равен большему из самого глубокого листа его левого поддерева + 1 и самого глубокого листа правого поддерева + 1.
  3. При нахождении самого глубокого листа мы фактически находим диаметр текущего узла (самый глубокий лист слева + самый глубокий лист справа + 2), во избежание повторных вычислений, при рекурсивном поиске самого глубокого листа диаметр тоже записывается)

код показывает, как показано ниже:

   public int diameterOfBinaryTree(TreeNode root) {
       AtomicReference<Integer> ret = new AtomicReference<>(0);
        find(root, ret);
       return ret.get();
   }

   private int find(TreeNode node, AtomicReference<Integer> result) {
       if (node == null) return 0;
       int left = 0, right = 0;
       if (node.left != null) left = find(node.left,result) + 1;
       if (node.right != null) right = find(node.right,result) + 1;
       int tmp = Math.max(result.get(), left + right);
       result.set(tmp);
       return Math.max(left, right);
   }

Код очень прост, он рекурсивно находит самый дальний лист левого поддерева и самый дальний лист правого поддерева, Затем в процессе вычисления当前节点的直径Сохраните его как альтернативу и, наконец, найдите максимальный диаметр.

2. Упаковка и распаковка Java

Java добавила механизм автоматической упаковки и распаковки в 1.5.В общем, это в основном автоматическое преобразование между базовым типом и соответствующим типом упаковки.

Как в коде ниже:

public class BoxTest {
    public static void main(String [] args){
        Integer a = 10; // 装箱
        int b = a; // 拆箱
    }
}

Декомпилируем код после компиляции, можете посмотреть

2019-10-24-14-32-50

Очевидно в коде#2 ,#3В упаковке и без коробки.

Целые называются соответственноvalueOfМетоды иintValueметод.

3. Когда пользовательский поток будет приостановлен в процессе сбора сборщиком мусора CMS?

Здесь не объясняются все сборщики мусора, заинтересованные друзья могут двигатьсяОбласть данных JVM и сборка мусора.

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

2019-08-10-21-19-28

Следовательно, по-прежнему необходимо приостанавливать пользовательский поток на двух этапах начальной маркировки и перемаркировки.

4. Почему ConcurrentHashMap не нужно блокировать в процессе чтения?

ПроверятьConcurrentHashMapИсходный код можно найти, определение узла Node:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
}

Как видите, в нем определены несколько свойств, а именно:

  1. Окончательное измененное хеш-значение нельзя изменить снова после инициализации.
  2. Окончательный измененный ключ нельзя изменить снова после инициализации.
  3. изменчивое декорированное значение
  4. изменчивый декорированный указатель следующего узла

существуетget(Ojbect)во время вызова метода.

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    //获取hash值
    int h = spread(key.hashCode());
    //通过tabat获取hash桶, tabAt是一个线程安全的操作, 有UnSafe来保证的.
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        //如果该hash桶的第一个节点就是查找结果,则返回
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        //第一个节点是树的根节点,按照树的方式进行遍历查找
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        //第一个节点是链表的根节点,按照链表的方式遍历查找
        while ((e = e.next) != null) {
            if (e.hash == h &&
                ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

В этом процессе

  1. Получите корневой узел хеш-ковша черезtabAtдля работы, потокобезопасный.
  2. При обходе используется атрибут next узла, поскольку он модифицируется с помощью volatile, он виден между потоками, и возникают проблемы параллелизма.
  3. Прочитайте изменчивое свойство val узла при возврате.

такgetОбъект можно получить корректно без блокировки в процессе.

5. В чем разница между перефразировкой словаря Redis и перефразировкой, такой как hashmap в JDK?

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

  1. При повторном хэшировании хэш-карты временно создается другая таблица. Redis постоянно сохраняет ссылку на две таблицы. Достаточное пространство выделяется только тогда, когда требуется повторное хеширование.
  2. Повторное хеширование Hashmap — это одноразовое централизованное завершение процесса повторного хеширования, а Redis — это прогрессивное хеширование.

Процесс повторного хеширования hashmap должен быть понятен всем, поэтому давайте поговорим о прогрессивном хешировании redis.

Прежде всего, rehash — это повторное хеширование всех данных в исходной таблице и сохранение их в новой таблице для расширения.

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

Поэтому Redis реализует прогрессивное хеширование, процесс выглядит следующим образом:

  1. Если текущие данные находятся в ht[0], то сначала выделите достаточно места для ht[1].
  2. В словаре поддерживается переменная, rehashindex = 0. Она используется для указания хода выполнения текущего перефразирования.
  3. Во время повторного хеширования каждый раз, когда словарь добавляется, удаляется, изменяется и выполняется поиск, после завершения фактической операции будет выполняться операция повторного хеширования, и ht[0] будет помещен вrehashindexПерефразируйте значение в позиции в ht[1].Увеличьте rehashindex на единицу.
  4. При непрерывном выполнении все значения исходного ht[0] всегда будут перехэшироваться, и на этом процесс перехеширования завершится.

В описанном выше процессе не упомянуты две проблемы:

  1. Что, если сервер очень свободен?Если в течение нескольких часов не будет поступать запросов, не будет ли пустой тратой памяти хранить две таблицы одновременно?

Решение таково: в функцию времени redis также добавлена ​​операция помощи перехешированию, так что если сервер простаивает, перехеширование будет выполнено быстрее.

  1. Каким образом хэш-таблица предоставляет услуги внешнему миру в период обслуживания двух таблиц?

Решение: для операции добавления добавьте ее непосредственно в ht[1], чтобы это могло гарантировать, что количество ht[0] будет только уменьшаться, а не увеличиваться, чтобы гарантировать, что процесс перефразирования может быть завершен. изменять, запрашивать и другие операции будут в Выполнить это на ht[0], Если результат не получен, он перейдет к ht[1] и выполнит его снова.

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

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

Справочная статья

Проектирование и реализация Redis (второе издание)

Заканчивать.



ChangeLog

2019-05-19 Завершено

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

Добро пожаловать на перепечатку, пожалуйста, подпишите и сохраните исходную ссылку.

Контактный адрес электронной почты: huyanshi2580@gmail.com

Дополнительные заметки об обучении см. в личном блоге или подпишитесь на общедоступную учетную запись WeChat ------>Хуян тен

Категории