Мелкими шажками мы придем к своей цели
Как я уже писал, на собеседованиях часто задаем какие-нибудь задачи. Не только логические, бывают и такие. А некоторые рассчитаны на проверку того, как кандидат может оптимизировать алгоритм.
Для примера разберем такую задачу:
в памяти есть картинка. Для простоты будем считать, что она в неупакованном виде (обычный bitmap) и размером точно как текущее разрешение экрана. Нужно перенести на экран картинку точка за точкой в самом что ни на есть случайном порядке.
И вот как ее решает типичный собеседуемый.
Первое, что озвучивается - давайте через random выбирать какую-нибудь точку, ставить ее на экран и так до тех пор, пока не перенесем все точки. Ну а чтобы знать, какие точки перенесли, будем складывать их в список и по нему проверять. Примечательно, что это неправильное решение - мало того, что требует изрядное количество дополнительной памяти, так и еще рискует не закончиться в обозримом будущем, ведь ближе к концу вероятность попадания рандомом на оставшиеся точки весьма снижается.
Ок, тогда делаем наоборот - складываем в список все координаты, выбираем случайную, переносим точку, координату из списка удаляем. Уже лучше - это по крайней мере работает. Однако недостатков у такого подхода к решению, в общем-то, простой задачи - море. Затраты на размещение списка, а потом удаление из него - хочется чего-то пооптимальнее. Кстати, если кандидат не может описать, чем плохо такое решение или хуже того - не может объяснить, почему предыдущее неправильное, то его шансы пройти собеседование резко стремятся к нулю.
Далее начинается оптимизация алгоритма. В данном случае нужно понять, что во-первых, список координат как таковой не нужен, взамен него вполне подойдет массив размером width * height, в котором будем отмечать уже перенесенные точки. Некоторые отмечают, что для этих целей подойдет даже битовый массив - и это неплохая оптимизация по памяти (правда, можно обойтись и совсем без массива, но об этом чуть позже). Следующим шагом нужно сообразить, как делать выборку из такого массива. Предположим, картинка у нас размером 4*3. Массив размером 12 заполняем нулями. Выбираем случайное число от 0 до 11 - пусть это будет 3. Помечаем его 1, точку с координатами x=3, y=0 копируем на экран. Следующее случайное число - но уже от 0 до 10 - предположим, будет 7. Идем по массиву и считаем: нулевая точка, не перенесена - значит, +1. Следующая - тоже самое, следующая, следующая... А вот она уже помечена, как перенесенная, поэтому на ней мы счетчик не увеличиваем. Идем дальше и останавливаемся на координатах x=4, y=1. Копируем, помечаем и далее, пока все точки не будут перенесены.
Теперь о том, как обойтись совсем без массива. Для этого нужно очистить экран каким-то одним цветом (например, черным), посчитать, сколько точек такого цвета в картинке и считать, что эти точки уже перенесены. Соответственно, начинать случайную выборку в диапазоне от 0 до width * height - <кол-во черных точек> - 1. И скопированные точки прямо в картинке затирать черным цветом.
Вот такая вот оптимизация. Если же кандидат оказывается эрудированным и вспоминает про генераторы псевдослучайных чисел и может внятно объяснить, почему для этой задачи они к месту - то это скорее всего наш кандидат :)
Для примера разберем такую задачу:
в памяти есть картинка. Для простоты будем считать, что она в неупакованном виде (обычный bitmap) и размером точно как текущее разрешение экрана. Нужно перенести на экран картинку точка за точкой в самом что ни на есть случайном порядке.
И вот как ее решает типичный собеседуемый.
Первое, что озвучивается - давайте через random выбирать какую-нибудь точку, ставить ее на экран и так до тех пор, пока не перенесем все точки. Ну а чтобы знать, какие точки перенесли, будем складывать их в список и по нему проверять. Примечательно, что это неправильное решение - мало того, что требует изрядное количество дополнительной памяти, так и еще рискует не закончиться в обозримом будущем, ведь ближе к концу вероятность попадания рандомом на оставшиеся точки весьма снижается.
Ок, тогда делаем наоборот - складываем в список все координаты, выбираем случайную, переносим точку, координату из списка удаляем. Уже лучше - это по крайней мере работает. Однако недостатков у такого подхода к решению, в общем-то, простой задачи - море. Затраты на размещение списка, а потом удаление из него - хочется чего-то пооптимальнее. Кстати, если кандидат не может описать, чем плохо такое решение или хуже того - не может объяснить, почему предыдущее неправильное, то его шансы пройти собеседование резко стремятся к нулю.
Далее начинается оптимизация алгоритма. В данном случае нужно понять, что во-первых, список координат как таковой не нужен, взамен него вполне подойдет массив размером width * height, в котором будем отмечать уже перенесенные точки. Некоторые отмечают, что для этих целей подойдет даже битовый массив - и это неплохая оптимизация по памяти (правда, можно обойтись и совсем без массива, но об этом чуть позже). Следующим шагом нужно сообразить, как делать выборку из такого массива. Предположим, картинка у нас размером 4*3. Массив размером 12 заполняем нулями. Выбираем случайное число от 0 до 11 - пусть это будет 3. Помечаем его 1, точку с координатами x=3, y=0 копируем на экран. Следующее случайное число - но уже от 0 до 10 - предположим, будет 7. Идем по массиву и считаем: нулевая точка, не перенесена - значит, +1. Следующая - тоже самое, следующая, следующая... А вот она уже помечена, как перенесенная, поэтому на ней мы счетчик не увеличиваем. Идем дальше и останавливаемся на координатах x=4, y=1. Копируем, помечаем и далее, пока все точки не будут перенесены.
Теперь о том, как обойтись совсем без массива. Для этого нужно очистить экран каким-то одним цветом (например, черным), посчитать, сколько точек такого цвета в картинке и считать, что эти точки уже перенесены. Соответственно, начинать случайную выборку в диапазоне от 0 до width * height - <кол-во черных точек> - 1. И скопированные точки прямо в картинке затирать черным цветом.
Вот такая вот оптимизация. Если же кандидат оказывается эрудированным и вспоминает про генераторы псевдослучайных чисел и может внятно объяснить, почему для этой задачи они к месту - то это скорее всего наш кандидат :)