| Главная » Статьи » Java » Java Ranger Basic |
День 12/21
| Алгоритмы - Вопросы на собеседовании Алгоритмы сортировки. Нужно назвать штук 5 и примерно рассказать, как они работают. Рассказать, на каких данных он работает лучше всего, а на каких хуже всего. Хэш-таблицы. Два разных варианта реализации хэш-таблиц – с открытой адресацией и закрытой адресацией. В Java в классе java.util.HashMap реализован только один из двух. Вопрос – какой, почему он, какой второй, на каких задачах одна хэш-таблица лучше первой и наоборот. Вопросы по деревьям: B-Tree, RB Trees. 10 мелких задач по теории алгоритмов: инвертирование массива, бинарный поиск (объяснить, как работает и попытаться ответить на вопрос: если у нас в массиве 572 миллиона элементов, сколько сделает сравнений бинарный поиск? – нужно примерно посчитать двоичный логарифм от 572 миллиона, это будет примерно 29). В реальности ни от кого не требуется, чтобы он писал алгоритмы по бумажке. Однако нужно четкое понимание человеком, какие бывают алгоритмы, какие бывают структуры данных. Еще один очень популярный алгоритм, который спрашивают на собеседовании – слияние сортированных массивов. Представим, что у нас уже есть два отсортированных массива: [0, 0, 10, 15, 17] и [1, 2, 3, 3, 5, 7]. Нам нужно получить третий массив суммарной длины, в котором будут отсортированы все элементы. Плохое решение: мы заводим новый массив суммарной длины, с помощью System.arraycopy копируем первый массив в начало, а второй в конец суммарного массива. И применяем метод сортировки к полученному массиву. Все будет работать, однако работа будет не оптимально быстрой. Ведь в нашем массиве какая-то часть работы уже выполнена, а мы ее полностью игнорируем. Нам нужен какой-то алгоритм, который будет учитывать, что оба этих массива уже отсортированы. Это часть алгоритма сортировки слиянием (merge sort). Сортировка слиянием работает следующим образом. Мы берем массив, делим его надвое, потом отдельно сортируем правую часть и отдельно левую. А потом из двух отсортированных половин нам нужно собрать готовый массив. Этот алгоритм работает рекурсивно. Как сливать два отсортированных массива в один отсортированный. Очевидно, что в результирующем массиве первым элементом будет идти либо первый элемент первого массива, любо первый элемент второго. Поэтому нужно завести два индекса aIndex и bIndex. Сравниваем два индекса, выявляем меньший элемент, записываем его в третий массив, при этом индекс перебрасываем вправо. И повторяем всю операцию до конца. Тогда время слияния примерно будет равным суммарному количеству элементов. Еще часто этот вопрос усложняют так: как ускорить этот алгоритм, если оказывается, что в каждом из массивов есть большие цепочки отсортированных чисел? Например, [1, 1, 2, 3, 1000, 1003, 1007] и [100, 100, 101, 102, 104]. То есть в одном массиве есть последовательности элементов, которые целиком попадут в определенные места второго массива. Но мы не знаем, где эти границы. Один из вариантов ответа. Сначала определяем в одном из массивов, что его следующее значение сильно отличается. Во втором массиве устанавливаем счетчик количества значений, которые были взяты подряд. Если он достигает, например, три – начинаем проверять значения с шагом х2 (то есть второе, четвертое, восьмое и т.д. Можно шаг делать большим, например х10, в зависимости от того, сколько у нас элементов). Далее стабилизируем границу и с помощью System.arraycopy скопировать этот кусок массива в первый. Задача на поиск цикла в односвязном списке Еще одна очень популярная задача на собеседовании. У нас есть 100-этажное здание и есть два крепких стеклянных шара. И мы должны, используя минимальное количество попыток, обнаружить такую пару этажей, что с нижнего шар еще не разобьётся, а с верхнего разобьётся. Простейший алгоритм: если у нас есть один шар, то мы берем его, поднимаемся на первый этаж, бросаем из окна, он не разбился. Поднимаемся на второй этаж, бросаем. Далее на третий, четвертый, пятый и т.д. Если шар разбился на этаже k, то это и есть искомый этаж, а на предыдущем этаже k–1 шар не разбивается. В этом случае уйдет очень много попыток, в худшем случае 100. Но если у нас есть два шара, то самый простой способ – сразу подняться на 50-й этаж, бросить оттуда шар. Если он разбился, то этот этаж лежит в диапазоне между 1 и 50. И вторым шаром сканировать этажи от 1 до 50 подряд. В худшем случае выйдет перебор не 100 этажей, а 51. Но оказывается, и это не оптимальное решение, можно еще значительно уменьшить количество попыток. Известно, что сумма двух сомножителей для заданного произведения минимальна тогда и только тогда, когда эти сомножители равны друг другу. Бросаем первый шарик последовательно с этажей: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99. Если он разбился на каком-либо шаге, оставшихся бросков хватит, чтобы пройти этажа, следующего за тем, с которого был совершен предыдущий бросок, до предыдущего этажа. Ответ: 14. В целом, на собеседовании есть три типа вопросов на сообразительность, оценку и математические, а не по Java. Эти вопросы в основном странные и их копируют из гугла, фейсбука – из разных зарубежных контор. Типичные три такие вопроса на оценку: Сколько бензозаправок в Лос-Анджелесе? Сколько теннисных мячиков влезет в Боинг-737? Сколько весит гора Фузди в Японии? Этим они проверяют общий инженерный интеллект человека, и может ли человек делать реальные оценки. Например, в вопросе о заправках можно подумать так: сколько в ЛА примерно человек (миллионов 5), сколько у них машин (у американцев, наверное, 5 миллионов машин), сколько заправка в сутки продает бензина, сколько нужно машине в среднем бензина и просто посчитать, сколько должно быть бензозаправок, чтобы заправлять эти машины. Нужно в ответе указать порядок – 100, 1000, 100000. А можно по-другому подходить к ответу. Посчитать примерно площадь ЛА (прикинуть насколько он отличается от Киева. У Киева радиус примерно 15 км, соответственно площадь около 700 км2). И вспомнить, как часто в жизни на квадратуру встречается заправка (если по дороге каждый километр, то на каждый квадратный километр встречается заправка). Типичные вопросы на сообразительность: Почему канализационные люки круглые? Почему у телеги передние колеса меньше, чем задние? Но в последнее время вопросы на сообразительность перестали задавать, а на оценку еще кое-где остались. Остались математические вопросы. Из тех, что сейчас популярны: Про два стеклянных шара и здание. Задача с фитилями. Объемы с жидкостью, как переливаниями получить другой объем. Существует достаточно сильная корреляция между способностью человека учить программирование (именно не знать, а учить) и способностью решать такие математические задачки. Вот тут есть куча таких задачек на сообразительность. В следующей теме мы рассмотрим: Arrays Источник: http://becomejavasenior.com/courses/?utm_source=Java+Email+Courses&utm_campaign=aa710df388-JavaRangerBasicIntro&utm_medi | |
| Просмотров: 432 | | |
| Всего комментариев: 0 | |