Бросто берешь и решаешь без задней мысли.
Несколько лет этим не занимался. Очень простая задачка, но я мимодумно налепил два ненужных домолнительных массива. А можно было проще и в один проход: https://pastebin.com/7Zi3s97W Чувствую себя бакой.
https://leetcode.com/problems/number-of-ships-in-a-rectangle/ Тоже простая задачка, хотя помечена как Hard. Решается элементарно через рекурсию - это первое и единственное, что может прийти в голову.
>>25985 Если чуть пристальнее вглядеться в условие, то увидите, что там ограничение по вызову функцией самой себя, и что решения, в которых мухлёж (созданием другой функции для рекурсии, например), имеют последствием дисквалификацию. Ещё, проблему назвали интерактивной, что бы это не значило. Если это значит многократный вызов той функции по разным запрашиваемым областям, я бы завёл дерево ранее найденных кораблей, проверяя в первую очередь, нет ли уже из чего ранее найденного в той области, и если нет, циклом по строкам искал бы корабль.
>>25989 Простой рекурсии достаточно: https://pastebin.com/E06SPDCw Там ограничение на 400 вызовов функции, при этом 10 кораблей и поле 1000 на 1000. Получаем как раз 4 10 log2(1000) вызовов при отбросе пустых квадратов - и гарантированно укладываемся.
https://leetcode.com/problems/k-diff-pairs-in-an-array/ Важный момент – случай с k == 0 нужно рассматривать отдельно и проверять, что в массиве есть сразу два элемента с одинаковым значением. Вполне подошло интуитивное решение через сортировку и два итератора. Однако, можно и лучше – через подсчет элементов в hashmap и проверку на вхождение туда элемента (key - k).
https://leetcode.com/problems/subarray-sum-equals-k/ Задачка очень похожа на предыдущую, только мы ищем разность не непосредственно между элементами, а между суммами от нуля до элемента. Плюс учитываем повторения Runtime: 56 ms, faster than 99.52% of C++ online submissions for Subarray Sum Equals K.
>>26001 Мое решение этой задачи неинтересно и почти совпадает с авторским, но кто-то прислал туда вдвое более быстрое (20-30 ms): https://hastebin.com/qiqurohaxo.cpp Автор создал какую-то свою структуру данных на битовых операциях, без пол-литра не разберешься.
>>26002 А, понял. Это кастомная хэш-таблица для интов. Прикольно.
Простая задачка, но я прочитал ее настолько мугичкой, что вместо подмножеств стал генерировать перестановки. Получилось сложнее и не нужно.
>>26005 Все подмножества действительно элементарно перечисляются. Считай, берёшь числовую переменную, на еденицу увеличиваешь, и вот тебе оно самое, следующее и уникальное. Тут интереснее, как быть с подмножествами мощности n. Для них вроде как тоже только числовыми операциями можно делать перечисления.
Сегодня случилась странная история. Мне написали из киевской (!) геймдев-компании с предложением работы и релокации за их счет. Я попросил зарплату вдвое больше текущей - они замялись и попросили решить несколько задачек на онлайн-платформе. Задачки оказались очень легкими, запомнилось только то, что в одном месте понадобилось написать свою хеш-функцию для кастомного класса. Они в восторге. А еще я не очень представляю, что такое UE4 и чем мне это грозит, лол.
>>26011 > Спойлер, добрый день. К сожалению, с учетом последних событий, мы приостановили найм. Буду рад оставаться с Вами на связи) Ну вот!
>>26012 Промахнулся, дружок!
Задачка с собеса в какой-то загруженный сервис метрики вк: у нас есть миллиард чисел типа int32, они записаны куда-то в файл. Оперативной памяти, чтобы запомнить их все, нам немного не хватает. Необходимо найти число типа int32, которого там нет. Пришло в голову только разбить числа на интервалы значений по миллиону штук, каждому интервалу привязать сумму в переменной int64. В первый проход мы заполняем суммы и определяем какого интервала у нас нет. Во второй проход мы смотрим только на числа из этого интервала и находим конкретное пропущенное. Меня обломали тем, что числа могут повторяться, и таким образом мы не можем знать сумму интревала заранее. Возможно, вместо суммы в этом случае может подойти другая агрегирующая функция, но я хз.
>>26019 Если там есть хотя бы 4 GiB памяти, то на запомнить их все памяти хватит однозначно: делаем операционку выделить нам обнулённый кусок памяти в 4GiB, и делаем так, чтобы i-ому биту этого куска соответствовало наличие числа i в том файле. Потом пробегаемся по тому куску пока не найдём бит равный 0, для чего можно задействовать long-и или даже AVX-регистры. i того найденного бита и будет тем числом, которого нет в том файле. Составленная структура данных называется bitmap и её сжатые варианты широко используются в СУБД. Если там нет даже 4-х GiB памяти, то придётся использовать те сжатые варианты. Вот эта https://roaringbitmap.org/ реализация довольно популярна.
Либо, идти в несколько проходов: скажем, сначала делаем bitmap для чисел от 0 до 2 в 31-ой, и если в нём ничего не нашли, потом делаем bitmap для чисел от 2 в 31-ой. Для миллиарда int-ов сжатие вряд ли поможет.
>>26020 Битовое поле с 4 млрд бит потребует 500 Мб памяти, не 4 Гб.
>>26020 Именно, что не хватит. Ориентировочно один. >>26022 Да, именно такая идея была изначально, меня попросили подумать как уменьшить число проходов.
>>26023 Лол, действительно. Тогда понятно, чего они от меня хотели.
>>26023 Моск лагает.
>>26024 >>26026 Ох лол. Лол. Тогда я им уже выдавал подходящее решение - я предлагал использовать для подсчета этоментов vector<bool>, а он как раз примерно так оптимизируется для уменьшения размера (хотя зависит от имплементации). Похоже, они не заметили, что его хватит для одного прохода, точно так же, как не заметил и я.
Было немного странное собеседование на работу в знакомой мне области - поиск документов по ключевым словам. Правда, если у меня это поиск по сотням гигабайт данных в шардированных кластерах, то у них это индексация и поиск в приложении на пользовательской машине. Вопрос: есть большой объем текстов, нужно посчитать количество использований для каждого слова - в различных падежах и склонениях. Количество уникальных слов - примерно 4 миллиона, а доступная оперативная память очень мала - несколько мегабайт. Ответ: Слова языка используются с разной частотой и количество различных лексем в отдельно взятом документе намного меньше, чем четыре миллиона. Для каждого документа по очереди мы создаем в оперативной памяти хеш-мапу для подсчета, затем приплюсовываем результат к "общей" мапе, лежащей на диске.
ｷﾀ━━━(ﾟ∀ﾟ)━━━!!
Долго возился вот с этим, решение работало, но не влезало в память. https://codeforces.com/contest/1721/problem/D Оказалось, что при разбиении задачи на подзадачи большая часть подзадач оказывались пустыми, но затем их раз за разом разбивало на все большее число пустых подзадач, что жрало память по экспоненте
>>26547 А в чём прикол этой задачи, написать парсер ввода? Я в уме посчитал примеры.
>>26607 Примеры специально сделаны небольшими, а так размеры массивов входных данных могут достигать 10^5. И как же ты в уме посчитал побитовые операции для всех 40320 возможных перестановок восьмиэлементного массива из этого примера?
>>26612 А там что-то про перестановки говорилось? function f (A, B: Array) return x: Integer where A.Length == B.Length is C: Array = new Array<Integer>(0 .. A.Length), Ci = Ai XOR Bi for i in 0 .. n, x = C0 AND C1 AND C2 ... AND Cn. — вот что там написано.
>>26613 Да, там говорилось про перестановки, а ты читал попой.
>>26615 Ну, там говорилось, что я могу их перетасовать (а могу и оставить), а не про то, что надо найти максимум f (A, B) при неизменном A и всех возможных вариантах упорядочивания B. Ну а так надо упорядочить B по критерию Ai XOR Bk = max (назовём упорядоченный массив B'), и после применить f (A, B'). В самом простом случае за квадратное время. Так?
>>26616 Там прямым текстом просят максимум. Твоя сортировка не сработает с массивами [8, 3], [4, 3] Просто напиши код так, чтобы он прошел тесты.
>>26619 Да, действительно. А если количество установленных бит посчитать? Упорядочить по критерию BitCountOf (Ai XOR Bk) = max >Просто напиши код так, чтобы он прошел тесты. А разве это интересно? И что делать, если тесты надо написать тебе самому?
>>26620 Уверен, что там тоже можно подобрать контрпример вида [101010101000, 11], [010101010100, 11]. > А разве это интересно? Да, я люблю по-быстрому сделать так, чтобы оно работало хоть как-то и хоть иногда, а уже затем допиливать возможности, оптимизировать и рефакторить. Возможно, даже переписывать заново, если пришла более крутая идея в процессе. Просто без быстрых наглядных результатов я теряю мотивацию. > И что делать, если тесты надо написать тебе самому Как вариант, набрать кучку случайных небольших массивов (можно добавить крайние случаи от себя), неэффективно, но набрутфорсить перестановки каждого и получить надежные ответы - а затем на основе этих данных тестировать другие алгоритмы. Но набор тестов уже есть на этой площадке. Вообще мое решение этой задачи имело сложность n*k — произведение длины массива на разрядность элементов, и мне кажется, что это очень неплохо.
>>26624 Ну вот видишь, стоило только задуматься, как будем это тестировать, так сразу и стало ясно, что это NP-полная задача. Ты рандомизацию использовал?
>>26636 > стоило только задуматься, как будем это тестировать, так сразу и стало ясно, что это NP-полная задача Хахаха, вот только тесты-то я предложил делать за факториальное время. > Ты рандомизацию использовал? Для задачи? Нет, простое честное решение в лоб за гарантированное время. Под спойлером выше же намек о методе.
>>26638 Простое честное решение в лоб — это divide&conquer генератор перестановок; здесь можно сэкономить на вычислении f (A, B) для каждой перестановки, но худший результат всё-равно имеет сложность (n!).
>>26641 Ну значит, ты не допираешь до более простого. Я не зря же добавил число разрядов в сложность, попробуй по ним проитерироваться и перераспределять числа так, чтобы ничего не терять на следующей итерации.
- wahaba + wakaba 3.0.9 + futaba + futallaby -
