|
Note
|
Задачи, которые предлагают различные компании в качестве практических задач в процессе проведения технического интервью (т.е. вы их решаете и при этом шарите свой экран). |
1. Max value in Tree
1.1. Описание
-
Создать собственное дерево
-
Найти в этом дереве наибольший элемент
1.2. Решение
class Node {
public Node left;
public Node right;
public int val;
public Node(int val) {
this(val, null, null);
}
public Node(int val, Node left, Node right) {
this.val = val;
this.left = left;
this.right = right;
}
}class Main {
public static void main(String[] args) {
Node tree = new Node(
5,
new Node(
7,
new Node(4),
new Node(3)
),
new Node(
10,
new Node(2),
new Node(13)
)
);
System.out.println(max(tree));
}
public static int max(Node tree) {
int max = tree.val;
if (tree.left != null) {
int leftMax = max(tree.left);
if (leftMax > max) {
max = leftMax;
}
}
if (tree.right != null) {
int rightMax = max(tree.right);
if (rightMax > max) {
max = rightMax;
}
}
return max;
}
}2. Conway’s Game of Life
2.1. Описание
-
Дан двумерный массив, элементами которого являются
0и1 -
Изменить элементы массива согласно правилам Conway’s Game of Life
|
Note
|
Описание самой игра можно найти здесь: Conway’s Game of Life |
2.2. Решение
public class ConwayGame {
public static void main(String[] args) {
int[][] game = {
{
0, 0, 0, 0, 0
},
{
0, 0, 1, 0, 0
},
{
0, 0, 0, 1, 0
},
{
0, 1, 1, 1, 0
},
{
0, 0, 0, 0, 0
}
};
int[][] update = update(game);
print(update);
}
private static void print(int[][] update) {
for (int[] internal : update) {
for (int cell : internal) {
System.out.print(cell);
}
System.out.println();
}
}
public static int[][] update(int[][] input) {
int n = input.length;
int m = input[0].length;
int[][] result = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[i][j] = input[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (checkRevert(i, j, input)) {
result[i][j] = (input[i][j] == 1) ? 0 : 1;
}
}
}
return result;
}
private static boolean checkRevert(int i, int j, int[][] input) {
int counter = 0;
if ((i >= 1 && j >= 1)
&& input[i - 1][j - 1] == 1) {
counter++;
}
if ((j >= 1)
&& input[i][j - 1] == 1
) {
counter++;
}
if ((i <= input.length - 2 && j >= 1)
&& input[i + 1][j - 1] == 1
) {
counter++;
}
if (i <= input.length - 2
&& input[i + 1][j] == 1
) {
counter++;
}
if ((i <= input.length - 2 && j <= input[0].length - 2)
&& input[i + 1][j + 1] == 1
) {
counter++;
}
if (j <= input[0].length - 2 && input[i][j + 1] == 1
) {
counter++;
}
if (i >= 1 && j <= input[0].length - 2
&& input[i - 1][j + 1] == 1
) {
counter++;
}
if (i >= 1 && input[i - 1][j] == 1
) {
counter++;
}
return input[i][j] == 1 && (counter < 2 || counter > 3)
|| (counter == 3 && input[i][j] == 0);
}
}3. Массив с дубликатами
3.1. Описание
Дан массив чисел с возможными дубликатами [2, 1, 1, 2, 3, 5]. Нужно вывести только уникальные (здесь могут быть разные формулировки - только уникальные, количество уникальных и т.д.).
3.2. Решение
public class Program {
public static void main(String[] args) {
int[] a = {2, 1, 1, 2, 3, 5};
// Посчитать сколько раз каждое значение встречается в массиве
Map<Integer, Integer> counter = new HashMap<>();
for (int x : a) {
int newValue = counter.getOrDefault(x, 0) + 1;
counter.put(x, newValue);
}
// Вывести числа
counter.entrySet().stream()
.filter(entry -> entry.getValue() == 1)
.forEach(System.out::println);
}
}4. Swap значений в переменных (без дополнительной переменной)
4.1. Описание
Даны две переменные a и b. Без ввода дополнительной переменной поменять их значения местами
4.2. Решение
public class Program {
public static void main(String[] args) {
int a = 1;
int b = 6;
a = a + b;
b = a - b;
a = a - b;
System.out.println(a);
System.out.println(b);
}
}5. Полиндром по индексу
5.1. Описание
Дана строка и индекс буквы в этой строке. Метод должен возвращать true/false. Цель метода проверить, можно ли разделить данную строку по индексу так, чтобы текст до индекса и после индекса были зеркальными. Например racecar и индекс 3 должны вернуть true, так как индекс 3 делит текс на rac и car.
5.2. Решение
public class Program {
private static boolean isMirrorText(String text, int index) {
if ((text.length() - 1) / 2 == index) {
return text.equals(reverse(text));
}
return false;
}
// way 1 for reverse
private static String reverse(String text) {
char[] array = text.toCharArray();
return IntStream.rangeClosed(1, array.length)
.mapToObj(i -> array[array.length - i])
.map(String::valueOf)
.collect(Collectors.joining());
}
// way 2 for reverse
private static String reverse2(String text) {
return new StringBuilder(text).reverse().toString();
}
}6. Обход магазина
6.1. Описание
После работы ваш коллега, стажер Павел, решил зайти в магазин. Как и вы, Павел — разработчик, поэтому каждое свое действие он выполняет по алгоритму в строгой последовательности.
Супермаркет для Павла — прямая с полками. На каждой полке стоят товары одной категории, а каждая полка помечена какой-то строчной буквой латинского алфавита (a, …, z)(a,…,z), т.е. весь супермаркет можно представлять как строку ss.
Павел хочет взять по одному товару с каждой полки в каком-то порядке. Для этого он делает две операции:
-
Взять товар с текущей полки и положить в корзину, если он этого не сделал ранее.
-
Передвинуться к следующей полке. Если он стоял у последней полки, он возвращается к первой.
Павел любит порядок и хочет складывать товары в отсортированном порядке, а именно сначала он хочет взять по одному товару с полок с буквой aa, если они есть, затем — с буквой bb и так далее до zz. У Павла был тяжелый день, он хочет домой, поэтому планирует закончить с покупками как можно быстрее. Для этого он решил брать товары не со всех полок, а только с какого-то подотрезка, т.е. рассматривать все полки с l-й по r-ю.
Пожалуйста, помогите Павлу быстрее попасть домой и посчитайте, сколько передвижений, т.е. операций второго типа, ему нужно будет сделать.
6.1.1. Формат входных данных
В первой строке содержится строка ss (1 ≤ ∣s∣ ≤ 10^5)(1 ≤ ∣s∣ ≤ 10^5), состоящая из строчных букв латинского алфавита — план супермаркета.
Во второй строке содержится число qq (1 ≤ |s| ≤ 10^5)(1 ≤ ∣s∣ ≤ 10^5) — количество рассматриваемых Павлом подотрезков.
В следующих qq строках содержатся границы подотрезка — два целых числа l_il i r_ir
i
(1 ≤ i ≤ q, 1 ≤ l_i ≤ r_i ≤ |s|)(1 ≤ i ≤ q ,1 ≤ l, i ≤ r, i ≤ ∣s∣).
hello 3 1 5 1 2 2 5
6.1.2. Формат выходных данных
Выведите qq строк, содержащих одно целое число — количество операций второго типа, которые необходимо выполнить для этого подотрезка.
|
Note
|
Для первого подотрезка из входных данных нужно сделать 9 перемещений: 1 шаг с первого символа подотрезка до буквы e, 4 шага до буквы h, 2 шага до первой ll, 1 шаг до второй l, 1 шаг до буквы o.
|
9 2 3