Forem

faangmaster
faangmaster

Posted on • Edited on

8

Шпаргалка по 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);
Enter fullscreen mode Exit fullscreen mode

Сортировка

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

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

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

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

//Объявления
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];
Enter fullscreen mode Exit fullscreen mode

Стек

//Объявление
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();
    ...
}
Enter fullscreen mode Exit fullscreen mode

Очередь

//Объявление
//В 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();
    ...
}
Enter fullscreen mode Exit fullscreen mode

Хэш-таблица

//Объявление
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()) {
    ....
}
Enter fullscreen mode Exit fullscreen mode

Хэш-сет

//Объявление
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) {
    ....
}
Enter fullscreen mode Exit fullscreen mode

LinkedLists

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

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

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

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

Куча/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();
    }
}
Enter fullscreen mode Exit fullscreen mode

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

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

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

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

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

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

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

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

Image of Datadog

The Essential Toolkit for Front-end Developers

Take a user-centric approach to front-end monitoring that evolves alongside increasingly complex frameworks and single-page applications.

Get The Kit

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more