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 };
Всего наилучшего для интервью! 🎊 🎊