Java-задачи с подвохом: привет, собеседования!

Статья из группы Java Developer
Для студентов JavaRush задачи по программированию, Java и валидатор — лучшие друзья. Тем не менее, у каждого падавана-разработчика наступает момент, когда нужно начинать иногда сходить с проторенной дорожки, придумывать себе мини-проекты и готовиться к собеседованиям. На интервью, казалось бы, должны встречаться точно такие же практические задачи по Java, что и в курсе. В большинстве случаев так и есть, но некоторые компании любят задавать вопросы с подвохом или что-то непривычное. Чтобы не быть сбитым с толку в стрессовый момент собеседования, полезно пробовать решать такие Java-задачи самостоятельно, в домашних условиях.
Java-задачи с подвохом: привет, собеседования! - 1
В этой статье мы рассмотрим полдесятка таких хитрых задач. Рекомендуем сначала прочитать условие и попробовать решить самостоятельно. И ещё: не забывайте решать задачи по Java из курса каждый день!

Задача - 1: Создание бесконечного цикла на пустом месте

Дан блок кода. Дополните его так, чтобы цикл стал бесконечным.

class ToInfinity {
    public static void main(String[] args) {

//впишите код сюда

        for (int i = start; i <= start + 1; i++) {
             /* тут должен быть бесконечный цикл, менять ничего нельзя*/
        }
    }
}

«Ничего сложного», — скажете вы. Скорее всего, вы не раз попадали в такую историю: решая задачи по Java, вы создавали бесконечный цикл и думали, как от него избавиться. Тут же наоборот. Хитрость в том, что сам цикл и условия выхода из него менять нельзя. Есть только две итерации. Тем не менее, их вполне достаточно, чтобы создать бесконечный цикл. Похоже, что он должен работать только для двух итераций, но его можно сделать бесконечным, за счет использования переполнения. Уже догадались, как?

Решение

За счёт переполнения. Integer.MAX_VALUE — максимальное значение, которое int может хранить в Java. Если вы достигаете Integer.MAX_VALUE и инкрементируете это значение, то скатываетесь к Integer.MIN_VALUE, то есть, к минимальному значению Integer. Таким образом, для решения этой Java-задачи нам достаточно присвоить переменной start значение на 1 меньшее, чем максимальное для типа данных int. Код задачи на Java:

class ToInfinity {
    public static void main(String[] args) {
        int start = Integer.MAX_VALUE - 1;
        for (int i = start; i <= start + 1; i++) {
            //бесконечный цикл
            System.out.println(i); //убеждаемся в бесконечности цикла
        }
    }
}
Что получается? Мы начинаем со start=2147483645 (Integer.MAX_VALUE-1), на следующей итерации значение становится 2147483645, потом 2147483646, затем -2147483648, -2147483647… и так далее.

Задача - 2. Создайте комментарий, который будет выполнятся

Ну вот, приехали! С самых первых лекций мы слышали о том, что комментарии не выполняются. На то они и комментарии. Думаем, решение этой задачи для Java-программиста, даже опытного, — не всегда очевидно. Тем не менее, есть один хитрый способ, как заставить Java-машину «легально» запустить комментарий на выполнение. Чувствуете, откуда ветер дует? Попробуйте предположить!

Решение

Код решения задачи на Java:

public class ExecutableComment {
    public static void main(String[] args) {
        // комментарий ниже будет выполнен! 
        // \u000d System.out.println("выполняемый комментарий");
    }
}
Если набрать код этой задачи по джава в IDE, вот что мы получим:

выполняемый комментарий
Причина в том, что компилятор Java считывает Unicod-символ \u000d как новую строку, и читает наш код следующим образом: Расшифрованный компилятором код решения задачи на Java:

public class ExecutableComment {
    public static void main(String[] args) {
        // the line below this gives an output
        // \u000d
        System.out.println("comment executed");
    }
}

Задача - 3: создать именованный цикл

Ещё один представитель серии «практические задачи по программированию, Java в сферическом вакууме». В том смысле, что непонятно, зачем это нужно, вряд ли цикл чувствует обиду от того, что он обезличен. Ну да ладно, важно другое: язык позволяет дать циклу имя.

Решение

Примечание: кому-то такие "имена" известны как "метки", которые не рекомендуется использовать на практике. Код решения задачи по джава, демонстрирующий именованный цикл

public class NamedLoop {
    public static void main(String[] args) {
        loop1:
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (i == 3)
                    break loop1;
                System.out.println("i = " + i + " j = " + j);
            }
        }
    }
} 
Вот что будет на выходе, если запустить программу:

i = 0 j = 0
i = 0 j = 1
i = 0 j = 2
i = 0 j = 3
i = 0 j = 4
i = 1 j = 0
i = 1 j = 1
i = 1 j = 2
i = 1 j = 3
i = 1 j = 4
i = 2 j = 0
i = 2 j = 1
i = 2 j = 2
i = 2 j = 3
i = 2 j = 4
Тут также можно использовать continue для перехода к началу именованного цикла. А ещё при надобности получится использовать break (или continue) во вложенном if-else с for-циклом, чтобы разбить несколько циклов с помощью if-else. Это поможет избежать установки большого количества флагов и тестирования их в if-else чтобы понять, продолжать или выходить из внутреннего цикла.

Задача - 4. О единственном дубликате в массиве целых чисел

Задан массив (или ArrayList, как вам больше нравится) целых чисел, в котором содержатся элементы Integer от 1 до 100. В этом массиве есть один и только один продублированный элемент. Как его найти? Такие задачи для Java-программиста привычнее, чем предыдущие три. Потому что она не о знании тонкостей языка, которые почти никогда не используются, а о логике. Первый необузданный порыв — решать перебором — пропадает довольно быстро, когда включается голова или там установка «я же программист, я же умный». Плохо только, что на собеседовании, в условиях стресса, этого может и не произойти. Так что думайте сейчас, прежде, чем заглядывать в решение!

Алгоритм решения следующий:

Посчитайте сумму всех чисел от 1 до 100. Думаем, вы знаете, как это можно сделать (например, с помощью знаменитого метода Гаусса) Теперь считаете сумму элементов вашего массива или ArrayList’а. И… вычитаете первую сумму из второй. Бинго! Полученное число — и есть значение дублирующегося элемента. Код решения java-задачи для ArrayList.

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class FindDuplicate {
    private static void findDuplicate(List<Integer> elements) {
//находим сумму всех уникальных элементов списка  
        int distinctSum = elements.stream().distinct().mapToInt(e -> e).sum();
//находим сумму всех элементов списка 
        int totalSum = elements.stream().mapToInt(e -> e).sum();
        System.out.println("Элемент, который повторяется : " + (totalSum - distinctSum));
    }

    public static void main(String[] args) {
//создаем список последовательных элементов на промежутке [1..101). 
        List <Integer> elements = IntStream.range(1, 101).boxed().collect(Collectors.toList());
//устанавливаем элементу с индексом 53 значение 23          
        elements.set(53, 23);
        findDuplicate(elements);
    }
}
Другое решение

import java.util.List;
import java.util.ArrayList;

public class Duplicate {

    public int findDuplicateNumber(List<Integer> numbers) {

        int highestNumber = numbers.size() - 1;
        int total = getSum(numbers);
        int duplicate = total - (highestNumber * (highestNumber + 1) / 2);
        return duplicate;
    }

    public int getSum(List<Integer> numbers) {

        int sum = 0;
        for (int num : numbers) {
            sum = sum + num;
        }
        return sum;
    }

    public static void main(String a[]) {
        List <Integer> numbers = new ArrayList <Integer>();
        for (int i = 1; i < 100; i++) {
            numbers.add(i);
        }
        //добавляем дубликат в список
        numbers.add(25);
        Duplicate dn = new Duplicate();
        System.out.println("Элемент, который повторяется: " + dn.findDuplicateNumber(numbers));
    }
}

Задача - 5. О неединственном дубликате в массиве целых чисел

Если предыдущая задачка показалась вам слишком лёгкой, то попробуйте решить следующую: дан лист целых чисел от 1 до 100. В нём есть дубликаты (больше одного). Как найти элементы, которые встречаются больше одного раза (найти сам элемент и указать, сколько раз он встречается)?

Решение

Тут логичнее всего для решения использовать такую структуру, как HashMap, поскольку она хранит данные парами «ключ-значение». Код решения Java-задачи:

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SomeDuplicates {
    private static void findDuplicates(List<Integer> elements) {
        HashMap <Integer, Integer > duplicates = new HashMap < >();
//заполняем Map duplicates значениями по принципу:
// ключ – значение элемента, значение – сколько раз он встречается
        elements.forEach(e -> duplicates.put(e, duplicates.get(e) == null ? 1 : duplicates.get(e) + 1));
//из duplicates убираем все элементы, которые встретились не более 1 раза, 
//и сохраняем //результат в список (для удобства обработки на следующем шаге)         
        List <Map.Entry <Integer, Integer> >
        result = duplicates.entrySet().stream().filter(d -> d.getValue() > 1).collect(Collectors.toList());
//выводим результат для всех элементов в списке result          
        result.forEach(e -> System.out.println(String.format("Элемент %d  встречается %d раз", e.getKey(), e.getValue())));
    }

    public static void main(String[] args) {
        List <Integer> elements = IntStream.range(1, 101).boxed().collect(Collectors.toList());
        elements.set(97, 23);
        elements.set(27, 51);
        elements.set(99, 23);
        findDuplicates(elements);
    }
}

Заключение

Практические задачи по Java бывают очень разные, и неизвестно, какую неведомую головоломку вам решит подсунуть интервьюер. Тем не менее, любой адекватный работодатель понимает, что намного важнее умения решать задачи по Java с подвохом будет ваше умение решать реальные практические задачи, такие, которые вам встретятся во время работы. Так что решайте их как можно больше. Для этого и был создан JavaRush. При подготовке статьи использованы материалы geeksforgeeks
Что еще почитать?

Какие бывают задачи по Java

10 вопросов по абстрактным классам и интерфейсам с собеседований по Java

Кей Хорстманн и его 1500 слов о том, как стать лучшим Java-программистом

Комментарии (15)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
jam berry Уровень 0, Russian Federation
17 октября 2021
чем это не понравилось?

        public static void main(String[] args) {
		int[] ints = new int[] {1,2,3,4,5,6,7,8,9,10,1,2,3};
		ArrayList<Integer> list = new ArrayList<>();
		
		for (int i = 0; i < ints.length; i++) {
		    if (list.contains(ints[i])) System.out.println(ints[i]);
		    else list.add(ints[i]);
		}
	}
если захочется, то в несколько строк будет возвращать значения вместо их вывода. ну и можно это делать с любым типом данных
Сергей Уровень 22, Россия
25 октября 2019
То чувство, когда ты умеешь поднять микросервисы в облаке, но не умеешь написать сортировку пузырьком. Уволюсь нахрен, пойду в 11 класс к ЕГЭ готовиться по информатике. Там много таких задач.
Дмитрий Уровень 20, Новосибирск, Россия
22 августа 2019
Честно, все решения ниже мне не понравились. В моем решении я не использовал 100 элементов, но это и не важно, оно универсальное для листов разных типов и любых размерностей.

public class Tes {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>(Arrays.asList(1,2,3,4,5,2,10,5));
        System.out.println(findDuplicates(numbers));
        List<String> strings = new ArrayList<>(Arrays.asList("1", "st", "1", "5", "st", "10", "st"));
        System.out.println(findDuplicates(strings));
    }

    private static <T> Map findDuplicates(List<T> list) {
       Map<T, Integer> duplicates = new HashMap<>();
        for (T element:list) {
            if (Collections.frequency(list, element) > 1) {
               duplicates.put(element, Collections.frequency(list, element));
            }
        }
        return duplicates;
    }
}
Cepr0 Уровень 41, Одесса, Украина
18 июля 2019
Решение для 4 задачи в один проход - слолжность меньше либо равна O(n) (равна - если дубликат окажется последним в массиве). Вставка в HashSet возвращает true в случае отсутствия элемента. Выполняется за O(1) (для целых чисел).

public class FindOneDuplicateInArray {

	private static final int ARRAY_LENGTH = 100;

	private static Integer findDuplicate(final int[] array) {
		Set<Integer> holder = new HashSet<>(array.length);
		for (Integer i : array) {
			if (!holder.add(i)) return i;
		}
		return null;
	}

	public static void main(String[] args) {

		ThreadLocalRandom random = ThreadLocalRandom.current();
		IntSupplier randomInt = () -> random.nextInt(1, ARRAY_LENGTH + 1);

		int[] array = IntStream.generate(randomInt)
				.distinct()
				.limit(ARRAY_LENGTH)
				.toArray();

		int duplicate = randomInt.getAsInt();
		array[randomInt.getAsInt()] = duplicate;

		Integer result = findDuplicate(array);
		System.out.printf("Duplicate is %s%nResult is %s%n", duplicate, result);
		System.out.println("Is result correct? " + Objects.equals(result, duplicate));
	}
}
Легко адаптировать также и для решения 5 задачи.
Артем Уровень 0
24 июня 2019
4 можно вот так например решить.

        List<Integer> list = IntStream.range(1, 101).boxed().collect(Collectors.toList());
        list.set(5, 100);

        list.sort(Comparator.naturalOrder());
        for (int i = 0; i < list.size() - 1;i++) {
            if (list.get(i).equals(list.get(i+1))) {
                System.out.println(list.get(i));
                break;
            }
        }
Ярослав Уровень 40, Днепр, Украина Master
16 апреля 2018
Я бы решил 4-ю задачу через словарь, подсчитывая повторения каждого элемента, и при первой же двойке сразу можно было бы сказать, какое число дубликат. Так не нужно было бы считать суммы, а в лучшем случае выполнение программы бы закончилось еще на 2-м элементе :)
Vitaly Khan Уровень 40, Россия Master
4 апреля 2018
а разве нельзя в первой задаче в теле цикла написать строку: i--;
LJ Уровень 40, Екатеринбург
28 марта 2018
«я же программист, я же умный» (c) KISS, решения противоречат и к тому же менее оптимальны самого очевидного
Oleksandr Klymenko Уровень 13, Харьков, Украина
26 марта 2018
Задача 4. Оба решения не верны. В первом решение .mapToInt ничто иное как перебор, такое решение не оптимальное, и удивить им можно только тех кто не знаком со streams. Второе решение рассматривает частный случай где число добавляется в конец массива, на место сотого элемента, а что если вместо 24го элемента будет не 24, а 25 и весь массив приобретет вид [...22, 23, 25, 25, 26...]. Сумма такого массива будет на 1 меньше суммы чисел от 1 до 100. То есть тупик.