Программирование, т. 6

вы че таких элементарных вещей не знаете, выжпрограамисты

да я чето подумал ты про power set говоришь и не мог догнать каким боком оно тут вообще

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

елси "все "пересечения"" (хотя это не пересечение вовсе) то это называется декартово произведение и тогда на выходе будут кортежи (из двух элементов) всех комбинаций элементов первого массива со всеми элементами второго (кросс джоин в sql)

вообще да, согласен нужно уточнять что имелось ввиду.

Just.doit

При клике на "откликнуться" там кинуло на 4 вопроса сразу, на которые надо прислать ответ вместе с резюме. Вот одним из вопросов было это, в итоге мне приплыл отказ. Я до этого делал 3 цикла, типа цикл по А - цикл по Б - если совпадение, то цикл по С и нахождение повтора, если повтора нет то запись в С. Мне ответили

Добрый день, Виктор!

В 4-ом вопросе тестового задания мы просили "функцию, которая максимально быстро ...", а Вами был применен самый медленный алгоритм из возможных (алгоритмическая сложность более чем N*M)

потому что worst case твоих трёх циклов это вообще около (n*k)^2, что есть слишком дохуя и действительно самый медленный из возможных вариантов

Just.doit

При клике на "откликнуться" там кинуло на 4 вопроса сразу, на которые надо прислать ответ вместе с резюме. Вот одним из вопросов было это, в итоге мне приплыл отказ. Я до этого делал 3 цикла, типа цикл по А - цикл по Б - если совпадение, то цикл по С и нахождение повтора, если повтора нет то запись в С. Мне ответили

Добрый день, Виктор!

В 4-ом вопросе тестового задания мы просили "функцию, которая максимально быстро ...", а Вами был применен самый медленный алгоритм из возможных (алгоритмическая сложность более чем N*M)

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

Если я сейчас после этого отказа у них попрошу второй шанс, при этом спросив "а шо такое пересечение массивов?", то имхо меня просто нахуй пошлют и всё тут

Just.doit

При клике на "откликнуться" там кинуло на 4 вопроса сразу, на которые надо прислать ответ вместе с резюме. Вот одним из вопросов было это, в итоге мне приплыл отказ. Я до этого делал 3 цикла, типа цикл по А - цикл по Б - если совпадение, то цикл по С и нахождение повтора, если повтора нет то запись в С. Мне ответили

Добрый день, Виктор!

В 4-ом вопросе тестового задания мы просили "функцию, которая максимально быстро ...", а Вами был применен самый медленный алгоритм из возможных (алгоритмическая сложность более чем N*M)

откликнесь еще раз и скопируй задание

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

Для этого надо новый акк регать вместе с заполнением резюме етс, оно не позволяет с одного акка два раза откликаться на одну вакансию

то что ты пишешь "по комбинаторике" такого нету нигде кроме SQL

елси "все "пересечения"" (хотя это не пересечение вовсе) то это называется декартово произведение и тогда на выходе будут кортежи (из двух элементов) всех комбинаций элементов первого массива со всеми элементами второго (кросс джоин в sql)

вообще да, согласен нужно уточнять что имелось ввиду.

ну я это и имел ввиду, это в принципе и есть что-то типа декартового произведения

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

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

Если я сейчас после этого отказа у них попрошу второй шанс, при этом спросив "а шо такое пересечение массивов?", то имхо меня просто нахуй пошлют и всё тут

ну то твоё решение ни для одного из возможных вариантов чем может быть пересечение не будет подходящим, потому что там даже близко не n*k

так что по факту ты им уже не подошёл

По-моему мне стоит просто написать, что если вы подразумеваете повторение элементов в выходном массиве, то будет вот эта функция: ....

Если же элементы не должны повторяться, то я бы использовал сортировку..... и в итоге функция имела бы вид. ....

горд за топан

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

и вот представь что изделия состоят только из детали со склада 1 и детали со склада 2. вопрос как найти перечень/количество изделий которые мы можем собрать сейчас.

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

и вот представь что изделия состоят только из детали со склада 1 и детали со склада 2. вопрос как найти перечень изделий которые мы можем собрать сейчас.

окей, убедил

По-моему мне стоит просто написать, что если вы подразумеваете повторение элементов в выходном массиве, то будет вот эта функция: ....

Если же элементы не должны повторяться, то я бы использовал сортировку..... и в итоге функция имела бы вид. ....

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

мне обычно всегда сразу писали после высылки ТестЗад - "если есть вопросы по заданию - пишите/спрашивайте, мы перешлем ответ наших специалистов (тк непосредственное общение шло с кадровиком)"

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

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

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

ибо лень

вообще надо копировать изначально задание и перечитывать много много раз (с первого раза почти всегда не понятно что имели ввиду в точности)

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

мне обычно всегда сразу писали после высылки ТестЗад - "если есть вопросы по заданию - пишите/спрашивайте, мы перешлем ответ наших специалистов (тк непосредственное общение шло с кадровиком)"

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

 

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

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

ибо лень

подписываюсь под каждым словом

2 варианта тут было бы достаточно

* ровно n*k через брут когда мы имеем на выходе дубликаты как будто это математическое пересечение двух мультимножеств

* через две сортировки + проход в n+k для того чтоб можно было отсеять дубликаты и при этом не выйти за пределы n*k

Нашёл в гугле вот это:

Пересечение двух массивов A и B — это массив только с теми элементами A и B, которые одновременно принадлежат обоим массивам, без дублей.

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function intersection(A, B)
{ var m = A.length, n = B.length, c = 0, C = [];
 for (var i = 0; i < m; i++)
 {
   var j = 0, k = 0;
   while (B[j] !== A[ i ] && j < n) j++;
   while (C[k] !== A[ i ] && k < c) k++;
   if (j != n && k == c) C[c++] = A[ i ];
 } return C;
}

Хуй знает, на самом деле Гляньте, тут реально n*m?

Нашёл в гугле вот это:

Пересечение двух массивов A и B — это массив только с теми элементами A и B, которые одновременно принадлежат обоим массивам, без дублей.

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function intersection(A, B)
{ var m = A.length, n = B.length, c = 0, C = [];
 for (var i = 0; i < m; i++)
 {
var j = 0, k = 0;
while (B[j] !== A[ i ] && j < n) j++;
while (C[k] !== A[ i ] && k < c) k++;
if (j != n && k == c) C[c++] = A[ i ];
 } return C;
}

 

Хуй знает, на самом деле Гляньте, тут реально n*m?

вообще сложность, как О(m*n) нельзя определять

камус мне ттут пару дней назад помогал советом по форме с отправкой изображений (л0л), хочу сказать спасибо, рил самый изи вариант был

Нашёл в гугле вот это:

Пересечение двух массивов A и B — это массив только с теми элементами A и B, которые одновременно принадлежат обоим массивам, без дублей.

Сложность алгоритма O(m*n), где m и n — длины входных массивов A и B соответственно.

function intersection(A, B)
{ var m = A.length, n = B.length, c = 0, C = [];
 for (var i = 0; i < m; i++)
 {
var j = 0, k = 0;
while (B[j] !== A[ i ] && j < n) j++;
while (C[k] !== A[ i ] && k < c) k++;
if (j != n && k == c) C[c++] = A[ i ];
 } return C;
}

 

Хуй знает, на самом деле Гляньте, тут реально n*m?

тоесть медленно работает если пересечений много

выглядит как m*n только я пока не до конца понял как оно работает

вообще сложность, как О(m*n) нельзя определять

схуяли?

sort(A);
sort(B);
while (i < n && j < k) {
 if (A[i] == B[j]) {
C[it++] = A[i];
i++;
j++;
 } else if (A[i] > B[j])
j++;
 else
i++;
}

Что-нить подобное выдаст тебе в лучшем случае O(n log n) + O(k log k) + min(n, k), или в худшем + (n + k)

Единственная проблема, что если размеры массивов меньше 6, то n*k будет меньше, чем сортировка + проход.

Про пересечение [2, 2] & [2] = [2, 2] улыбнуло.

теоретическая сложность (котора через О нотацию) у него таки m*n но вообще у него функции по скорости слабые какие-то всё-равно, он сделал немногим лучше чем вариант который финаро отправил с 3 циклами, только поиск дубликатов у него на порядок быстрее в среднем, а worst-case для них почти одинаков

для сортируемых объектов (а сортируемы считай все) через сортировку всё-равно должно быть гораздо быстрее чем O(m*n) при даже совсем небольших массивах

мне интересно стоит ли сейчас начинать изучать j2se и j2ee ?