Ычан: [d | au / b / bro / hr / l / m / mi / mu / o / ph / r / s / sci / tran / tu / tv / vg / x | a / aa / c / fi / jp / rm / tan / to / vn / vo]
[Назад]
Ответ в нить
Имя
Animapcha image [@] [?]
Тема   ( ответ в 25980)
Сообщение flower
Файл 
Пароль  (для удаления файлов и сообщений)
Параметры   
  • Прежде чем постить, ознакомьтесь с правилами.
  • Поддерживаются файлы типов 7Z, BZ, BZ2, GIF, GZ, JPG, MO, MP3, MP4, OGG, OGV, PDF, PNG, PSD, RAR, SVG, SWF, TXT, WEBM, WEBP, XCF, ZIP размером до 5000 кБ.
  • Ныне 3679 unique user posts. Посмотреть каталог
  • Максимальное количество бампов нити: 500
No. 25980  
Бросто берешь и решаешь без задней мысли.
No. 25981  
Несколько лет этим не занимался.

Очень простая задачка, но я мимодумно налепил два ненужных домолнительных массива. А можно было проще и в один проход: https://pastebin.com/7Zi3s97W

Чувствую себя бакой.
No. 25985  
https://leetcode.com/problems/number-of-ships-in-a-rectangle/

Тоже простая задачка, хотя помечена как Hard. Решается элементарно через рекурсию - это первое и единственное, что может прийти в голову.
No. 25989  
>>25985
Если чуть пристальнее вглядеться в условие, то увидите, что там ограничение по вызову функцией самой себя, и что решения, в которых мухлёж (созданием другой функции для рекурсии, например), имеют последствием дисквалификацию.
Ещё, проблему назвали интерактивной, что бы это не значило.
Если это значит многократный вызов той функции по разным запрашиваемым областям, я бы завёл дерево ранее найденных кораблей, проверяя в первую очередь, нет ли уже из чего ранее найденного в той области, и если нет, циклом по строкам искал бы корабль.
No. 25990  
>>25989
Простой рекурсии достаточно: https://pastebin.com/E06SPDCw

Там ограничение на 400 вызовов функции, при этом 10 кораблей и поле 1000 на 1000. Получаем как раз 4 10 log2(1000) вызовов при отбросе пустых квадратов - и гарантированно укладываемся.
No. 25994  
https://leetcode.com/problems/k-diff-pairs-in-an-array/

Важный момент – случай с k == 0 нужно рассматривать отдельно и проверять, что в массиве есть сразу два элемента с одинаковым значением.

Вполне подошло интуитивное решение через сортировку и два итератора. Однако, можно и лучше – через подсчет элементов в hashmap и проверку на вхождение туда элемента (key - k).
No. 26001  
https://leetcode.com/problems/subarray-sum-equals-k/

Задачка очень похожа на предыдущую, только мы ищем разность не непосредственно между элементами, а между суммами от нуля до элемента. Плюс учитываем повторения

Runtime: 56 ms, faster than 99.52% of C++ online submissions for Subarray Sum Equals K.
No. 26002  
>>26001
Мое решение этой задачи неинтересно и почти совпадает с авторским, но кто-то прислал туда вдвое более быстрое (20-30 ms): https://hastebin.com/qiqurohaxo.cpp

Автор создал какую-то свою структуру данных на битовых операциях, без пол-литра не разберешься.
No. 26003  
>>26002
А, понял. Это кастомная хэш-таблица для интов. Прикольно.
No. 26005  
Простая задачка, но я прочитал ее настолько мугичкой, что вместо подмножеств стал генерировать перестановки. Получилось сложнее и не нужно.
No. 26006  
>>26005
Все подмножества действительно элементарно перечисляются. Считай, берёшь числовую переменную, на еденицу увеличиваешь, и вот тебе оно самое, следующее и уникальное.
Тут интереснее, как быть с подмножествами мощности n. Для них вроде как тоже только числовыми операциями можно делать перечисления.
No. 26011  
Сегодня случилась странная история. Мне написали из киевской (!) геймдев-компании с предложением работы и релокации за их счет. Я попросил зарплату вдвое больше текущей - они замялись и попросили решить несколько задачек на онлайн-платформе. Задачки оказались очень легкими, запомнилось только то, что в одном месте понадобилось написать свою хеш-функцию для кастомного класса. Они в восторге.

А еще я не очень представляю, что такое UE4 и чем мне это грозит, лол.
No. 26012  
>>26011
> Спойлер, добрый день. К сожалению, с учетом последних событий, мы приостановили найм. Буду рад оставаться с Вами на связи)

Ну вот!
No. 26013  
>>26012
Промахнулся, дружок!
No. 26019  
Задачка с собеса в какой-то загруженный сервис метрики вк: у нас есть миллиард чисел типа int32, они записаны куда-то в файл. Оперативной памяти, чтобы запомнить их все, нам немного не хватает. Необходимо найти число типа int32, которого там нет.

Пришло в голову только разбить числа на интервалы значений по миллиону штук, каждому интервалу привязать сумму в переменной int64. В первый проход мы заполняем суммы и определяем какого интервала у нас нет. Во второй проход мы смотрим только на числа из этого интервала и находим конкретное пропущенное.

Меня обломали тем, что числа могут повторяться, и таким образом мы не можем знать сумму интревала заранее. Возможно, вместо суммы в этом случае может подойти другая агрегирующая функция, но я хз.
No. 26020  
94576209_p3.jpg - (1.91MB, 2733×3859)
26020
>>26019
Если там есть хотя бы 4 GiB памяти, то на запомнить их все памяти хватит однозначно: делаем операционку выделить нам обнулённый кусок памяти в 4GiB, и делаем так, чтобы i-ому биту этого куска соответствовало наличие числа i в том файле. Потом пробегаемся по тому куску пока не найдём бит равный 0, для чего можно задействовать long-и или даже AVX-регистры. i того найденного бита и будет тем числом, которого нет в том файле. Составленная структура данных называется bitmap и её сжатые варианты широко используются в СУБД.
Если там нет даже 4-х GiB памяти, то придётся использовать те сжатые варианты. Вот эта https://roaringbitmap.org/ реализация довольно популярна.
No. 26022  
Либо, идти в несколько проходов: скажем, сначала делаем bitmap для чисел от 0 до 2 в 31-ой, и если в нём ничего не нашли, потом делаем bitmap для чисел от 2 в 31-ой. Для миллиарда int-ов сжатие вряд ли поможет.
No. 26023  
65569830_p1.jpg - (784.30KB, 1202×1700)
26023
>>26020
Битовое поле с 4 млрд бит потребует 500 Мб памяти, не 4 Гб.
No. 26024  
>>26020
Именно, что не хватит. Ориентировочно один.

>>26022
Да, именно такая идея была изначально, меня попросили подумать как уменьшить число проходов.
No. 26026  
>>26023
Лол, действительно. Тогда понятно, чего они от меня хотели.
No. 26027  
3d6eaf9d0ccdecc6ac3976cd21793d58.jpg - (478.23KB, 2856×2931)
26027
>>26023
Моск лагает.
No. 26028  
>>26024
>>26026
Ох лол. Лол.

Тогда я им уже выдавал подходящее решение - я предлагал использовать для подсчета этоментов vector<bool>, а он как раз примерно так оптимизируется для уменьшения размера (хотя зависит от имплементации). Похоже, они не заметили, что его хватит для одного прохода, точно так же, как не заметил и я.
No. 26031  
Было немного странное собеседование на работу в знакомой мне области - поиск документов по ключевым словам. Правда, если у меня это поиск по сотням гигабайт данных в шардированных кластерах, то у них это индексация и поиск в приложении на пользовательской машине.

Вопрос: есть большой объем текстов, нужно посчитать количество использований для каждого слова - в различных падежах и склонениях. Количество уникальных слов - примерно 4 миллиона, а доступная оперативная память очень мала - несколько мегабайт.

Ответ: Слова языка используются с разной частотой и количество различных лексем в отдельно взятом документе намного меньше, чем четыре миллиона. Для каждого документа по очереди мы создаем в оперативной памяти хеш-мапу для подсчета, затем приплюсовываем результат к "общей" мапе, лежащей на диске.
No. 26100  
IMG_20220416_122611_397.jpg - (88.13KB, 1125×1130)
26100
キタ━━━(゚∀゚)━━━!!
Удалить сообщение []
Пароль  
[Mod]