2022-08-12 03:31:56
Виртуальное собеседование на позицию ML Engineer
Решение. Часть 2.
3.2)
Алгоритмы синьор (с неким @sneddy)
В первом случае нам заранее известно произведение скольких чисел нужно хранить. Поэтому в качестве хранилища будем использовать очередь размера n. После каждой операции пут в случае превышения очередью размера n мы будем выкидывать ее первое значение.
Также будем хранить текущее ненулевое произведение последних n чисел, которое обновляется после каждой операции put (умножить на новое число и поделить на первое число в очереди если она переполнилась). Тогда для выполнения гет нам нужно лишь возвращать это текущее произведение.
Самое популярное пространство для бага - не учесть что логика немного ломается в случае добавления нуля. Как вариант можно хранить отдельно количество нулей в очереди и если они есть в get отдавать 0, а как только они заканчиваются - выдавать текущее ненулевое произведение
Follow-up:
В этом случае придется хранить всё, вопрос только в каком виде. Как вариант можно хранить в обычном листе кумулятивные произведения от 1 элемента массива до текущего. В таком случае чтобы ответить на запрос get(self, k) достаточно выдать отношение кумулятивного произведения последнего элемента и -(k+1)-го.
Также в случае хранения кумулятивных произведений возникает опасность численного переполнения. Она может быть решена с некоторой вычислительной ошибкой хранением не самих произведений чисел а его логарифма Тогда кумулятивные произведения перейдут в кумулятивные суммы логарифмов, а отношение произведений - к разности сумм.
Код последний задачи я не приложил - но надеюсь что моего объяснения будет достаточно, чтобы внимательный читатель мог его воспроизвести
1.7K viewsAnuar Aimoldin, edited 00:31
D
