Решается она за k проходов по массиву людей, что даже лучше чем у парня с видео. Вряд ли кто-то лучше сможет делать, но попробуйте. Погнали!
Решение: https://jsfiddle.net/1Lyjg7n9/
Задача: https://www.youtube.com/watch?v=xGvQN_g-JCI
Какая у меня зп я даже говорить не буду, чтобы вас не расстраивать
Почему он не спрашивает вопрос "ты знаешь кого-нибудь?". Тупо спрашивать про конкретного чела, когда можно за одни вопрос сразу несколько включить.
>Тупо спрашивать про конкретного чела, когда можно за одни вопрос сразу несколько включить.
Мы вам перезвоним
Я в мак пришёл устраиваться или куда?!
>Какая у меня зп я даже говорить не буду, чтобы вас не расстраивать
301к\нс?
Немного меньше
сеьер пиздабол на дваче
Соси жопу, писькомер
Для каждого k ты можешь удалить строчку. Посчитай сложность, клоун. Твое решение бездарное говно. Убейся нахуй
Вот поаккуратнее код расписал
https://jsfiddle.net/bqeupfj8/
>>258030843
>>258030792
>>258030746
>>258030696
>>258030627
>>258030544
>>258030513
>>258030486
>>258030390
>>258030357
>>258030023
>>258029995
>>258029937
>>258029889
Ебало дауна который усердно бампает тред на протяжении 25 минут, представили ?
>Посчитай сложность, клоун
O(k), даун)
Представил ебало дауна, который за мной следит)
Покормлю зелень.
Во первых у сабжа в задаче ровно ТРИ прохода по массиву.
За первый проход ты ищешь потенциальную знаменитость.
За два других ты проверяешь, что знаменитость действительно знаменитость.
Во вторых у тебя асимптотика кубическая. Предлагаю самостоятельно подумать, почему.
Мимо 500к/наносек бэкенд-архитект.
>О том, что ты не прав я скажу
>Почему именно я не скажу
Классика. Если тебе есть что сказать, то просто говори, иначе на хуй рот открывать?)
>асимптотика кубическая
Вообще лол. Значение этого знаешь хотя бы?) Показывай где она там кубическая
https://jsfiddle.net/bqeupfj8/7/
Ладно ладно, я тролирую, не рвитесь, просто надеюсь что недосмотрит и рванёт жопа
>https://jsfiddle.net/bqeupfj8/7/
Что я только что все сломал добавив еще одного человека. Иди переделывай
И ведь недосмотрел же))
О чем ты?
Сложность удаления ты учел, сын шлюхи?
Представь, что у меня было больше времени и я описал данные в виде графа по которому двигаюсь. В этом случае не надо будет ничего удалять. Так и скажи, что сгорел и ничего лучше написать не можешь
Лень смотреть. А по условию знаменитость гарантированно есть и он один, или ее может не быть?
Потому что если ее может не быть - мы должны будем опросить каждого о каждом
А если она есть - то нам всего лишь нужно найти чувака, который никого не знает, и он будет искомым. То есть, опрашиваем каждого до тех пор, пока он не скажет, что кого-то знает, после чего шлем нахуй
В чем я не прав?
>В чем я не прав?
В том, что это не самое оптимальное решение
Которое из? Знаменитость гарантирована по условию или нет?
Думаю, что гарантирована
А, точно, если в процессе кто-то сказал, что не знает i-го чела, то i-го чела можно не опрашивать
Ты долбоеб. Решения лучше O(k) быть не может. Сначала ты говоришь, что придумал решение лучше. Тебе говорят, что ты бездарный хуесос. Дальше ты говоришь, что будь у тебя время ты бы придумал решение лучше. Когда оно будет - тогда и приходи.
В виде графа он представит. Флаг тебе в руки, хуесос, граф строится в онлайне. Ебашъ блять. Напишешь - приходи. А пока ты тупой хуеглот, что обосрался
Хуя ты горишь
И сразу фейл. У тебя нет этого графа.
Если он у тебя есть, то задача упрощается до неприличия, просто считаем сумму по столбцам и строкам.
Вот почему фронтэндеров нельзя подпускать ни к чему сложнее табуретки.
А сложность удаления из списка у тебя О(1), да?
>Если он у тебя есть, то задача упрощается до неприличия, просто считаем сумму по столбцам и строкам
Столбцы и строки в граффе?
>Какая у меня зп я даже говорить не буду, чтобы вас не расстраивать
Если ты на том уровне что тебе на техсобесе задают вопросы про базовые алгоритмы сортирофки - то только посмешить можешь.
Из массива, самофикс
У ОП-а граф представлен в виде матрицы, что и видно на скриншоте.
ну так задача и состоит в частичном восстановлении этого графа путем опроса (i,j)
а в коде у него для проверки сразу забит граф, но он им не пользуется, потому что такое условие
Рад за тебя, что будучи макакой, у тебя хорошая ЗП. В своём же примере перемести знаменитость как последний элемент массива и получишь ОЙ. Ну или тупо перемешай между собой НЕзнаменитостей. И получишь ещё один ОЙ.
Меняем структуру данных и вуаля, сложность уже О(1). Не длагодари
Переместил, все работает. В чем я не прав?
>Меняем структуру данных
Экий ты умный. Сложность ремапа одной структуры данных на другую?
Знаменитости это ровно те i такие что i строка нулевая а i столбец единичный (за исключением нуля на диагонали)
Cчитаем две матрицы: одна M'[i,j] = 1 - M[i,j] ,вторая транспонированная M с заменой 0 на единицу на диагонали
Тогда i это знаменитость если скалярное произведение i строки в первой и второй матрице == n
Все манипуляции с матрицами сравнений не содержат, в итоге проходим один раз сравнивая скалярное произведение, O(n)
>Сложность ремапа
Они на старте будут как надо подготовлены. Ты когда пишешь приложение тоже всегда как попало хранишь данные, а при каждом выполнении приводишь их в порядок в памяти?
Алсо, забыл добавить, что почти всегда логичность, читаемость и гарантированно верный результат будет в приоритете над сложностью или оптимизированным кодом. А вообще, ты - хуёвый программист, потому что ты решил задачу, но решил неправильно, да ещё и с помпой этим гордишься, и потом из-за таких вот дебичей плавающие баги на проде появляются.
>>258032505
В том, что селебрити 5эй элемент, когда он должен быть 6-ым, если переместить его в самый конец.
мимо бэкенд сеньор в крупном финтехе
>В том, что селебрити 5эй элемент, когда он должен быть 6-ым, если переместить его в самый конец
Как именно это сломает скрипт?
>>258032561
>но решил неправильно
Ты так и не указал на ошибку
Высокая сложность
А тащем то где он не прав? Допустим есть какой то массив know у каждого объекта person
Что нам мешает сравнить содержимое этого массива с текущим массивом person? И не нужно говорить "риииии массив know может быть большим а группа маленькой", потому что с таким аргументом можно смело слать нахуй неприятие решение с O(k^2), ибо не принципиально для малых групп.
Притом если мне не изменяет память сравнение элементов двух массивов - o(logK), что как бы быстрее чем O(k)
Притом в лучшем случае при подобном сравнении мы за одно сравнение находим кандидата в знаменитость
>Как именно это сломает скрипт?
Скрипт должен находить кто из людей является селебрити. В твоём примере это тот, что с индексом 5. Если его переместить на 6 индекс, то алгоритм всё-равно покажет, что селебрити находится под индексом 5, что неправильно, задача не решена.
Говнозон хочет от вас следующее.
Задача это банальнейшая сортировка слиянием. Все описание задачи хитровыебанная абстракция, которая скрывает в себе сортировку наибольшего числа.
Человек который не знает никого но все его знает, это наибольшее число.
Остальные по такой логике. 1 знает два и три. Три не знает один и два. Но два знет три. Мысль вы уловили.
Условия, все знают его, никто не знает его это завуалированная подъебка что повторяющихся числе нет.
Говнозон так проверяет наличие у вас возможности переводить абстракцию в простые задачи.
Но задавать вам их будет не говнозон а сранные вебстудии, которые под него косят. Удачи.
>Что нам мешает сравнить содержимое этого массива с текущим массивом person?
Ничего не мешает, просто будет высокая сложность выполнения алгоритма. А так все ок
Сложность считаем по сравнениям, их ровно n
Ещё n^2 + n операций с памятью, ~ 2n^2 арифметических
Если ты просто перемещаешь элемент на другое место, без изменения других данных, это значит, что ты просто портишь данные. И вся твоя претензия, получается, состоит в том, что скрипт упал когда ему дали на вход неправильные данные. Да, это есть
Идёт 2021 год, люди с манямешными аватарками становятся всё тупее и тупее
Какой рейт в час?
Единственный, кто решил эту задачу
Ок, логику понял, беру свои слова назад, ты хороший прогер, разве что немного код надо бы отрефакторить.
function search(): number {
return 5
}
Ну а чо, если 5 - это не селебрити, идите на хуй, сами виноваты.
Так ведь как раз не будет, будет O(lnK)
И при каждом вызове у тебя будет вызываться условный List.contains(), который ой какой не быстрый
ОП блядь ты заебал.
Найди себе уже место джуна, и поработай хотя бы полтора годика, потом уже думай что тебя в гугле с амазоном спросят.
Один хуй без опыта ты дальше хрюши не пройдешь.
А в такие конторы что бы там кто не бухтел что вышка не нужна, в том же гугле из РФ только выпускники МФТИ да МГУ одни. Какое совпадение, блядь.
>в том же гугле из РФ
Охуительно наглый пиздеж
Как минимум двух человек знаю без вышки вообще, один устроился в 19 лет в прошлом году
Но это скорее исключение большинство дейсвительно с вышкой и большинство даже крутые ребята, а не задрочившие алгоритмы
Ты только по одному элементу можешь за раз получить для сравнения, то есть, если у человек знает всех, тебе надо будет у него про каждого человека отдельно интересоваться
> Меньше 4К баксов
> Срубли
> Сбер
Хехе, мило
>Считать чужие деньги
Ладно, ОП, я пошутил, я получаю еще меньше. Надеюсь у тебя все будет хорошо. Учись развивайся. Не перегорай, забивай хуй на свою жизнь как я. Спокойной ночи. Удачи, и успехов. А я пойду спать.
Обнял
>не забивай хуй
Спасибо.
Тут уже вопрос выборки изначальных данных, но я понял твою мысль. Просто с тем же успехом ты можешь "выключить" сразу половину группы, так что таки да, это алгоритм с не стабильным временем выполнения, но таки выигрывающий на больших выборках. А на маленьких тебе таки просто насрать, хоть перебором делай, разница будет незаметна. Хотя хули толку задача синтетическая и код будет написан в прод перебором просто потому что читать этот код в будущем будут идиоты.
И опять же ты наебешься с contains(element) в оригинальном решение, он медленный и я даже с этим наебывался
Напиши в коде свое решение. Оче сложно воспринимать вот такие рассуждения. В решении в оппосте сложность всегда O(k)
Увы, нет
Кароче, я вроде решил, но у меня там такой быдлокод, что я стесняюсь показать и меня говнонимы закидают гавном и ничего не поймут.
Кидай, все ок
У тебя 6 ебальников и откуда у каждого по шесть отношений, лол.
7 ебальников и 7 отношений (6 об окружающих + 1 о себе). Что тебя развеселило?
Бля я стесняюсь. Ты шел по массиву слева направо и перемещал указатель на тот элемент, который не знал элемент по предыдущему указателю?
По факту проще всего, и самым не быдляцким методом, для людей которые имеют хотя бы вышку в процганье, а не мамкины веб-макаки, будут битовые флаги, а там уже даже сортировка не нужна, лол.
1 << 0
1 << 1
1 << 2
Далее просто находишь ебальник у которого флаги = 0.
Семь ебальников, да. Зачем тебе хранить отношение о самом себе.
Нет, его я просто удалял, так как он не может быть знаменитостью, а потом переходил на следующий еще не проверенный элемент. Скидывай, а то я скоро спать. Хочу посмотреть что там
>>258033893
Какая сложность у алгоритма?
>>258033915
Чтобы не усложнять код
Мне лень открывать ide в час ночи так что лови псевдокод
class Person(){
BigInt id;
List<BigInt> linked;
boolean know(Person person){
return linked.contains(person.id);
}
public List<BigInt> findCommonLinks(List<Person> groupPersons){
Set groupSet = groupPersonsId.toSet();
return linked.stream().filter(i->groupSet.contains(i)).collectToList();
}
}
class Solution{
List<Persons> group;
psvm(){
set ignore;
possibleStar;
foreach person in group{
if(!ignore.contain(person))
links = person.findCommonLinks(group);
if(links.isEmpty())
if(possibleStar!=null) return noStarsHere;
posibleStar = person;
if(links.size<group.size) ignore.addAll(getUncommonLinks(links)); // вот где то тут мы можем отбросить огромную часть значений а можем и не отбросить, да
}
return checkStartLikeInVideo(possibleStar);
}
}
>Какая сложность у алгоритма?
Буквально O(N) там одномерный массив, цикл и сравнение.
int arr[7] = {
firstPerson | secondPerson | thirdPerson,
secondPerson | thirdPerson,
thirdPerson | sixthPerson,
firstPerson | seventhPerson,
secondPerson | fourthPerson,
0,
thirdPerson | fifthPerson,
}
for(size_t i = 0; i < 7; i++){
if(arr == 0) return i;
}
>Чтобы не усложнять код
Так у тебя знаменитость, нихуя не знаменитость, он сам себя не знает, переделывай так, чтобы он игнорил тогда то что знаменистость себя мог знать, он же других не может знать, а без этого значит что его не все знают.
Ну держи. У меня прошло тесты.
Обезьянний движок сожрал скобочки, ибо [ i ] это курсив ебанный :))
Кста, вот после этого, кто-то будет говорить еще что код на крестах большой и громоздкий :))).
>>258034356
Решение не подходит под условия задачи
Почему?
С моим что? Разобрался?
Просто добавь к каждому отношения к шестому, и все готово, количество итераций не превышает количества лиц. Если шестой знает сам себя, то придется каждого обходить и через маску вытаскивать знает ли он шестого, но я напомню что операции со строками еще более затратны чем применение битовых масок, ибо на применение битовой маски тратится ровно ОДИН такт процессора :)
Хорошо получилось
Там проблема только в одном будет по факту, что ты максимум можешь иметь 32 ебальника, при unsigned int, и 64 ебальника при unsigned long long
Так вот, надо у одного спросить, кого из люлей он знает, допустим, знает он двух.
Потом спросить этих двух, если сразу попали на знаменитость, то получается, в 2 шага решение..
Это с наилучшем случае, в наихудшем у тебя может попасться цикл из
ебало1 -> ебало2 -> ебало3 -> ебало1
Либо ты пойдешь по самому длинному пути из древа.
> Решения лучше O(k) быть не может
Может. О(1) например
Бывает, данные хранятся в обобщённой структуре для нескольких сервисов, но каждый из них маппит под нужный формат. И тут финт "да там уже в каком надо формате" не сработает.
> Решение: https://jsfiddle.net/1Lyjg7n9/
Ок, но у тебя:
1) захардкоден вариант с шестью человеками
2) нет проверки знают ли все остальные чела, который не знает никого
3) наивное предположение, что данные придут именно в формате двумерного массива
> Какая у меня зп я даже говорить не буду, чтобы вас не расстраивать
тысяч 10 рублей.