PriorityQueue с переопределенным Comparator, TreeMap, LinkedHashMap и т. Д.

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

Почему именно Ява?

Java - широко известный язык, который безопасно использовать во время собеседований в большинстве компаний, и более вероятно, что интервьюер знаком с этим языком. Более того, некоторые из лучших книг по подготовке к собеседованию по кодированию, такие как Cracking The Coding Interview или Programing Interview Exposed, написаны на Java.

Без лишних слов, давайте начнем с HashMap.

Хеш-карта

HashMap обеспечивает O(1) сложность поиска и вставки. Запись не отсортирована. Чтобы создать хэш-карту с целым числом в качестве ключевых типов данных и String в качестве типов данных значений:

Map<Integer, String> map = new HashMap<>();

Чтобы проверить, существует ли ключ:

map.containsKey(key); // returns boolean

Чтобы получить значение на основе ключа:

map.get(key);

Чтобы добавить пару ключ и значение:

map.put(key, value);

Чтобы перебрать пару ключей и значений:

for (Map.Entry<Integer, String> entry: map.entrySet()) {
  int key = entry.getKey();
  String value = entry.getValue();
}

TreeMap

TreeMap - это еще одна реализация Map interface, поэтому API похож на HashMap, за исключением инициализации, где мы объявляем тип объекта как TreeMap:

Map<String, Integer> = new TreeMap<>();

У него есть несколько интересных функций:

  • Его реализация заимствована из красно-черного дерева.
  • Он всегда упорядочивается по ключу, что делает его отсортированной картой.
  • Можно передать уникальный компаратор в качестве аргумента во время инициализации, чтобы сделать порядок на основе переданного настраиваемого компаратора.
  • Это гарантирует O(log n) сложность операций поиска и удаления

TreeMap - редкая особенность языка программирования. Насколько я знаю, это есть только в C ++ и Java.

LinkedHashMap

LinkedHashMap - еще одна реализация интерфейса карты. Его уникальные особенности:

  • Ключи упорядочены в соответствии с порядком их вставки.
  • Он предлагает O(1) поиск и вставку.

Короче говоря, он такой же, как HashMap, но с ключами, упорядоченными в соответствии с порядком их вставки. Это полезно, когда мы внедряем карту на основе наименее недавнего использования (LRU).

LinkedList

Java также предоставила свою реализацию структуры данных двусвязного списка через LinkedList API. Это реализация интерфейса List, как и ArrayList, поэтому его объявление выглядело так:

List<String> list = new LinkedList();

LinkedList имеет O(n) временную сложность для произвольных индексов добавления / удаления, но O(1) для операций в конце / начале списка. Более того, он также быстрее поддается манипуляциям по сравнению с ArrayList. Манипуляции с ArrayList медленны, потому что он использует массив внутри. Если какой-либо элемент удаляется из массива, все биты сдвигаются в памяти.

Остальная часть его API для доступа / удаления элемента аналогична API ArrayList. То есть для доступа к элементу:

int number = list.get(index);

Чтобы добавить значение в список:

// add value at certain index
list.set(index, value);
// add value at the end of the list
list.add(value);

Проверить, пуст ли список:

list.isEmpty() // Returns boolean

Чтобы перебрать весь элемент в списке

for (Integer i: list) { ... }

HashSet

Set - это структура данных для хранения коллекций без дубликатов. Методы add, remove и contains имеют постоянную временную сложность O (1). Чтобы создать новый набор целых чисел:

Set<Integer> set = new HashSet();

Прочие операции с наборами:

// Check if set contains value
set.contains(value);
// Add value in set
set.add(value);
// Remove value from set
set.remove(value);

TreeSet

TreeSet - это еще одна реализация Set API, поэтому повторяющиеся значения не допускаются. Некоторые из его интересных особенностей:

  • Объекты внутри упорядочиваются на основе его ключей, а не порядка вставки.
  • TreeSet - это в основном реализация самобалансирующегося двоичного дерева поиска, такого как Красно-Черное дерево. Поэтому такие операции, как добавление, удаление и поиск, занимают O(log n) время.
  • TreeSet служит отличным выбором для хранения больших объемов отсортированной информации, к которой требуется быстрый доступ из-за более быстрого доступа и времени поиска.

Очередь

Чтобы инициализировать очередь Obj:

Queue<Obj> q = new LinkedList<>();

Другие операции с очередью:

// Add element
q.add(element);
// Pop off the earliest element added
Obj element = q.poll();
// See the earliest element added
Obj element = q.peek();
// Check if queue is empty
q.isEmpty();

Приоритетная очередь

Чтобы создать собственный компаратор для очереди приоритетов:

class ResidentComparator implements Comparator<Resident>{
  public int compare(Resident r1, Resident r2) {
    if (r1.year < r2.year) return 1; 
    else if (r1.year > r2.year) return -1;
    return 0;
  }
}

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

PriorityQueue<Resident> pq = new PriorityQueue<Resident>(5, new ResidentComparator());

Остальные API для PriorityQueue, то есть для просмотра / извлечения значения из очереди, аналогичны API для Queue.

Куча

Чтобы инициализировать стек Obj:

Stack<Obj> stack = new Stack<>();

Чтобы увидеть верх стопки:

stack.peek();

Чтобы выдвинуть верх стопки:

stack.pop();

Чтобы добавить элемент в стек:

stack.push(element);

Проверьте, пуст ли стек:

stack.isEmpty();

Строка и символ

Строка заключена в двойные кавычки, а символ - в одинарные.

Чтобы получить символ в строке, находящейся в определенном индексе:

string.charAt(index);

Чтобы получить длину строки:

string.length();

Чтобы проверить, является ли символ буквенно-цифровым / пробелом / цифрой:

// Check if character is alphanumeric
Character.isLetterOrDigit(character);
// Check if character is whitespace
Character.isWhitespace(character);
// Check if character is digit
Character.isDigit();

Чтобы получить символ нижнего регистра из символа:

Character.toLowerCase(character);

Для динамического построения строки рекомендуется использовать StringBuilder следующим образом. Сначала мы объявляем новый StringBuilder.

// Contains Empty String
StringBuilder strBuilder = new StringBuilder();
// Contains someString during initialization
StringBuilder strBuilder = new StringBuilder(someString);

Чтобы добавить символ к объекту StringBuilder:

strBuilder.append(char);

После построения строки преобразуйте StringBuilder в String:

strBuilder.toString();

Битовые манипуляции и математика

Чтобы найти максимальное / минимальное значение между двумя значениями:

// Instead of:
int max = a;
if (b > a)  max = b;
//Do it this way
int max = Math.max(a,b);
int min = Math.min(a,b);

Чтобы получить минимальное / максимальное значение целого числа без ввода чисел:

int minInt = Integer.MIN_VALUE;
int maxInt = Integer.MAX_VALUE;

Чтобы выполнить битовые операции с числом:

int x = 1 ^ 0              // XOR
int a = 1 & 0              // AND
int b = ~1                 // NOT
int c = 1 | 0              // OR
int y = 1111 >> 2          // RIGHT SHIFT
int z = 1111 << 2          // LEFT SHIFT

Множество

Синтаксис массива [] используется, когда мы знаем во время инициализации длину необходимого массива. С другой стороны, List используется, когда номер массива может динамически изменяться.

Одна функция, которую я нашел удобной в массиве, но я все время забываю, - это создать массив, в котором все элементы внутри известны во время создания:

int[] intArray = new int[]{ 1,2,3,4,5,6,7,8,9,10 };

Всего наилучшего для интервью! 🎊 🎊