Алгоритмы Java сумма диапазона
Изучаю Java несколько месяцев, ранее не имел опыта программирования вообще. Как и любой другой начинающий студент, я практикуюсь на Codewars
Попалась мне задача, совсем не сложная. Есть int a и int b. Нужно найти сумму чисел в диапазоне между a и b, включая их. Инты могут быть и положительные и отрицательные. Если a==b то возвращаем a или b, неважно.
Я конечно ее решил, так сказать брут форсом. Ввел дополнительные переменные переменные, циклом сложил диапазон ... Все это заняло у меня кучу строк кода и времени.
В решениях нашел элегантный способ решить эту задачу в одну (!) строку.
У меня вопрос, это нормально для собеседования, если я решаю такие задачи "брут форсом" ? Или все айтишники решают элегантно ? Просто я не знаю, как самостоятельно находить решения в одну строку ?
П.С. В школу не отправляйте, меня уже не возьмут по причине возвраста ((
Ответы (1 шт):
Хорошие программисты математику знают и используют при необходимости.
Я вообще удивлён, что подсчёт в цикле прошёл по времени: обычно на эту задачу выставляют ограничения -109...109, а цикл на 109 операций - штука не быстрая, особенно для джавы.
Я на си чисто из любопытства (скучно было ждать конца пробного тура) пытался подсунуть цикл - это действительно прокатило, но у си и джавы производительность отличается значительно. Хотя, может такие штуки с тех пор и пооптимизировали.
Проверил. Джава, вроде, считает за .77 секунды. Си++ слишком умный и считает при компиляции, так что добавляем считывание и получаем .29 секунды - примерно в 2 раза быстрее. Но в стандартный TL в секунду всё укладывается... А вот джавовская версия с LongStream работает аж 3.65 - 4.46 секунды. Интересно, что версия с IntStream вполне успевает за .86, но может давать неверный результат.
Что касается элегантности в целом, то не все и не всегда. Да и вообще у разных программистов понятие элегантности разное. Да и критерии элегантности могут отличаться в зависимости от назначения программы.
Впрочем, не только элегантности. Во многих алгоритмических задачах при выборе алгоритма будет стоять выбор между памятью и скоростью. Лично я предпочитаю скорость. А во многих задачах ничто из этого не требуется, зато можно написать красивый код или красиво построить архитектуру (это уже не про олимпиадные задачи).
В олимпиадных задачах как правило имеет значение только асимптотика, поскольку на менее эффективное, но асимптотически верное решение закладывается запас при построении тестов и установке лимита по времени. Насколько я знаю, обычно делается выбор в пользу возможности ухитриться упихать асимптотически худшее решение (но это не будет просто сделать) против возможности случайно зарубить неэффективное асимптотически верное.
Но в твоём примере желаемая асимптотика O(1), а твоя O(res). Хотя может в пробной задаче ограничения специально понизили.