На алгоритмическом собеседовании код нужно писать на реальном языке программирования, близким к тому, чтобы быть компилируемым. При этом нельзя пользоваться гуглом и подсказками. Поэтому некоторые стандартные конструкции языка программирования, стандартные структуры данных и библиотечные функции нужно знать наизусть.
Также смотрите реализацию на 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(); // Получить символ, хранящийся в данной вершине
Top comments (0)