Программирование[8]

Что это за язык?

Это псевдокод)

 

Что это за язык?

Это псевдокод)

 

тут только фронтэндеры передного конца

слишком сложна

уж лучше сортануть сто тысяч чем массив на 2 ляма делать имхо

 

учитывая, что это задачка, явно должно быть решение получше сортировки и жора памяти

сортировка на GLSL (на CUDA тоже самое), считаем среднее значение пикселя и сравниваем с другими (1пиксель=1число массива, а не 4 как обчыно(по клику мыши показана яркость), сортировка горизонтально по насыщенности цвета, вертикально по яркости(с цифрами будет работать корректно))

https://www.shadertoy.com/view/WtsSR2

время расчета=

(высота.массива + ширина.массива)/(ФПС*2)

для 800*450 разрешения и 60фпс

10,4 сек

для 1920*1080 и 60фпс (2млн размер массива)

25 сек

жрет ~200мб видюхи

(пробел для сброса на фулскрине)

(сори ес не в тему, делать было не чего...)

вот хира пришел и сделал правильно

100к в условии это размер массива

у тебя же бул на каждое число

блять ты шо читать не умеешь там же написано булевый массив размера N

перечитай внимательнее пиздец....

обрати внимание: ответ лежит в диапазоне [1, N + 1] где N это размер переданного массива

https://medium.com/racial-equity-in-tech/how-to-fix-diversity-and-inclusion-at-your-company-5af85e51f85a

одаааа 

https://medium.com/racial-equity-in-tech/how-to-fix-diversity-and-inclusion-at-your-company-5af85e51f85a

одаааа 

у тебя уже и так есть белые привилегии, дай другим покодить, ну

Держите парни)

Алгоритм O(2*n), space O(n).
int min = -1;
for integer in array {
set.put(integer);
if integer > 0 {
min = Math.min(min, integer);
}
}
if min > 1 {
return 1;
}
int current = min;
while (set.contains(current)) {
current++;
}
return current;

set put и set contains не log(n) операции?

Это значит что мы можем создать булевый массив V размера N в котором отмечать какие числа мы встречали в массиве

что тебе непонятно?

ты собираешься отмечать true каждое ЧИСЛО ИЗ ДИАПАЗОНА ВСЕХ ВОЗМОЖНЫХ ЧИСЕЛ

или у тебя массив на [1, 2741235, 23] будет что, [true, true, true]? ну заебись, че

нет, я собираюсь отмечать числа от 1 до N, где N это размер заданного массива

я уже 3 раза это написал. лучше перечитай мой первый пост ОЧЕНЬ внимательно и пойми почему ответ лежит именно в диапазоне [1, N + 1], где N это размер заданного массива

проще код выкатить чтобы понятно было. щас закодирую и скину

https://ideone.com/dPFn5a

да, с кодом я понял, что ты имеешь в виду

У DDamager'a хорошее решение, хотя и ебанутое с первой точки зрения (потому что задание ебанутое).

Через HashSet решение. HashSet put/get O(1)
https://ideone.com/aSXmd7

Обычно в этой задаче хотят видеть ин-плейс алгоритм с модификацией исходного массива и без доп памяти. Решения с доп массивом булов или сортировкой слишком простые, скорее всего на реальных собесах во всяких гуглах даже не разрешат писать для них код, заставят "правильное" решение придумывать.

Задача есть на литкоде, кому интересно почитайте дискашены https://leetcode.com/problems/first-missing-positive/

В реальной работе, конечно, никто такой херней заниматься не станет, но это же число алгоритмическая задачка  

В реальной работе

берешь терабайт оперативки, подрубаешь PHP с MYSQL, врубаешь на полную катушку, и вуаля - твой фейсбук готов!

рекомендую ДЛЦ - Замороженный фронтенд

Обычно в этой задаче хотят видеть ин-плейс алгоритм с модификацией исходного массива и без доп памяти. Решения с доп массивом булов или сортировкой слишком простые, скорее всего на реальных собесах во всяких гуглах даже не разрешат писать для них код, заставят "правильное" решение придумывать.

 

Задача есть на литкоде, кому интересно почитайте дискашены https://leetcode.com/problems/first-missing-positive/

 

В реальной работе, конечно, никто такой херней заниматься не станет, но это же число алгоритмическая задачка

Чёт у меня иногда происходит диссонанс, когда есть задача с ограничениями и я вроде как должен найти ей решение, применимое и оптимальное в существующей среде, а потом появляется ответ в виде ... Цитата сообщения сверху..... И тут я ловлю дизмораль... Ладно, пойду дальше в дискретную математику нырять, там хоть интересно вроде.

 

Обычно в этой задаче хотят видеть ин-плейс алгоритм с модификацией исходного массива и без доп памяти. Решения с доп массивом булов или сортировкой слишком простые, скорее всего на реальных собесах во всяких гуглах даже не разрешат писать для них код, заставят "правильное" решение придумывать.

 

Задача есть на литкоде, кому интересно почитайте дискашены https://leetcode.com/problems/first-missing-positive/

 

В реальной работе, конечно, никто такой херней заниматься не станет, но это же число алгоритмическая задачка

Т.е. мое решение плохое или хуже чем у ддамагера?

Чёт у меня иногда происходит диссонанс, когда есть задача с ограничениями и я вроде как должен найти ей решение, применимое и оптимальное в существующей среде, а потом появляется ответ в виде ... Цитата сообщения сверху..... И тут я ловлю дизмораль... Ладно, пойду дальше в дискретную математику нырять, там хоть интересно вроде.

 

Смотря в каком контексте.

Если бы такая "задача" в реальном проекте возникла -- первой мыслью у адекватного разработчика была бы, разумеется, сортировка вектора с линейным проходом (если по каким-то причинам нам такой набор чисел вообще в векторе хранить надо, а не в дереве). И только если по каким-то причинам понятно, что этот множитель log(n) сильно портит общую производительность софта, тогда стоило бы задуматься о более оптимальном решении. На практике в большинстве случаев это не потребуется. У простых решений есть еще одно важное преимущество -- в них сложнее наделать багов, их проще читать / поддерживать.

Если же такую задачу дают на собеседовании (так себе задача для собеса, я такие не даю) -- почти наверняка ожидают решение с оптимальной асимптотикой по сложности/памяти. Можно, конечно, и с простых решений начать обсуждение, но почти наверняка скажут "да, так решить задачу можно, но давай подумаем, нет ли более оптимального по скорости/памяти решения". Везде, конечно, по-разному, но в большинстве компаний в духе гугл/фейсбук/яндекс/етц с четко отлаженной системой собеседований это будет именно так.

То есть решение через сортировку плохим, конечно же, назвать нельзя; на практике в нем смысл есть (у нас, кстати, есть одно место в коде, где ровно такая задача решается и у нас там именно сортировка воткнута; все вроде живы). Но на собесах как правило хотят посмотреть, что человек может придумать оптимальный (и скорее всего не самый простой) алгоритм, а также реализовать его и не насажать при этом багов. Вообще решать такие задачки -- отдельный скилл, который вполне можно прокачать, решив около сотни задач на разные темы на всяких leetcode / hackerrank.

Спасибо за информацию!

https://leetcode.com/problems/first-missing-positive/discuss/339078/Java-faster-than-100-with-a-very-good-step-by-step-explanation

ну вот тут чел сделал себе память для маркировки прямо в самом массиве

но если бы не тот код ддамагера я бы не понял, почему это вообще работает

Если же такую задачу дают на собеседовании (так себе задача для собеса, я такие не даю) -- почти наверняка ожидают решение с оптимальной асимптотикой по сложности/памяти. Можно, конечно, и с простых решений начать обсуждение, но почти наверняка скажут "да, так решить задачу можно, но давай подумаем, нет ли более оптимального по скорости/памяти решения". Везде, конечно, по-разному, но в большинстве компаний в духе гугл/фейсбук/яндекс/етц с четко отлаженной системой собеседований это будет именно так.

 

То есть решение через сортировку плохим, конечно же, назвать нельзя; на практике в нем смысл есть (у нас, кстати, есть одно место в коде, где ровно такая задача решается и у нас там именно сортировка воткнута; все вроде живы). Но на собесах как правило хотят посмотреть, что человек может придумать оптимальный (и скорее всего не самый простой) алгоритм, а также реализовать его и не насажать при этом багов. Вообще решать такие задачки -- отдельный скилл, который вполне можно прокачать, решив около сотни задач на разные темы на всяких leetcode / hackerrank.

 

весьма спорно что на собесах хотят оптимального

из того что я слышал - хотят проверить базу и хотят проверить соображалку - поэтому вариант предложить даже худшее решение n^2 потом улучшить его до n log n и на этом остановиться - вполне норм сценарий

в гугле из-за того что таких будет 100 на одно место, то чисто статистически найдется тот кто придумает оптимальное - тут соглашусь что шансы из-за этого могут снижаться, но не из-за того что собеседующие такие все из себя олимпиадники с phd и "о этот дауничь даже не смог придумать оптимального решения, хехе. в утиль его", а потому что найдется кто-то лучше

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

 

Если же такую задачу дают на собеседовании (так себе задача для собеса, я такие не даю) -- почти наверняка ожидают решение с оптимальной асимптотикой по сложности/памяти. Можно, конечно, и с простых решений начать обсуждение, но почти наверняка скажут "да, так решить задачу можно, но давай подумаем, нет ли более оптимального по скорости/памяти решения". Везде, конечно, по-разному, но в большинстве компаний в духе гугл/фейсбук/яндекс/етц с четко отлаженной системой собеседований это будет именно так.

 

То есть решение через сортировку плохим, конечно же, назвать нельзя; на практике в нем смысл есть (у нас, кстати, есть одно место в коде, где ровно такая задача решается и у нас там именно сортировка воткнута; все вроде живы). Но на собесах как правило хотят посмотреть, что человек может придумать оптимальный (и скорее всего не самый простой) алгоритм, а также реализовать его и не насажать при этом багов. Вообще решать такие задачки -- отдельный скилл, который вполне можно прокачать, решив около сотни задач на разные темы на всяких leetcode / hackerrank.

 

весьма спорно что на собесах хотят оптимального

из того что я слышал - хотят проверить базу и хотят проверить соображалку - поэтому вариант предложить даже худшее решение n^2 потом улучшить его до n log n и на этом остановиться - вполне норм сценарий

в гугле из-за того что таких будет 100 на одно место, то чисто статистически найдется тот кто придумает оптимальное - тут соглашусь что шансы из-за этого могут снижаться, но не из-за того что собеседующие такие все из себя олимпиадники с phd и "о этот дауничь даже не смог придумать оптимального решения, хехе. в утиль его", а потому что найдется кто-то лучше

 

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

 

Да, цель таких секций -- 1) проверить соображалку (умение придумать алгоритм) и 2) умение аккуратно перекладывать абстрактную идею на код. Если алгоритм простой, то второй пункт не проверяется, поэтому задачи тоже надо хорошие выбирать, чтобы не было очень простых и почти оптимальных решений Еще, кстати, существует такая специальная категория задач, где сама идея оптимального решения в принципе простая, но вот аккуратный код написать для нее сложно, такое тоже дают.

Я, конечно, в целом рассуждаю про компании уровня гуяндбуков; как в среднестатистических конторах дела обстоят не интересовался, там вообще анархия и какой-то общей схемы собесов нет. Бывают собесы, где вообще код практически не пишешь. На прошлой работе (hft-компания в мск) мы вообще извратом на собесах занимались (помимо прочих задачек на алгоритмы / concurrency) -- компилили бинарник, давали ноут и gdb/valgrind: надо было подебагать, попрофилировать и что-то про код рассказать  

Сам сейчас как раз ради интереса решил пособеседоваться; параллельно 7 международных HFT-компаний, в целом пока что по ощущениям все онлайн-собеседования близки к тому, как мы в Я их проводим, только попутно по C++ любят пообщаться еще. В онлайн тестах (codility/hackerrank) время от времени проскакивают какие-то безумные задачи, которые кажется нормальный человек, не-международный-олимпиадник, не осилит за остающиеся 20-30 минут (но при этом и без них дальше собеседоваться пропускают). На одном скайп-собесе была задача на оставшиеся полчаса реализовать матчинг строки по регулярке, из спецсимволов только звездочки (т.е. проверку строки по заданному паттерну, естественно не используя либы и всякие regex) -- здесь тоже есть правильное решение за O(N^2), но на него надо времени больше, чем полчаса; выбрал рекурсивное, оно вроде норм зашло.