Шпаргалка по Java для алгоритмического собеседования

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

Также смотрите реализацию на Java стандартных алгоритмов: Шпаргалка по основным алгоритмам для алгоритмического собеседования

Строки

//Посимвольные циклы
for (char c : str.toCharArray()) {
    ...
}

for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    ...
}

//Массив символов в строку
char arr[] = ...
String str = new String(arr);
String str = String.valueOf(arr);

//Посимвольная трансформация строки
char arr[] = new char[str.length()];
for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    arr[i] = //Какое-то преобразование символа c
}
String result = new String(arr);

//Разбиение строки
String arr[] = str.split(separator);

//Соединить коллекцию строк в одну
String str = String.join(separator, arrayOfStrings);

//Конструирование новой строки
StringBuilder sb = new StringBuilder();
for (....) {
    sb.append(...);
    ...
}
sb.toString();
sb.reverse().toString();//В обратном порядке

//Вспомогательные методы для работы с char
Character.isLetter(c);
Character.isDigit(c);
Character.isLetterOrDigit(c);
Character.isLowerCase(c);
Character.isUpperCase(c);
Character.toLowerCase(c);
Character.toUpperCase(c);
Character.isAlphabetic(c);

//Преобразование чисел, boolean в строку
String str = String.valueOf(num);

Сортировка

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

//Сортировка массива
Arrays.sort(arr);
Arrays.sort(arr, comparator);

//Сортировка коллекций
Collections.sort(collection);
Collections.sort(collection, comparator);

Массивы и числа

//Объявления
int arr[] = new int[100];
int arr[][] = new int[100][100];
int arr[] = new int[list.size()];
int arr[] = {1, 2, 3, 4, 5};
int arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

//Циклы
for (int i = 0; i < arr.length; i++) {
    int num = arr[i];
    ...
}

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr[i].length; j++) {
        int num = arr[i][j];
        ...
    }
}

//Преобразования  строки в число
Integer.parseInt(str);
Float.parseFloat(str);
Double.parseDouble(str);

//Создать массив из двух элементов (пара)
int val1 = ..
int val2 = ...
int pair[] = new int[] {val1, val2};

//Хранение пары чисел в коллекции
Stack<Integer[]> stack = new Stack<>();
stack.push(new Integer[] {val1, val2});
Integer top[] = stack.pop();
... = top[0];
... = top[1];

Стек

//Объявление
Stack<Integer> stack = new Stack<>();
Stack<String> stack = new Stack<>();
...
//Использование
stack.push(num); //Поместить элемент
stack.pop(); //Достать из вершины
stack.isEmpty(); //Проверить пуст или нет
stack.peek(); //Взять элемент из вершины без удаления

//Цикл
while (!stack.isEmpty()) {
    String top = stack.pop();
    ...
}

Очередь

//Объявление
//В ArrayDeque нельзя добвлять null, а в LinkedList можно
Queue<String> queue = new ArrayDeque<>();
Queue<String> queue = new LinkedList<>();

//Использование

//Добавление в хвост
queue.add(str);
queue.offer(str);
queue.addAll(list);

//Получение из головы
queue.poll();
queue.remove();//Бросает исключение, если очередь пустая
queue.peek();//Получает элемент из головы очереди без удаления

queue.isEmpty(); //Проверить пустая очередь или нет

//Цикл
while (!queue.isEmpty()) {
    String head = queue.poll();
    ...
}

Хэш-таблица

//Объявление
Map<String, String> map = new HashMap<>();

//Использование
map.put(key, value); //Поместить в хэш-таблицу
map.get(key); //Получить значение по ключу
map.containsKey(key); //Проверить наличие ключа
map.isEmpty();// Проверить пустая или нет
map.remove(key);//Удалить по ключу
map.getOrDefault(key, defaultValue);//Получить по ключу, если такого ключа нет, то вернуть defaultValue

//Цикл по элементам
for (String key : map.keySet()) {
    String value = map.get(key);
    ....
}
//Цикл только по значениям
for (String value : map.values()) {
    ....
}

Хэш-сет

//Объявление
Set<String> set = new HashSet<>();

//Использование
set.add(str); //Добавить
set.contains(key); //Проверить наличие
set.isEmpty(); //Проверить пуст или нет
set.remove(key);//Удалить
set.addAll(collection);
set.removeAll(collection);
set.retainAll(collection); //Найти пересечение

//Цикл
for (String val : set) {
    ....
}

LinkedLists

Для односвязных списков предполагайте, что есть некий класс Node с полями next, val. Для двусвязных списков, что есть еще ссылка на предыдущий элемент prev.

Node node = ...
node.next;//Получить следующий
node.val;//Получить значение

//Для двусвязного
node.prev;//Получить ссылку на предыдущий

//Цикл
Node current = head;
while (current != null) {
    ....
    current = current.next;
} 

Куча/PriorityQueue

//Объявления
PriorityQueue<String> queue = new PriorityQueue<>();
PriorityQueue<String> queue = new PriorityQueue<>(comparator);

//Использование
queue.add(str);
queue.size();
queue.remove();//удалить из головы очереди

//Хранение в очереди не более maxSize элементов
for (...) {
    queue.add(el);
    if (queue.size() > maxSize) {
        queue.remove();
    }
}

Бинарные Деревья

Предполагайте, что уже определен некий класс с полями left, right, val.

//Использование
Node node...
node.left;// Получить левого ребенка
node.right;//Получить правого ребенка
node.val;//Получить ключ/значение

//Иногда может быть доступно поле parent, уточняйте у интервьюера
node.parent;// Получить родительскую вершину

Trie/префиксные деревья

Можно предполагать что есть два класса Trie и TrieNode

Trie trie = ...
trie.contains(str);//Проверить, содержит ли префиксное дерево строку
trie.addWord(str);//Добавить строку в префиксное дерево

TrieNode node = ...
node.getChild(c); //получить дочернюю вершину по символу
node.temninates(); //Является ли вершина терминальной
node.getChar(); // Получить символ, хранящийся в данной вершине