Привет!
На днях я наткнулся на одну занимательную задачку "Закрутить числа". А сегодня как раз выдался свободный день и я решил совместить приятное с полезным. Посидеть дома, под прохладой кондиционера (на улице +30!) и немного покодить.
Задача достаточно интересная, хотя для кого-то и не новая. Но речь пойдет даже не о самом алгоритме или способе его реализации, а о проблеме, на которую меня натолкнул один знакомый тестировщик.
Ну и про фейсбук, конечно! :) Ныряй под кат, поехали!
тестированием на уровне как я, думаю сразу вспоминается про классы эквивалентности и как погонять тесты по граничным значениям. С нижней границей всё ясно M = 0; N = 0, капитан очевидность какбэ намекает, что отрицательный размер матрицы даст нам исключение. А какие значения надо подать, чтобы протестировать верхние граничные значения? И есть ли вообще верхняя граница у массива?
Ну а пока знатоки обсуждают, а те, кто знает или думает, что знает - смеются с глупых вопросов, можем порассуждать на общие темы.
Вообще, я считаю, что подобные задачи (это я про "Закрутить спираль") не для Java. Они, в основном, решаются функционально, один класс да две-три функции в нём. Статические переменные, статические функции. Конечно, можно и ООП сюда запихнуть, было бы желание... Это больше бы подошло, как мне кажется, для Haskell или Python. Там течет размеренная жизнь и нет такого упора на ООП, как в Java. Но, в моём случае, приходилось руководствоваться принципом "на чём умею - на том и пишу".
Я признаюсь честно, я его решил самым быстрым и простым для меня способом. Правильно, через циклы. Потом подумал и решил ещё раз. И опять через циклы. И тут мне стало интересно какой выигрыш по времени у меня в разных реализациях? Откуда я знаю, что вторая реализация лучше, если при размерах матрицы 10х8, алгоритм отрабатывает за 1мс, в обоих случаях. Увеличить размер матрицы? Сказано - сделано. N = 7000 и M = 7000. Главное, не забыть закоментить метод print(). Иначе начнется кромешный ад! :D
Да, действительно есть выигрыш по времени, не очень большой, но так я ещё и не оптимизировал ничего! Тем более можно проверить на ещё больших значениях... Следующим шагом было (так как я очень ленив) просто дописать два нолика и получить соответственно N = 70000 и M = 70000. Догадываетесь что было дальше? А дальше ответ на вопрос, который я задавал в начале. Нет, не про facebook. ))
Возвращаемся к вопросу о верхней границе размера матрицы.
Итак, какой ответ правильный? Какие граничные значения будут у этого массива?
первый вариант ответа:
(2^31 - 1) == (2147483647). Например, стороны матрицы могут быть примерно 46341 х 46340, если мы хотим примерно одинаковые стороны. (Корень из 2^31-1 = 46340,95). Ну или 2147483647 х 1. Принцип, думаю понятен. То есть когда общее количество элементов в int[][] достигнет Integer.MAX_VALUE будет выброшено исключение
ArrayIndexOutOfBoundsException: -2147483648
второй вариант ответа:
Максимальное количество элементов в массиве будет: (Integer.MAX_VALUE - 8) или 2147483639. Когда общее количество элементов в int[][] превысит это значение, будет выброшено исключение
java.lang.OutOfMemoryError: Requested array size exceeds VM limit
третий вариант ответа:
Ограничен размером в 2Гб оперативной памяти. Каждый элемент Integer занимает 8 байт. Когда общий размер превышает 2 Гб - будет выброшено исключение
java.lang.OutOfMemoryError: GC overhead limit exceeded
четвертый вариант ответа:
Ограничен размером памяти в куче, выделяемой с помощью параметра -Xmx. Когда порождается множество объектов, в данном случае int, а сборщик мусора, по каким-то причинам не справляется, то при превышении лимита будет выброшено исключение
java.lang.OutOfMemoryError: Java heap space
пятый вариант:
Здесь нет правильного ответа. Зато я напишу свой в комментариях. ;-)
Думаю, будет интересно. Особенно, если ещё и попробовать решить задачу :)
Ну и про фейсбук.
Когда я лазил по интернету, в поисках того, "как это сделали другие", я наткнулся на статейку на хабре как раз про мой алгоритм (можно почитать, решение под спойлером) в которой похожее задание было отборочным к собеседованию на фейсбук. (О_о)
В двух словах: лекция от FB, на которой присутствовало около 150 человек и предложили сделать это задание, как отбор на собеседование. Ну и конечно же доблестный хабровчанин не подкачал. ))
Что меня поразило первое - это то что мой алгоритм (не оформление!!! :D ) был практически такой же, как у автора. Не вылизан, а так норм! Впрочем, сам автор был удивлен не менее.
А второе, и самое главное, что меня поразило, это то что из 150 человек, прислали решение 3(три)!! При этом у одного из них, решение ещё и не скомпилировалось. ))))
Почему не отправили остальные? Я почему-то думаю, что причина проста. Вредная мысль "Зачем что-то делать, если таких же, как я, ещё 100 человек будет? Только время зря потрачу."
И так подумал каждый(!) А возможно, счастье было так близко :D Конечно, попасть на собеседование - это чуть менее, чем ничего в перспективе дальнейшего трудоустройства. Но даже, если ты его в итоге завалил:
- это опыт, сложно пройти собеседование, если не знаешь что тебя там может ждать;
- многие не могут даже попасть на собеседование, решив легкую задачку, поэтому уже какой-никакой а уровень;
- обычно, это достаточно интересно и весело :D
Не стоит бояться туда идти и лениться попробовать. Давайте не бояться! Решать задачи на JavaRush очень тепло и комфортно, да и помощь можно у сообщества запросить. Или подсмотреть. Но может уже стоит попробовать покинуть зону комфорта, хоть на пару дней (или недельку), ради того, чтобы "прощупать почву". Пусть не фейсбук, тем более, он не является каким-то эталоном или мегацелью. Есть множество других не менее классных компаний с отличными людьми и интересными задачами. А вдруг ты как раз тот, который в нужный момент не побоялся и не поленился. А вдруг нужный момент сейчас? А вдруг... В любом случае, можно и помечтать!?
Удачи!">
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ