Так, у нас собеседование. Вам необходимо решить 10 алгоритмических задач и 10 задач на логику, рассказать как работают алгоритм A*, красно-чёрные деревья, написать функцию извлечения корня без sqrt, ... Вы отлично справились с собеседованием, вы приняты! Ура! Босс, я готов начинать, какие у нас задачи? Там в юай надо 10 кнопок добавить, одну сделать красной, приступайте
А вот Вам реальность, а не реклама курсов и больших зарплат. Вам придётся тягаться с молодыми людьми с профильным образованием (спойлер - это бесполезно) и вы будете получать в два раза меньше чем они и они вас потом могут оптимизировать. К тому же тот факт что работу можно делать удаленно это огромный минус а не плюс, вас могут заменить в любой момент или дать пинка под зад, и на основании этого превратить в раба на галере. Работа программистом это постоянный стресс потому что каждый день новые задачи в половине случаев которые ещё никто не решал, а в каком нибудь Яндексе которые в 95% случаев никто не решал! Задачи эти надо решать вовремя т.к дед-лайны и неустойки по бизнесу никто не отменял и зачастую приходится рапрощаться с личной жизнью и сном в поисках решения. Это вам не оператор станка с ЧПУ где заранее известно как делать деталь и сколько времени уходит на её изготовление.
@@alexsmirniy Не знаю, у меня никакого стресса нету. Решаю столько времени, сколько мне потребуется, а замены это скорее в европейских странах, в РФ законодательно человека сложно уволить, а нового искать ещё сложнее
Задача №1 В отсортированной последовательности проще всего искать бинарным поиском. Маркером досрочного выхода из поиска будет равенство элемента и разности длины массива и индекса этого элемента. Т.к. значения слева уже не улучшат наш h-индекс. Сложность максимум log(n). 1. Устанавливаем левую и правую границы l и r на начало и конец массива 2. Вычисляем середину mid = (l+r)/2 3. Если значение по индексу mid равно (n - mid), то мы нашли максимально возможный h-индекс и возвращаем его 4. Если значение больше, то сдвигаем правую границу до mid и сохраняем текущий максимально достигнутый h-индекс, в противном случае сдвигаем левую границу. 5. Повторяем пункты 2-4 пока границы не сойдутся 6. Возвращаем последний сохранённый h-индекс в случае, если не нашли точного совпадения. import random N = 20 citations = [random.randint(0, N) for _ in range(N)] citations.sort() def quick_h(citations: list[int]) -> int: l, r, n = 0, len(citations) - 1, len(citations) h_index = 0 while l n - mid: h_index = n - mid r = mid - 1 else: l = mid + 1 return h_index print(citations) print(f"h-index: {quick_h(citations)}") Задача №2 Из условия досрочного выхода для первой задачи, можно сделать вывод, что актуальным для определения h-индекса являлась только совокупность значения некоторого элемента и расстояние от этого элемента до конца массива. Для последовательно поступающих значений, можно завести массив, который будет поддерживаться в отсортированном порядке и для определения текущего h-индекса будет необходимо и достаточно анализировать первый элемент массива и его длину. Длина будет соответствовать актуальному h-индексу, но только при условии, что значение первого элемента не меньше длины массива. 1. Пропускаем все значения равные нулю, печатая h-индекс = 0. Первое ненулевое значение записываем в массив, печатаем h-индекс = 1. 2. Если новое поступающее значение меньше длины массива или равно ей, т.е. меньше или равно текущему h-индексу, то добавлять его нет необходимости, улучшить его могут только большие значения. 3. В случае, если новое поступающее значение больше длины массива, то добавляем, сохраняя отсортированный порядок. 4. Т.к. длина изменилась, то может нарушится условие «значение первого элемента должно быть не меньше длины массива», в этом случае первый элемент необходимо удалить. 5. Печатаем текущее значение h-индекса и возвращаемся к пункту 2. Лучше всего для работы с упорядоченной последовательностью подходит двоичная куча, в нашем случае минимальная, которая эмулирует вышеописанный отсортированный массив, и позволяет совершать операции вставки и удаления за log(h) времени, где h - это текущий h-индекс. Итого максимальная сложность O(nlog(n)). Возможно есть и линейное решение, но пока не увидел как решить проблему с разными возможными минимумами. Ниже код с использованием стандартного модуля. В языках где такой функционал не реализован, придется написать дополнительный короткий код, реализующий базовые операции работы с кучей: восстановление, удаление, добавление. import random import heapq as hq N = 16 citations = [0]+[random.randint(0, N) for _ in range(N-1)] print(citations) def stream_h(citations: list[int]) -> int: heap = [] for count, c in enumerate(citations): if heap: if c > len(heap): if heap[0] == len(heap): hq.heapreplace(heap, c) else: hq.heappush(heap, c) elif c: hq.heappush(heap, c) print(f"Step {count + 1}") print(citations[:count+1]) print(f"Current h-index: {len(heap)}") print("----------------") stream_h(citations) * условия внутри цикла на проверку непустой кучи и ненулевого элемента можно убрать, если инициализировать кучу первым ненулевым элементом, как было описано в пункте 1. Но мне было лень дублировать print-ы, поэтому пусть остаётся так.
добавление в отсортированный массив - уже O(n). Погуглите алгоритм частичной сортировки, он же nth element, он есть готовый в STL. Суть в том, что мы просим поставить n-q элемент на то место, где бы он стоял, если бы массив был отсортированный, а также переместить элементы, которые больше или указанного вверх, которые меньше или равны - вниз. По реализации - похоже на qsort, но в рекурсии смотрим не на обе половинки, а только на ту, где наш элемент. В итоге - O(n). У нас индекс может или увеличиться на 1 или остаться прежним. Значит, достаточно добавить новую статью в массив и выполнить nth element для индекса на 1 больше старого и проверить этот элемент. Итого, O(log n) на шаг.
Думаю, что 2 и 3 этап можно заменить одним. Можно бежать справа налево добавляя к сумме значения, а когда сумма будет больше или равна индексу на котором находится цикл возращать это число
Если массив отсортирован, можно двоичным поиском искать, число из массива, которое больше или равно своего индекса + 1, если индекс считать справа и расположенным максимально к левому концу. Т.е. сначала в центр посмотреть, потом, если нашли такое число, сдвинутся на четверть в лево и т.д.
низкий поклон за ваш труд, хоть я ничего не понял , было очень интересно. Я сам являюсь мидл+ дата аналитиком в одной международной компании, но очень хотел бы перейти в МААНГ компанию. Надеюсь ваши видео помогут)
Как я понял h-index = N-h, т.е. у нас есть N-h элементов меньше h. Если статьи отсортированы сработает простой бинарный поиск. def h_index(citations: List[int]) -> int: n = len(citations) beg, end = 0, n-1 while beg = n - mid: end = mid - 1 else: beg = mid + 1 return n - beg #Time O(log(n)) В datastream можно взять упорядочную структуру ( в питоне есть SortedList) и считать h-index значения citations[n_old - h_index] для старого масива, если новое значение больше citations[n_old - h_index], то h-index += 1 и в противном случае значение не изменяем. добавляем значение в citations. #Time: O(log(n)), Space: O(n) Возможно это решение не оптимально.
Интересная задачка, спасибо. Только не вижу необходимости после того, как есть массив вхождений, еще раз алоцировать отсортированный массив, вместо этого можно в обратном порядке пробежаться по массиву вхождений, складывая его значения до тех пор, пока агрегированная сумма не догонит индекс.
Саша спасибо за такие видео, коротко и по дело, а главное объяснения решений очень понятны и хорошо разжеванны. Может запишешь видео о тонкостях работы в лондоне, какие часть зп удерживается налогом , про саму жизнь в Лондоне и т.п.
В последнем решении не нужен второй шаг. проще уже идти по массиву от последнего индекса к первому и смотреть какое число записано (и инкрементировать общий счетчик) если в 6 записано 2 значи мало запоминаем 2. если в 5 записано 0 то 2+0=2 это тоже меньше 5 запоминаем 2. если в 4 0 то 2+0=2 и тоде меньше 4. если в 3 - 1 то 2+1 =3 подходит и индекс равен 3
Тоже так подумал. Единственное думал не массив количества, а словарь делать, чтобы на нули не тратиться. 2 дополнительный вопрос вы с какой сложностью решили? Я так понимаю там вообще О(1). Добавил к частоте 1 за О(1). Проверил соседа справа в словаре частот за О(1) и все. Только нужно хранить старое h и словарь частот жолжен быть полным а не укророченым типа 6+.
Для решения с непрерывным потоком поступающих данных можно добавить второй массив, с элементами уже участвовавшими в подсчете h-index, и при последующем добавление элемента, удалять не подходящие элементы. Те при каждом новом n элементе, алгоритм будет бегать по дополнительному массиву из h+1 элементов.
У меня первая мысль была после сортировки, это заменить, что полностью сортировать массив не нужно. За O(n) в данном массиве находится медиана и разбивается массив на две части. Если медиана больше, чем половина от размера массива (грубо говоря n/2), то индекс Хирша по крайней мере n/2 и не зависит от значений, больших чем медиана. Если меньше, чем n/2, то индекс Хирша меньше, чем n/2, и нас интересуют только числа, большие медианы. После этого мы находим медиану в нужной нам половине и т.д. Весь алгоритм будет работать за O(n). Если вместо медианы использовать случайный элемент, то алгоритм получится проще и в среднем будет также работать за O(n), но хочется все-таки детерминированно. Нахождение медианы детерминированно за O(n) это отдельный вопрос, алгоритм есть. В целом на придумывание этого решения потратил минуты 2-3, но вот объяснить его за 20 минут может быть квестом.
Насчет первого вопроса дополнительного. Я бы использовал бинарный поиск. Например [0, 1, 3, 5, 6] нам надо найти наибольшее i при котором arr[i] < n - i. Рассматриваем 3 (arr[2] == n - 2 == 5 - 2 == 3) условие не выполняется, соответственно и у всех правых чисел условие не выполняется т.к. они больше или равны 3. Представим такую ситуацию [0, 1, 3, 3, 3] получаем arr[4] >= 1, arr[3] >= 2, arr[2] >= 3. Думаю понятно. Далее рассматриваем 0 (т.к. left=0, right=1, mid = (right - left) / 2 + left = 0) arr[0] < 5 условие выполняется, но мы не заканчиваем поиск, а смещаемся в правую часть, как раз для того, чтобы найти максимальный i. Получаем i = 1, ну и ответ 3. Сложность в данном случае O(logn)
вместо 2 и 3 части финального решения с корзинной сортировкой проще сразу суммировать значения массива count справа налево и как только сумма стала больше или равна текущему индексу выводить этот индекс - это будет ответ(если мы идем дальше и в цикле не вышли - return 0) мне эта идея пришла а не сортировка корзинная да и в целом с сортировкой и сравнением соседей кажется более громоздко. пример кода на ts: function hIndex(citations: number[]): number { // первая часть как в видео const n = citations.length; const count = new Array(n + 1); for (let citation of citations) { if (citation >= n) { count[n] = (count[n] ?? 0) + 1; } else { count[citation] = (count[citation] ?? 0) + 1; } } // вот тут в видео начинается часть 2 и 3 let sum = 0; for (let i = count.length - 1; i >= 0; i--) { sum += count[i] ?? 0; if (sum >= i) { return i; } } return 0; };
1. бинарный поиск. O(log n) 2. nth_element (он же в других источниках partitial sort). держим весь массив и последний посчитанный индекс Херша. Если новая статья улучшила индекс - она могла улучшить только на 1, ухудшить вообще нельзя. Значит, добавляем статью в хвост массива и делаем nth_element для номера на 1 больше старого индекса. Проверяем указанное место - если проверка прошла, индекс увеличился на 1, если нет - остался прежний. O(log n) на каждый шаг.
Второй доп. вопрос: нужна куча, чтобы на верху был минимальный элемент, и если входящие число меньше h индекса, его просто откидываем, если нет- добавляем в кучу, пробуем увеличить h, смотрим, сколько элементов придется выкинуть. Куча может повторяющиеся элементы.
После того как мы посчитали можно не сортировать, а работать непосредственно с массивом подсчитанных значений. Идём с конца и если значение больше или равно индексу, то возвращаем его, если нет , то увеличиваем следующее значение (индекс - 1) на количество в данной ячейке (вед h статьи должны цитироваться минимум h раз, а не ровно h). Вот код второй части на go: for i := len(cnt)-1; i>=0; i-- { if cnt[i] >= i { return i } if i > 0 { cnt[i-1]+=cnt[i] } }
первый вопрос: нужно использовать бинарный поиск. Если "количество элементов справа" больше чем "значение элемента" идем правее, меньше - левее. Итерация прерывается если "количество элементов справа" РАВНО "значению элемента" Заканчивается на правом у которого "количество элементов справа" всё ещё больше чем "значение элемента". Ответ - количество элементов справа. второй вопрос: хранишь(в карте) числа больше Н-индекса и их количаства. 1) Если приходит меньше или равный Н-индекса - игнорируешь, иначе сохраняешь в карту и проверяешь сумму количеств чисел больше Н-индекса (сумма всех исключив равного Н-индексу). 1.1) Если сумма больше или равна - увеличивашь Н-индекс на 1, иначе ничего.
массив citations совершенно необязательно переписывать - для решения достаточно заполненного массива count. можно взять его последний элемент и сравнить с индексом - если он больше то решение найдено. если меньше то мы прибавляем значение этого элемента к предыдущему и так пока не найдем или не дойдем до индекса -1. аналогично решается и вторая допзадача, но вместо массива count нужно хранить какой-нть map где ключ - значение из массива citation & value - число таких элементов + нужно наибольшее значение чтобы начинать поиск по этому словарю с него
Второе решение на питоне, только вместо сортировки я использовал преобразование листа во множество и обратно, и т.о. мы получаем отсортированный массив из уникальных элементов: def h_index(papers): papers = list(set(papers)) max_h_index = len(papers) for h_index in range(max_h_index-1, -1, -1): if h_index < papers[h_index]: max_h_index = h_index - 1 break return max_h_index papers_info = [3, 0, 6, 1, 5] print(h_index(papers_info))
интересно, а эту задачу можно решить через факториал или матричную степень? а как распараллелить эту задачу, если массивов цитирования статей несколько частично-пересекающихся? а как быстро пересчитать индекс Хирша, если добавилось число цитирования одной статьи в массиве? а что если построить дерево или граф, вместо плоского массива? а можно описать это в декларативном или функциональном, вместо императивного, языке программирования? а если БД с индексами вместо массива с сортировкой, и в SQL? а на конечных автоматах? а какая универсальная архитектура нейронных сетей могла бы доучиться до приблизительного решения с приемлемой точностью, начав с полностью необученного состояния?
Первое решение, которое пришло в голову для 1-ой задачи. можно двигаться от числа h, попутно сокращая его. Берём h-индекс и начинаем линейно пробегать по элементам, попутно удаляя их из масива, если они подходят под условие, складывая эти же элементы в новую структуру данных. В том случае, если у нас условие не выполнилось, пробегаем снова по массиву, но в нём уже будет меньше элементов, добавляем их в структуру, где лежат элементы, подходящие под условие на этом цикле h + 1. И так до момента, пока мы не найдём удовлетворяющее условие. То есть, мы на каждом этапе сокращаем изначальный массив.
Первая задача с помощью dict , решение которой сразу пришло в голову. n = [3,0,6,1,5] h = 1 d = {} while True: for i in n: if i >= h: if h not in d: d.setdefault(h,1) else: d[h] += 1 if d[h] < h: del d[h] break h += 1 print(max(d))
задача про H индекс (делал сам, на js) const getHidx = (array) => { let maxIdx = Math.max(...array); for (i = 0; i {if (e >= i) hIdxCount ++}) if (i === hIdxCount) return i; } } P.S. - переписал с console.log на return, после того как досмотрел - понял слабые места в своем коде, спасибо!
Спасибо Саша за видео, рад что ты вернулся! ❤ Видео можно проще делать для монтирования, главное наличие! Интересно что на leetcode полно задач, но смотреть видео гораздо интересней
Можно решить ещё быстрее и проще (я про основное решение а не про дополнительные вопросы), тоже за O(n) но тем не менее быстрее, за один проход. Алгоритм такой, изначально считаем h индекс == n, проходим по массиву если встречаем число меньше h, то декрементируем h (h=h-1) и продолжаем проход с того же числа (т.к. знаем что все числа которые прошли до этого точно больше нового h) таким образом задача решается за один проход без сортировки
@@Fritz131415 спасибо за ответ, я имел ввиду концепцию, а не готовый алгоритм. В этом случае нужны две переменные. Как бы двусторонний счетчик. И проходя по массиву уменьшаешь максимальный h - встречая меньший элемент, и увеличиваешь минимальный h если встреченный элемент >= минимальному h. Надеюсь понятно объяснил. Возможно нужно будет ещё хранить индекс... Хммм.. стоит сперва попробовать решить на литкоде
Спасибо, прикольная задачка. Решил примерно вторым способом. Любопытно, что этот h index у учёного будет 0, если у него мало статей, но их все хорошо цитируют :)
@@Gribozhuy Я про то, что можно совместить подсчет статей с определенным цитированием и сразу же считать индекс, без повторного обхода массива количества цитирований с конца для поиска индекса цитирования. Опять же, смотрим ЕГЭ 27, там много подобных задач.
У меня есть вариант для решения с отсортированным массивом со сложностью O((logN)^2). Далее для поиска h-индекса применем бинарный поиск. Мы можем его использовать, т.к. если сущ. h-индекс то сущ. и h-1 индекс. Возьмём l = 0, r = размеру массива. Если сущ. индекс mid [(l + r) / 2] то двигаем левую границу, иначе правую. Проверять будем тоже с помощью бинпоиска (алгоритм upper_bound из заголовочного файла algorithm C++). Если мы нашли элемент где значение > h И расстояние от конца массива до этого индекса больше h - то да индекс h существует и мы двигаем левую границу, иначе - правую. (logN)^2 растёт куда медленне чем N начиная со значения 16. Я не считал, просто построил графики в десмосе)
Итерируемся по массиву начиная с 1 индекса Запоминаем нулевой индекс - В данном случае 3 - пусть будет переменная x и вторая такая же y Далее сравниваем y и все последующие элементы Если i >=y то x+=1 иначе x-=1 Return x
не понял сложности - мои обычные будни... и сразу оптимизируем код с учетом вероятности нормального распределения цитирования. def hindex(m: list) -> int: n = len(m) for h in range(n, 0, -1): j = h for i, e in enumerate(m): if e >= h: j -= 1; if not j: return h else: if j >= n - i: break return 0 # выполнение: hindex([3, 0, 6, 1, 5])
по первой задаче решение такое увидел , циклом проходим каждое число в итерации выполняем второй цикл от 1 до текущего значения числа формируем выходной массив где индекс итерации является индексом выходного массива и просто прибавляем к значению под этим индексом единицу в итоге на выходе получим массив с нашими H индексами , останется найти максимальный H индекс , просто перебираем массив с H индексами и по условию значение массива больше или равно текущему индексу , если да то переопределяем число H индекса по итогу возвращаем переменную с H индексом из цикла
а посмотрел и понял что можно второй цикл ограничить длиной входного массива , но тогда количество итераций будет где то в длину основного массива помноженное на количество интераций цикла до длины первого .
решение на вторую, о котором я в начале подумал наверно не хуже, скажи свое мнение: возможно напишу с ошибками, не в редакторе все таки, понадобится только цикл в цикле и две переменных function Fn() { let i = 1, count = 1 while (i { if (item > i) { count--; if (count 0) { // тут невыполнилось условие, значит в предыдущей итерации был нужный результат: return i - 1; } }) } } Fn(); я пока в тему О(n) не вникал, но думаю 2 переменных это хорошее решение
В третьем способе решения ведь необязательно после подсчёта элементов снова записывать их в массив. Можно массив подсчета пройти справа налево до момента пока сумма значений пройденных элементов массива не станет больше или равна индеску текущего элемента. Так как он начинается с 0, то даже n-1 делать не нужно.
Для перой задчи: бинарный поиск нужен (будет O(log n) ). Для второй задачи: - считаем, что на вход будут по одному подваться числа, например из массива articles - [11111,0,1,7,4,7,88,11010,0,1,2,7,7,7,7,7,88,3,2,2,3,5,3,3] - проверки будут проходить в цикле articles (не очень понимаю, как именно можно эмулировать поступление значений на вход по одному, без использования массива и цикла) - создадим объект, в котором будут храниться ключи (количество цитирований статьи) и значения (сколько статей с таким числом цитирований мы зафиксировали) let h = {}; - создадим переменную где будем хранить ответ (текущий индекс Хирша для обработанной последовательности) let answer = null; - если текущий ключ не определен (мы еще не получали на вход статью с таким кол-вом цитирований), инициируем его в объекте h значением 1 иначе, прибавляем к значению 1 - далее делаем две проверки если в объекте значение по ключю, равного текущему зачению на входе больше или равно значению на входе И текущее значение на входе больше текущего ответа - это и есть текущий ответ ========================================================= const articles = [11111,0,1,7,4,7,88,11010,0,1,2,7,7,7,7,7,88,3,2,2,3,5,3,3]; let h = {}; let answer = null; articles.forEach(a => { (h[a] === undefined) ? h[a] = 1 : h[a]++; if (h[a] >= a && a > answer) { answer = a; } }); console.log(answer); ========================================================= - для данной последовательно будет ответ 7
@@DmitryPatrushev-wd5fq Ага не подумал. Тогда все таки через создание массива и его сортировку const articles = [8, 8, 8, 8, 8, 8, 8]; let h = 0; articles.sort((a, b) => b - a); articles.forEach(e => { h = articles.findIndex((e, i) => i + 1 > e); if (h === -1) { h = articles.length; }; }); console.log(h); // 7
зачем эту сортировку подсчетом было делать? Вроде можно просто начать с h=5, дальше пойти по массиву и декрементить h если nums[i] < h. Но это я придумал только на примере инпута из видео автора
отсортируем в обратном порядке, а потом пойдем считать так же в обратном порядке и сравнивать позицию элемента и его значение. Вернем предыдущий, от которого меньше. Если статьи пишет Донцова, то рещение из видео не подходит
в 3м собесе была задача на 3 лошади - это тебе даны 25 лошадей и стадион, где одновременно может бегать 5 лошадей, сколько нужно сделать забегов, чтобы выбрать 3 самые быстрые лошади)) недавно ее решал
с последним кодом может не сильно уменьшится время, но по идее мы же знаем сколько у нас 6+ элементов и по сути их можно не проверят а начинать сразу с n - 1 - (кол 6+) и h-индекс = кол 6+
Что-то не сходится. Каким образом в массиве из "n" элементов, диапазон значений может быть больше "n", он всегда будет "n" или меньше, т.е. всегда нужно использовать сортировку подсчетом и зачем изобретали другие сортировки непонятно.
Моё решение такое. Сортируем массив O(NlogN), бежим по индексам, берём разницу между размером массива и текущим индексом (кол-во оставшихся статей), бежим до тех пор, пока кол-во оставшихся статей >= значению по текущему индексу Time: O(N logN) Space: O(1)
Скорее на усидчивость. Большинство кто проходит успешно эти собесы не придумывают решения задач на ходу, они их либо уже прорешали, либо решали аналогичные и знают принцип.
На самом деле просто долбежка задач на литкоде) ищут они чуваков кто будет писать адекватный код который обработает миллиарды записей за адекватное время. У нас в СНГ таких нагрузок особо нет, по этому с этой точки зрения у нас проще собесы
@@inoob2624 неа не сходится. Архитектура и математика не одно и тоже. Одно дело сделать СУБД с нуля, которое будет миллионы записей в секунду обрабатывать. Другое дело применить правильные паттерны, подобрать подходящий яп, инфраструктуру, наладить работу в команде. После этого нормальный код и джун накидает по шаблону 😅
Не легче в каунт записывать на первом цыкле в каждый индекс сколько раз ты встретил число такое же или больше , а во втором цикле вернуть найбольший индекс каунт в котором записанное число равно или больше индекса
Можно построить дерево отрезков на сумму и добавление значения, потом при добавлении нового числа будем прибалять 1 в дереве(как в массиве при сортировке подсчетом) и бинарным поиском подбирать h и проверять можем мы его получить или нет. Ели сумма с индекса n - h +- 1 до n >= h, то сдвигаем левую границу бин поиска , иначе правую и когда отрезок станет равен 1 это наш ответ
На второй допвопрос. Следует проверять каждое новое выпадающее значение на величину относительно эйч_индекса. Если оно больше или равно эйч_индексу, то эйч_индекс инкриминируется. Положить эйч_индекс изначально равным нулю.
Так, я не программист, но вопрос такой, мы получаем в решении Саши для заполнения массива вложенные циклы, разве там не будет сложность O(n*m), а не O(n)?
Быстрее линии только логарифм (ну и константа), значит бин поиском. Т.е. смотрим на средний элемент массива - а не больше ли он, чем длина половины массива. Если да, ставим h-index равным половине длины массива и идёт в левый полумассив проверить тоже самое. В общем, бинпоиск. Основная сложность - всякие граничные условия правильно учесть Для второй - нам пофиг на значения
Прикольно! Делитесь интересными задачками с реальных собеседований, Саша Лукин. Суперценные вести - [ценные] и технологически-научно (для изучения программирования), и рыночно-экономически (для изучения рынка работодателей). Подписка, мы следим за вашими выпусками
Hash set (multi): Проходясь по массиву записываем подходящие числа для h-index, пока не наберем h штук. O(1) h-index увеличиваем и удаляем все меньшие h числа из сета O(1), эти числа всегда будут равны h - 1 Time = Memory = O(n)
А затем, этот вариант легко превращается в решение, где цифры подаются по одной: ```golang func hIndex(citations []int) int { m := make(map[int]int) hMap := func(input int) int { m[input]++ i, h, max := 0, len(m), 0 for ; i
Тем, кто решил обе доп.задачи за O(log n), предлагаю чуть-чуть усложнить задачу, приблизив ее к реальности. В жизни же сначала статью пишут, потом она годами набирает ссылки. Итак: в программу идет вперемежку поток сообщений вида "Написана новая статья" (у новой статьи - 0 ссылок) или "у статьи 232 добавилось 11 ссылок". В любой момент у программы можно спросить индекс Хирша ученого. Естественно, все 3 эти операции желательно проделывать за O(log n).
Первую задачу можно еще решить бинпоиском по ответу, типо перебирать ответ от 0 до n за logn, и проверять для каждого предполагаемого ответа подойдет ли он за n, таким образом мы сможем найти ответ за n log n.
Вместо двух первых действий в 3-ем решении можно как в JS создать мапу: const a = {}; for (let i = 0; i < citations.length; i++) { if (!a[i]) { a[i = 1]; } else { a[i]++; } } сounts получится быстрее. Или нет?
еще не досмотрел, но не очень понимаю, зачем из count на 9.36 создавать сортированый массив cotations, если достаточно пройтись в обратном порядке по массиву count, cумируя count-ы? типа index == valuesum? valuesum += valuesum + count[index ]
count[] сортировать не нужно было, нужен был просто второй цикл по count[] в обратном порядке for (q = 0, h = n; h >= 0; h--), суммируя значения массива q += count[h] до первого элемента для которого выполняется q >= h. h при этом будет h-индексом просто по определению.
так это ограничение искуственное. большие числа редуцируются к N+1 ибо от этого результат не исказится. 1000 можно свести к N+1. Для индекса цитирования 1000 мы не наберем 1000 статей в 5 элементном массиве. также как и для 5+1 поэтому смело меням 1000 на 5+1. Если я все правильно понял.
А если изначально предположить, что hindex равен 5 и потом пробежаться по массиву не сортирую, а просто проверяя. Если значение меньше пяти, то потенциальный индекс стал 4, если нет остался пять. И так уменьшать или оставлять индекс без изменения до самого конца. Вроде должно получиться.
1 цитирование одной работы = 1 или более 2 цитирования двух работ = 4 или более 3 цитирования трёх работ = 9 или более 4 цитирования четырёх работ = 16 или более h_indicies = [0, 1, 2, 3, 4] study = [3, 0, 6, 1, 5] if sum(study) >= 16: print(f'The H index is {h_indicies[4]}') elif sum(study) >= 9 and sum(study) < 16: print(f'The H index is {h_indicies[3]}') elif sum(study) >= 4 and sum(study) < 9: print(f'The H index is {h_indicies[2]}') elif sum(study) >= 1 and sum(study) < 4: print(f'The H index is {h_indicies[1]}') else: print("Can't calculate the H index")
первая задача вот так const articles = [3, 0, 6, 1, 5]; articles.sort((a, b) => b - a) for (let i = 0; i < articles.length; i++) { if (i + 1 > articles[i]) { console.log(i); break; } }
Отсортированный массив быстрее линейного времени можно наверное, только если делить список пополам? Допустим у нас 1000 статей. Берем сразу индекс по середине т.е. 500(порядковый номер) и сравниваем его с 500(h_index). Если он меньше, берем оставшуюся правую часть и также делим пополам, т.е. берем уже индекс 250(порядковый номер) и сравниваем с 250(h_index). Допустим он тоже меньше. Опять берем правую часть. Индекс 125 сравниваем с 125. Допустим опять меньше. Берем опять правую часть, сравниваем с 62(порядковый номер) и пусть тут уже будет значение больше 62(h_index), тогда берем левую часть и ее середину, со значением 93. сравниваем с 93, допустим опять меньше, берем снова середину между 93 и 62. Это 78 значение, сравниваем его с 78 (h_index) и допустим значение меньше, тогда берем середину между 78 и 62, это значение 70 и сравниваем его с 70 (h_index). Опять меньше, берем число между 70 и 62, это 66 сравниваем с 66, меньше. Берем между 62 и 66, это 64. Сравниваем, опять меньше. И остается только 63, проверяем его, если 63 >= 63(h_index), то ответ будет 63, иначе ответ 62. Метод поиска вроде называется как разделяй и властвуй, но это не точно. И интересно узнать, что может быть быстрее этого... По сути из 1000 значений я нашел ответ за 11 итераций и это рассмотрен худший случай.
Вариант решения первоначальной задачи: Сортируем массив подсчётом, параллельно считая общее значение всех элементов (все значения большие чем длины массива считая как его длину) Затем находим среднее арифметическое значений и переходим к элементу с индексом равным среднему арифметическому. Если удовлетворяет h, то проверяем h+1 и тд. иначе проверяем h-1 и тд. В худшем случае будет O(n), но в остальных должно быть чуть быстрее, наверное😅
Под "удовлетворяет h" подразумевается сравнение значение элемента массива под номером среднего арифметического со средним арифметическим. Если оно >= то удовлетворяет, иначе неудовлетворяет
При маленьком значении n, O(n) и O(n*logn) тоже не будут сильно отличаться. Неочевидно будет ли сортировка методом подсчета быстрее чем обычная сортировка. для массива из n элементов, значения которых могут быть 0 до n, при средних значениях n.
к тому же для сортировки подсчетом надо выделять и освобождать память. А это реально операции с неведомой трудоемкостью, зависящей от фрагментации памяти.
Задача собеседующего определить обладает ли кандидат минимальными знаниями, что необходимы для работы, а не может ли он решать искуственные олимпиадные задачи в неествественных условиях.
Я б искал максимальное из элементов от 0 по N-i. И сравнивал бы его значение с i. Как только значение меньше или равно i ответ получен. До O(n) не додумался бы точно)
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Так, у нас собеседование. Вам необходимо решить 10 алгоритмических задач и 10 задач на логику, рассказать как работают алгоритм A*, красно-чёрные деревья, написать функцию извлечения корня без sqrt, ...
Вы отлично справились с собеседованием, вы приняты! Ура! Босс, я готов начинать, какие у нас задачи? Там в юай надо 10 кнопок добавить, одну сделать красной, приступайте
По крайней мере слово с корнем «красн» встретилось и на собеседовании и в реальной работе. Это уже что-то!
За $200к в год можно и кнопку покрасить 😀
@@algoseekee это точно, люди за 200 долларов красят заборы, а тут за 200к какую-то кнопку покрасить
А вот Вам реальность, а не реклама курсов и больших зарплат. Вам придётся тягаться с молодыми людьми с профильным образованием (спойлер - это бесполезно) и вы будете получать в два раза меньше чем они и они вас потом могут оптимизировать. К тому же тот факт что работу можно делать удаленно это огромный минус а не плюс, вас могут заменить в любой момент или дать пинка под зад, и на основании этого превратить в раба на галере. Работа программистом это постоянный стресс потому что каждый день новые задачи в половине случаев которые ещё никто не решал, а в каком нибудь Яндексе которые в 95% случаев никто не решал! Задачи эти надо решать вовремя т.к дед-лайны и неустойки по бизнесу никто не отменял и зачастую приходится рапрощаться с личной жизнью и сном в поисках решения. Это вам не оператор станка с ЧПУ где заранее известно как делать деталь и сколько времени уходит на её изготовление.
@@alexsmirniy Не знаю, у меня никакого стресса нету. Решаю столько времени, сколько мне потребуется, а замены это скорее в европейских странах, в РФ законодательно человека сложно уволить, а нового искать ещё сложнее
Такого канала не видел вообще. Просто бомба
Первая мысль была - решить задачу с сортировкой, как во втором способе. Посмотрев видео до конца понял: Я НЕ УЕДУ ЖИТЬ В ЛОНДОН....
@@ez4sayk сколько ты прошел собесов в Гугл, умник? Это сидя на диване она легкая (хотя на литкоде она Medium).
Тут очень важен опыт решения алгоритмических задач. Чем больше вы решите, тем проще будет решать новые. Это задача, например, достаточно типовая.
"Посмотрев видео до конца дня понял"
мораль: не принимай решения вечером, утром - ты решился бы уехать жить в Лондон =)
Спасибо большое за то что делаешь. Продолжай дальше, а мы с удовольствием будем смотреть)
Задача №1
В отсортированной последовательности проще всего искать бинарным поиском. Маркером досрочного выхода из поиска будет равенство элемента и разности длины массива и индекса этого элемента. Т.к. значения слева уже не улучшат наш h-индекс. Сложность максимум log(n).
1. Устанавливаем левую и правую границы l и r на начало и конец массива
2. Вычисляем середину mid = (l+r)/2
3. Если значение по индексу mid равно (n - mid), то мы нашли максимально возможный h-индекс и возвращаем его
4. Если значение больше, то сдвигаем правую границу до mid и сохраняем текущий максимально достигнутый h-индекс, в противном случае сдвигаем левую границу.
5. Повторяем пункты 2-4 пока границы не сойдутся
6. Возвращаем последний сохранённый h-индекс в случае, если не нашли точного совпадения.
import random
N = 20
citations = [random.randint(0, N) for _ in range(N)]
citations.sort()
def quick_h(citations: list[int]) -> int:
l, r, n = 0, len(citations) - 1, len(citations)
h_index = 0
while l n - mid:
h_index = n - mid
r = mid - 1
else:
l = mid + 1
return h_index
print(citations)
print(f"h-index: {quick_h(citations)}")
Задача №2
Из условия досрочного выхода для первой задачи, можно сделать вывод, что актуальным для определения h-индекса являлась только совокупность значения некоторого элемента и расстояние от этого элемента до конца массива. Для последовательно поступающих значений, можно завести массив, который будет поддерживаться в отсортированном порядке и для определения текущего h-индекса будет необходимо и достаточно анализировать первый элемент массива и его длину. Длина будет соответствовать актуальному h-индексу, но только при условии, что значение первого элемента не меньше длины массива.
1. Пропускаем все значения равные нулю, печатая h-индекс = 0. Первое ненулевое значение записываем в массив, печатаем h-индекс = 1.
2. Если новое поступающее значение меньше длины массива или равно ей, т.е. меньше или равно текущему h-индексу, то добавлять его нет необходимости, улучшить его могут только большие значения.
3. В случае, если новое поступающее значение больше длины массива, то добавляем, сохраняя отсортированный порядок.
4. Т.к. длина изменилась, то может нарушится условие «значение первого элемента должно быть не меньше длины массива», в этом случае первый элемент необходимо удалить.
5. Печатаем текущее значение h-индекса и возвращаемся к пункту 2.
Лучше всего для работы с упорядоченной последовательностью подходит двоичная куча, в нашем случае минимальная, которая эмулирует вышеописанный отсортированный массив, и позволяет совершать операции вставки и удаления за log(h) времени, где h - это текущий h-индекс. Итого максимальная сложность O(nlog(n)). Возможно есть и линейное решение, но пока не увидел как решить проблему с разными возможными минимумами.
Ниже код с использованием стандартного модуля. В языках где такой функционал не реализован, придется написать дополнительный короткий код, реализующий базовые операции работы с кучей: восстановление, удаление, добавление.
import random
import heapq as hq
N = 16
citations = [0]+[random.randint(0, N) for _ in range(N-1)]
print(citations)
def stream_h(citations: list[int]) -> int:
heap = []
for count, c in enumerate(citations):
if heap:
if c > len(heap):
if heap[0] == len(heap):
hq.heapreplace(heap, c)
else:
hq.heappush(heap, c)
elif c:
hq.heappush(heap, c)
print(f"Step {count + 1}")
print(citations[:count+1])
print(f"Current h-index: {len(heap)}")
print("----------------")
stream_h(citations)
* условия внутри цикла на проверку непустой кучи и ненулевого элемента можно убрать, если инициализировать кучу первым ненулевым элементом, как было описано в пункте 1. Но мне было лень дублировать print-ы, поэтому пусть остаётся так.
Задача №1 - у нас не отсортированная последовательность
@@ipave 10:16 а если условие послушать внимательно?
супер! спасибо за пояснения и код.
Та же мысль была, отсортировать. бинарным поиском добить)
добавление в отсортированный массив - уже O(n). Погуглите алгоритм частичной сортировки, он же nth element, он есть готовый в STL. Суть в том, что мы просим поставить n-q элемент на то место, где бы он стоял, если бы массив был отсортированный, а также переместить элементы, которые больше или указанного вверх, которые меньше или равны - вниз. По реализации - похоже на qsort, но в рекурсии смотрим не на обе половинки, а только на ту, где наш элемент. В итоге - O(n).
У нас индекс может или увеличиться на 1 или остаться прежним. Значит, достаточно добавить новую статью в массив и выполнить nth element для индекса на 1 больше старого и проверить этот элемент. Итого, O(log n) на шаг.
Думаю, что 2 и 3 этап можно заменить одним. Можно бежать справа налево добавляя к сумме значения, а когда сумма будет больше или равна индексу на котором находится цикл возращать это число
Я думаю он разделил для наглядности
Хорошая мысль! Алгоритм будет быстрее, но сложность этого не покажет 😄
Вот я также для себя решил эту задачу и удивился когда в видео предложили сформировать отсортированный массив, но может и правда для наглядности.
Если массив отсортирован, можно двоичным поиском искать, число из массива, которое больше или равно своего индекса + 1, если индекс считать справа и расположенным максимально к левому концу. Т.е. сначала в центр посмотреть, потом, если нашли такое число, сдвинутся на четверть в лево и т.д.
Sus 😳
Да, но асимпотика не изменится, тк будет O(n logn + log n) вместо O(n logn + n), что не сильно меняет ситуацию
И вообще кажется данная идея с бинпоиском - лажа. Можно взять массив 2 6 6 6 6 6 6 6 6 и бинпоиск не найдёт его
@@neiro22 почему "n logn + log n" - массив же уже отсортирован, останется только log n
@@neiro22 Найдет, сразу заходим в центр видим 6, и сравниваем с макс чего можем получить - и сразу выводим.
низкий поклон за ваш труд, хоть я ничего не понял , было очень интересно. Я сам являюсь мидл+ дата аналитиком в одной международной компании, но очень хотел бы перейти в МААНГ компанию. Надеюсь ваши видео помогут)
1) Хорошо, но можно быстрее и с меньшей памятью. В целом решение подзадачи 3 (см. ниже) дает линейное время О(n), один проход по входному массиву, и память О(1). С другой стороны, мы знаем, что h-index имеет максимальное значение, скажем например 1000. Тогда мы можем завести массив нулей на in[1000] элементов и при проходе по массиву входных данных (input) добавлять единицу в in[input[i]] =+ 1. Затем мы идем в обратную сторону с конца while(sum[j:] h_index): num_greater += 1 in[new_item] =+ 1 if(num_greater - in[h_index] > h_index): num_greater -= in[h_index] h_index = (index > h_index, индекс следующего положительно элемента в in[...] массиве). Меня зовут Лёша и я безработный©
Какие же все таки есть умные люди,говорила же мама Учись сынок ,не прогуливай уроки )))
Как я понял h-index = N-h, т.е. у нас есть N-h элементов меньше h. Если статьи отсортированы сработает простой бинарный поиск.
def h_index(citations: List[int]) -> int:
n = len(citations)
beg, end = 0, n-1
while beg = n - mid:
end = mid - 1
else:
beg = mid + 1
return n - beg #Time O(log(n))
В datastream можно взять упорядочную структуру ( в питоне есть SortedList) и считать h-index значения citations[n_old - h_index] для старого масива,
если новое значение больше citations[n_old - h_index], то h-index += 1 и в противном случае значение не изменяем. добавляем значение в citations. #Time: O(log(n)), Space: O(n)
Возможно это решение не оптимально.
Интересная задачка, спасибо. Только не вижу необходимости после того, как есть массив вхождений, еще раз алоцировать отсортированный массив, вместо этого можно в обратном порядке пробежаться по массиву вхождений, складывая его значения до тех пор, пока агрегированная сумма не догонит индекс.
Саша спасибо за такие видео, коротко и по дело, а главное объяснения решений очень понятны и хорошо разжеванны.
Может запишешь видео о тонкостях работы в лондоне, какие часть зп удерживается налогом , про саму жизнь в Лондоне и т.п.
Ага, думаю такие видео сделать
В последнем решении не нужен второй шаг. проще уже идти по массиву от последнего индекса к первому и смотреть какое число записано (и инкрементировать общий счетчик) если в 6 записано 2 значи мало запоминаем 2. если в 5 записано 0 то 2+0=2 это тоже меньше 5 запоминаем 2. если в 4 0 то 2+0=2 и тоде меньше 4. если в 3 - 1 то 2+1 =3 подходит и индекс равен 3
Тоже так подумал. Единственное думал не массив количества, а словарь делать, чтобы на нули не тратиться.
2 дополнительный вопрос вы с какой сложностью решили? Я так понимаю там вообще О(1). Добавил к частоте 1 за О(1). Проверил соседа справа в словаре частот за О(1) и все. Только нужно хранить старое h и словарь частот жолжен быть полным а не укророченым типа 6+.
Для решения с непрерывным потоком поступающих данных можно добавить второй массив, с элементами уже участвовавшими в подсчете h-index, и при последующем добавление элемента, удалять не подходящие элементы. Те при каждом новом n элементе, алгоритм будет бегать по дополнительному массиву из h+1 элементов.
У меня первая мысль была после сортировки, это заменить, что полностью сортировать массив не нужно. За O(n) в данном массиве находится медиана и разбивается массив на две части. Если медиана больше, чем половина от размера массива (грубо говоря n/2), то индекс Хирша по крайней мере n/2 и не зависит от значений, больших чем медиана. Если меньше, чем n/2, то индекс Хирша меньше, чем n/2, и нас интересуют только числа, большие медианы. После этого мы находим медиану в нужной нам половине и т.д. Весь алгоритм будет работать за O(n).
Если вместо медианы использовать случайный элемент, то алгоритм получится проще и в среднем будет также работать за O(n), но хочется все-таки детерминированно.
Нахождение медианы детерминированно за O(n) это отдельный вопрос, алгоритм есть.
В целом на придумывание этого решения потратил минуты 2-3, но вот объяснить его за 20 минут может быть квестом.
Тоже так подумал на паузе. По сути квиксорт, но по одной ветке.
отличный разбор, побольше бы таких
Клас, выходишь на новый уровень!
Насчет первого вопроса дополнительного. Я бы использовал бинарный поиск. Например [0, 1, 3, 5, 6] нам надо найти наибольшее i при котором arr[i] < n - i. Рассматриваем 3 (arr[2] == n - 2 == 5 - 2 == 3) условие не выполняется, соответственно и у всех правых чисел условие не выполняется т.к. они больше или равны 3. Представим такую ситуацию [0, 1, 3, 3, 3] получаем arr[4] >= 1, arr[3] >= 2, arr[2] >= 3. Думаю понятно. Далее рассматриваем 0 (т.к. left=0, right=1, mid = (right - left) / 2 + left = 0) arr[0] < 5 условие выполняется, но мы не заканчиваем поиск, а смещаемся в правую часть, как раз для того, чтобы найти максимальный i. Получаем i = 1, ну и ответ 3. Сложность в данном случае O(logn)
вместо 2 и 3 части финального решения с корзинной сортировкой проще сразу суммировать значения массива count справа налево и как только сумма стала больше или равна текущему индексу выводить этот индекс - это будет ответ(если мы идем дальше и в цикле не вышли - return 0) мне эта идея пришла а не сортировка корзинная да и в целом с сортировкой и сравнением соседей кажется более громоздко. пример кода на ts:
function hIndex(citations: number[]): number {
// первая часть как в видео
const n = citations.length;
const count = new Array(n + 1);
for (let citation of citations) {
if (citation >= n) {
count[n] = (count[n] ?? 0) + 1;
} else {
count[citation] = (count[citation] ?? 0) + 1;
}
}
// вот тут в видео начинается часть 2 и 3
let sum = 0;
for (let i = count.length - 1; i >= 0; i--) {
sum += count[i] ?? 0;
if (sum >= i) {
return i;
}
}
return 0;
};
1. бинарный поиск. O(log n)
2. nth_element (он же в других источниках partitial sort). держим весь массив и последний посчитанный индекс Херша. Если новая статья улучшила индекс - она могла улучшить только на 1, ухудшить вообще нельзя. Значит, добавляем статью в хвост массива и делаем nth_element для номера на 1 больше старого индекса. Проверяем указанное место - если проверка прошла, индекс увеличился на 1, если нет - остался прежний. O(log n) на каждый шаг.
Я сидел, думал, что как-то надо плясать от размера массива. Но чтобы так... Круто, в очередной раз кайфанул, спасибо
Решил без этой вашей сортировки, про использовав мап. Довольно простая задача.
Второй доп. вопрос: нужна куча, чтобы на верху был минимальный элемент, и если входящие число меньше h индекса, его просто откидываем, если нет- добавляем в кучу, пробуем увеличить h, смотрим, сколько элементов придется выкинуть. Куча может повторяющиеся элементы.
и какая трудоемкость с учетом того, что вы не знаете, сколько придется отбрасывать на каждом шагу? Там же по одному элементу не определить.
После того как мы посчитали можно не сортировать, а работать непосредственно с массивом подсчитанных значений. Идём с конца и если значение больше или равно индексу, то возвращаем его, если нет , то увеличиваем следующее значение (индекс - 1) на количество в данной ячейке (вед h статьи должны цитироваться минимум h раз, а не ровно h). Вот код второй части на go:
for i := len(cnt)-1; i>=0; i-- {
if cnt[i] >= i {
return i
}
if i > 0 {
cnt[i-1]+=cnt[i]
}
}
первый вопрос:
нужно использовать бинарный поиск.
Если "количество элементов справа" больше чем "значение элемента" идем правее, меньше - левее.
Итерация прерывается если "количество элементов справа" РАВНО "значению элемента"
Заканчивается на правом у которого "количество элементов справа" всё ещё больше чем "значение элемента".
Ответ - количество элементов справа.
второй вопрос:
хранишь(в карте) числа больше Н-индекса и их количаства.
1) Если приходит меньше или равный Н-индекса - игнорируешь, иначе сохраняешь в карту и проверяешь сумму количеств чисел больше Н-индекса (сумма всех исключив равного Н-индексу).
1.1) Если сумма больше или равна - увеличивашь Н-индекс на 1, иначе ничего.
массив citations совершенно необязательно переписывать - для решения достаточно заполненного массива count. можно взять его последний элемент и сравнить с индексом - если он больше то решение найдено. если меньше то мы прибавляем значение этого элемента к предыдущему и так пока не найдем или не дойдем до индекса -1. аналогично решается и вторая допзадача, но вместо массива count нужно хранить какой-нть map где ключ - значение из массива citation & value - число таких элементов + нужно наибольшее значение чтобы начинать поиск по этому словарю с него
В оригинальном решении не нужен шаг с перезаписыванием массива, достаточно идти по k,v мапы в обратном порядке
Второе решение на питоне, только вместо сортировки я использовал преобразование листа во множество и обратно, и т.о. мы получаем отсортированный массив из уникальных элементов:
def h_index(papers):
papers = list(set(papers))
max_h_index = len(papers)
for h_index in range(max_h_index-1, -1, -1):
if h_index < papers[h_index]:
max_h_index = h_index - 1
break
return max_h_index
papers_info = [3, 0, 6, 1, 5]
print(h_index(papers_info))
интересно, а эту задачу можно решить через факториал или матричную степень? а как распараллелить эту задачу, если массивов цитирования статей несколько частично-пересекающихся? а как быстро пересчитать индекс Хирша, если добавилось число цитирования одной статьи в массиве? а что если построить дерево или граф, вместо плоского массива? а можно описать это в декларативном или функциональном, вместо императивного, языке программирования? а если БД с индексами вместо массива с сортировкой, и в SQL? а на конечных автоматах? а какая универсальная архитектура нейронных сетей могла бы доучиться до приблизительного решения с приемлемой точностью, начав с полностью необученного состояния?
@sashalukin А для последнего цикла мы же можем использовать двоичный поиск? Хотя на сложность алгоритма это не повлияет верно?
Первое решение, которое пришло в голову для 1-ой задачи. можно двигаться от числа h, попутно сокращая его. Берём h-индекс и начинаем линейно пробегать по элементам, попутно удаляя их из масива, если они подходят под условие, складывая эти же элементы в новую структуру данных. В том случае, если у нас условие не выполнилось, пробегаем снова по массиву, но в нём уже будет меньше элементов, добавляем их в структуру, где лежат элементы, подходящие под условие на этом цикле h + 1. И так до момента, пока мы не найдём удовлетворяющее условие. То есть, мы на каждом этапе сокращаем изначальный массив.
Класс, хочу ещё видео разборы пожалуйста
Офигеть мне прям сразу идея решения пришла, я даже не думал почти, я удивлен
Первая задача с помощью dict , решение которой сразу пришло в голову.
n = [3,0,6,1,5]
h = 1
d = {}
while True:
for i in n:
if i >= h:
if h not in d:
d.setdefault(h,1)
else:
d[h] += 1
if d[h] < h:
del d[h]
break
h += 1
print(max(d))
задача про H индекс (делал сам, на js)
const getHidx = (array) => {
let maxIdx = Math.max(...array);
for (i = 0; i {if (e >= i) hIdxCount ++})
if (i === hIdxCount) return i;
}
}
P.S. - переписал с console.log на return, после того как досмотрел - понял слабые места в своем коде, спасибо!
Спасибо Саша за видео, рад что ты вернулся! ❤ Видео можно проще делать для монтирования, главное наличие! Интересно что на leetcode полно задач, но смотреть видео гораздо интересней
смотреть не мешки ворочать :)
@@andreypopov6166 можно чередовать просмотр с ворочанием мешков, я всегда так делаю =)
(ну, правда, не мешки - а так, спортивный упражнения всякие)
Для решения доп вопроса подойдет использование дерева поиска с поддержкой размера поддерева. Но я не тестил. Чисто на вскидку
Можно решить ещё быстрее и проще (я про основное решение а не про дополнительные вопросы), тоже за O(n) но тем не менее быстрее, за один проход.
Алгоритм такой, изначально считаем h индекс == n, проходим по массиву если встречаем число меньше h, то декрементируем h (h=h-1) и продолжаем проход с того же числа (т.к. знаем что все числа которые прошли до этого точно больше нового h) таким образом задача решается за один проход без сортировки
Не получится, проверь на массиве [6, 0, 3, 1, 5]
По твоему алгоритму h будет меняться так: 5, 4, 3, 2, 2. А ответом должна быть 3.
@@Fritz131415 спасибо за ответ, я имел ввиду концепцию, а не готовый алгоритм. В этом случае нужны две переменные. Как бы двусторонний счетчик. И проходя по массиву уменьшаешь максимальный h - встречая меньший элемент, и увеличиваешь минимальный h если встреченный элемент >= минимальному h. Надеюсь понятно объяснил.
Возможно нужно будет ещё хранить индекс...
Хммм.. стоит сперва попробовать решить на литкоде
@@Fritz131415 Не, виноват, херню придумал
Спасибо, прикольная задачка. Решил примерно вторым способом.
Любопытно, что этот h index у учёного будет 0, если у него мало статей, но их все хорошо цитируют :)
При наличии цитирований h-индекс априори не может быть нулевым
@@SayXaNow да, верно
Допустим 2 статьи, у каждой по 1000 ссылок. Получается h только 2.
По сути 27 задача из ЕГЭ. А последний вопрос прямо наводит на решение вообще в один цикл :) Спасибо за интересные задачи.
Один цикл не значит что это максимально быстро. Если поддерживать какую то структуру в упорядочении виде это будет сложно log(n) на каждую вставку
@@Gribozhuy Я про то, что можно совместить подсчет статей с определенным цитированием и сразу же считать индекс, без повторного обхода массива количества цитирований с конца для поиска индекса цитирования. Опять же, смотрим ЕГЭ 27, там много подобных задач.
У меня есть вариант для решения с отсортированным массивом со сложностью O((logN)^2). Далее для поиска h-индекса применем бинарный поиск. Мы можем его использовать, т.к. если сущ. h-индекс то сущ. и h-1 индекс. Возьмём l = 0, r = размеру массива. Если сущ. индекс mid [(l + r) / 2] то двигаем левую границу, иначе правую. Проверять будем тоже с помощью бинпоиска (алгоритм upper_bound из заголовочного файла algorithm C++). Если мы нашли элемент где значение > h И расстояние от конца массива до этого индекса больше h - то да индекс h существует и мы двигаем левую границу, иначе - правую. (logN)^2 растёт куда медленне чем N начиная со значения 16. Я не считал, просто построил графики в десмосе)
Итерируемся по массиву начиная с 1 индекса
Запоминаем нулевой индекс - В данном случае 3 - пусть будет переменная x и вторая такая же y
Далее сравниваем y и все последующие элементы
Если i >=y то x+=1 иначе x-=1
Return x
Для массива 1, 1, 1, 1, 1 не работает.
Забавно, мне как раз финальный метод пришёл в голову , но я подумал что как-то просто для этого канала и решил что не то😅
не понял сложности - мои обычные будни... и сразу оптимизируем код с учетом вероятности нормального распределения цитирования.
def hindex(m: list) -> int:
n = len(m)
for h in range(n, 0, -1):
j = h
for i, e in enumerate(m):
if e >= h:
j -= 1;
if not j: return h
else:
if j >= n - i: break
return 0
# выполнение:
hindex([3, 0, 6, 1, 5])
по первой задаче решение такое увидел ,
циклом проходим каждое число
в итерации выполняем второй цикл от 1 до текущего значения числа
формируем выходной массив где индекс итерации является индексом выходного массива и просто прибавляем к значению под этим индексом единицу
в итоге на выходе получим массив с нашими H индексами ,
останется найти максимальный H индекс , просто перебираем массив с H индексами и по условию значение массива больше или равно текущему индексу , если да то переопределяем число H индекса
по итогу возвращаем переменную с H индексом из цикла
а посмотрел и понял что можно второй цикл ограничить длиной входного массива , но тогда количество итераций будет где то в длину основного массива помноженное на количество интераций цикла до длины первого .
lst = sorted(lst)
begin = 0
end = len(lst)-1
while begin +1 < end:
i = begin + (end-begin) // 2
if lst[i]
решение на вторую, о котором я в начале подумал наверно не хуже, скажи свое мнение:
возможно напишу с ошибками, не в редакторе все таки, понадобится только цикл в цикле и две переменных
function Fn() {
let i = 1, count = 1
while (i {
if (item > i) {
count--;
if (count 0) {
// тут невыполнилось условие, значит в предыдущей итерации был нужный результат:
return i - 1;
}
})
}
}
Fn();
я пока в тему О(n) не вникал, но думаю 2 переменных это хорошее решение
Спасибо за записи! ٩(｡•́‿•̀｡)۶
В третьем способе решения ведь необязательно после подсчёта элементов снова записывать их в массив. Можно массив подсчета пройти справа налево до момента пока сумма значений пройденных элементов массива не станет больше или равна индеску текущего элемента. Так как он начинается с 0, то даже n-1 делать не нужно.
Для перой задчи: бинарный поиск нужен (будет O(log n) ).
Для второй задачи:
- считаем, что на вход будут по одному подваться числа, например из массива articles - [11111,0,1,7,4,7,88,11010,0,1,2,7,7,7,7,7,88,3,2,2,3,5,3,3]
- проверки будут проходить в цикле articles (не очень понимаю, как именно можно эмулировать поступление значений на вход по одному, без использования массива и цикла)
- создадим объект, в котором будут храниться ключи (количество цитирований статьи) и значения (сколько статей с таким числом цитирований мы зафиксировали)
let h = {};
- создадим переменную где будем хранить ответ (текущий индекс Хирша для обработанной последовательности)
let answer = null;
- если текущий ключ не определен (мы еще не получали на вход статью с таким кол-вом цитирований), инициируем его в объекте h значением 1
иначе, прибавляем к значению 1
- далее делаем две проверки
если в объекте значение по ключю, равного текущему зачению на входе больше или равно значению на входе И текущее значение на входе больше текущего ответа - это и есть текущий ответ
=========================================================
const articles = [11111,0,1,7,4,7,88,11010,0,1,2,7,7,7,7,7,88,3,2,2,3,5,3,3];
let h = {};
let answer = null;
articles.forEach(a => {
(h[a] === undefined) ? h[a] = 1 : h[a]++;
if (h[a] >= a && a > answer) {
answer = a;
}
});
console.log(answer);
=========================================================
- для данной последовательно будет ответ 7
Вторая задача: проверь, что выдаст твой алгоритм на последовательность [8, 8, 8, 8, 8, 8, 8] (семь восьмерок) :)
@@DmitryPatrushev-wd5fq Ага не подумал. Тогда все таки через создание массива и его сортировку
const articles = [8, 8, 8, 8, 8, 8, 8];
let h = 0;
articles.sort((a, b) => b - a);
articles.forEach(e => {
h = articles.findIndex((e, i) => i + 1 > e);
if (h === -1) {
h = articles.length;
};
});
console.log(h);
// 7
зачем эту сортировку подсчетом было делать? Вроде можно просто начать с h=5, дальше пойти по массиву и декрементить h если nums[i] < h. Но это я придумал только на примере инпута из видео автора
отсортируем в обратном порядке, а потом пойдем считать так же в обратном порядке и сравнивать позицию элемента и его значение. Вернем предыдущий, от которого меньше. Если статьи пишет Донцова, то рещение из видео не подходит
в 3м собесе была задача на 3 лошади - это тебе даны 25 лошадей и стадион, где одновременно может бегать 5 лошадей, сколько нужно сделать забегов, чтобы выбрать 3 самые быстрые лошади)) недавно ее решал
Прикольная. Сначала хочется ответить 9 - не сразу очевидно, что 7)
Ну вообще каждая лошадь бежит н времени, значит надо всего лишь 5 забегов. Из 5 забегов берешь первые места и берешь три лучших время забега.
@@DrampiRUS Не сработает :) Не учитываешь, что не первые места какого-либо забега могут быть быстрее первых мест других забегов
а секундомер есть? =)
@@RealMrPitsa нет) было бы слишком просто
с последним кодом может не сильно уменьшится время, но по идее мы же знаем сколько у нас 6+ элементов и по сути их можно не проверят а начинать сразу с n - 1 - (кол 6+) и h-индекс = кол 6+
Что-то не сходится. Каким образом в массиве из "n" элементов, диапазон значений может быть больше "n", он всегда будет "n" или меньше, т.е. всегда нужно использовать сортировку подсчетом и зачем изобретали другие сортировки непонятно.
Моё решение такое. Сортируем массив O(NlogN), бежим по индексам, берём разницу между размером массива и текущим индексом (кол-во оставшихся статей), бежим до тех пор, пока кол-во оставшихся статей >= значению по текущему индексу
Time: O(N logN)
Space: O(1)
Да, действительно, справа-налево более красиво выглядит чем моё
4:09 'citations' нужно заменить на 'quotations', пишем readable code.
Очень рад за Сашу что он устроился в Google.
Понятно одно, по этим собеседованиям ищут математиков. Главное чтобы задачи потом были не из разряда CRUD
Именно такие и будут. На собесе решаешь на нобелевку, по факту кнопки расставляешь
Скорее на усидчивость. Большинство кто проходит успешно эти собесы не придумывают решения задач на ходу, они их либо уже прорешали, либо решали аналогичные и знают принцип.
На самом деле просто долбежка задач на литкоде) ищут они чуваков кто будет писать адекватный код который обработает миллиарды записей за адекватное время. У нас в СНГ таких нагрузок особо нет, по этому с этой точки зрения у нас проще собесы
@@inoob2624 неа не сходится. Архитектура и математика не одно и тоже. Одно дело сделать СУБД с нуля, которое будет миллионы записей в секунду обрабатывать. Другое дело применить правильные паттерны, подобрать подходящий яп, инфраструктуру, наладить работу в команде. После этого нормальный код и джун накидает по шаблону 😅
в 1 задаче можно также решить через прибавление на отрезке префиксными суммами
на питоне
a = sorted([3, 0, 6, 1, 5])
for i in range(len(a))[::-1]:
if i+1 >= a[i]:
print(a[i])
break
Сколько после налогов останется? В Израиле тоже можно такую зарплату сеньору получить, только от нее 42% заберет социалистическое правительство.
Побольше подобных видео)
Уважаемый, у вам вопрос есть. Правда, что в IT действует принцип "Дорогу осилит идущий" ?
Мне нравится решать задчи визуальным способом
Можешь выложить побольше видео с решениями задач? Интересно 😅
При входящих статьях думаю двусвязный список?
Если меньше влево вставлять, если больше вправо.
А дальше справа налево бежим.
Не легче в каунт записывать на первом цыкле в каждый индекс сколько раз ты встретил число такое же или больше , а во втором цикле вернуть найбольший индекс каунт в котором записанное число равно или больше индекса
Можно построить дерево отрезков на сумму и добавление значения, потом при добавлении нового числа будем прибалять 1 в дереве(как в массиве при сортировке подсчетом) и бинарным поиском подбирать h и проверять можем мы его получить или нет. Ели сумма с индекса n - h +- 1 до n >= h, то сдвигаем левую границу бин поиска , иначе правую и когда отрезок станет равен 1 это наш ответ
На второй допвопрос. Следует проверять каждое новое выпадающее значение на величину относительно эйч_индекса. Если оно больше или равно эйч_индексу, то эйч_индекс инкриминируется. Положить эйч_индекс изначально равным нулю.
последовательно приходят 1 2 3 4 5. по вашему решению получится инкремент на каждое число и на выходе 5, хотя должно быть 3.
@@TheSanSanch мммда
Так, я не программист, но вопрос такой, мы получаем в решении Саши для заполнения массива вложенные циклы, разве там не будет сложность O(n*m), а не O(n)?
Нет, суммарное кол-во итераций будет гарантировано равно длине массива
Да, цикла два, но во втором цикле количество итераций всегда будет строькотде сколько чисел всего изначально. То есть это фактически 2*n, а не n ^2
Быстрее линии только логарифм (ну и константа), значит бин поиском. Т.е. смотрим на средний элемент массива - а не больше ли он, чем длина половины массива. Если да, ставим h-index равным половине длины массива и идёт в левый полумассив проверить тоже самое. В общем, бинпоиск. Основная сложность - всякие граничные условия правильно учесть
Для второй - нам пофиг на значения
бин поиск только для отсортированного списка подойдёт
@@ic6406 как раз как в первом допвопросе в конце видео
Ещё есть ln(n)
Yeeeaah! My guy is back!
Прикольно! Делитесь интересными задачками с реальных собеседований, Саша Лукин.
Суперценные вести - [ценные] и технологически-научно (для изучения программирования), и рыночно-экономически (для изучения рынка работодателей).
Подписка, мы следим за вашими выпусками
Спасибо за видео! Зарплата указана до вычета налогов?
Hash set (multi):
Проходясь по массиву записываем подходящие числа для h-index, пока не наберем h штук. O(1)
h-index увеличиваем и удаляем все меньшие h числа из сета O(1), эти числа всегда будут равны h - 1
Time = Memory = O(n)
А затем, этот вариант легко превращается в решение, где цифры подаются по одной:
```golang
func hIndex(citations []int) int {
m := make(map[int]int)
hMap := func(input int) int {
m[input]++
i, h, max := 0, len(m), 0
for ; i
Тем, кто решил обе доп.задачи за O(log n), предлагаю чуть-чуть усложнить задачу, приблизив ее к реальности. В жизни же сначала статью пишут, потом она годами набирает ссылки.
Итак: в программу идет вперемежку поток сообщений вида "Написана новая статья" (у новой статьи - 0 ссылок) или "у статьи 232 добавилось 11 ссылок". В любой момент у программы можно спросить индекс Хирша ученого. Естественно, все 3 эти операции желательно проделывать за O(log n).
Первую задачу можно еще решить бинпоиском по ответу, типо перебирать ответ от 0 до n за logn, и проверять для каждого предполагаемого ответа подойдет ли он за n, таким образом мы сможем найти ответ за n log n.
Я пока не знаю алгоритмов, так что первую задачу решил на JS с помощью цикла while и вызовом filter на каждой итерации
В реальных интервью ограничения накладываются не только на комплексити, но и на потребляемую память.
Через хэш таблицу , в значение добавляем для каждого индекса
Вместо двух первых действий в 3-ем решении можно как в JS создать мапу:
const a = {};
for (let i = 0; i < citations.length; i++) {
if (!a[i]) {
a[i = 1];
} else {
a[i]++;
}
}
сounts получится быстрее. Или нет?
2 вариант рассмотрен не верно. Если попадется несколько одинаковых ссылок то озвученный подсчет индекса не корректно отработает😅
оптимизировать задачу для случая 5 статей по определению странно.
еще не досмотрел, но не очень понимаю, зачем из count на 9.36 создавать сортированый массив cotations, если достаточно пройтись в обратном порядке по массиву count, cумируя count-ы? типа
index == valuesum?
valuesum += valuesum + count[index ]
count[] сортировать не нужно было, нужен был просто второй цикл по count[] в обратном порядке for (q = 0, h = n; h >= 0; h--), суммируя значения массива q += count[h] до первого элемента для которого выполняется q >= h. h при этом будет h-индексом просто по определению.
В ппоследнем варианте решения сложность разве не O(n^2)?! Там вложеный цикл ведь
Задача койфовая, особенно с доп. вопросами! Спасибо за контент
Жалко что не сказал про ограничения на n вначале, сортировка посчетом это круто, но массив интов на 10^8 тяжеловато заводить, по памяти будет же O(n)
так это ограничение искуственное. большие числа редуцируются к N+1 ибо от этого результат не исказится. 1000 можно свести к N+1. Для индекса цитирования 1000 мы не наберем 1000 статей в 5 элементном массиве. также как и для 5+1 поэтому смело меням 1000 на 5+1. Если я все правильно понял.
А если изначально предположить, что hindex равен 5 и потом пробежаться по массиву не сортирую, а просто проверяя. Если значение меньше пяти, то потенциальный индекс стал 4, если нет остался пять. И так уменьшать или оставлять индекс без изменения до самого конца. Вроде должно получиться.
1 цитирование одной работы = 1 или более
2 цитирования двух работ = 4 или более
3 цитирования трёх работ = 9 или более
4 цитирования четырёх работ = 16 или более
h_indicies = [0, 1, 2, 3, 4]
study = [3, 0, 6, 1, 5]
if sum(study) >= 16:
print(f'The H index is {h_indicies[4]}')
elif sum(study) >= 9 and sum(study) < 16:
print(f'The H index is {h_indicies[3]}')
elif sum(study) >= 4 and sum(study) < 9:
print(f'The H index is {h_indicies[2]}')
elif sum(study) >= 1 and sum(study) < 4:
print(f'The H index is {h_indicies[1]}')
else:
print("Can't calculate the H index")
почему не исключить 0 из массива? нас же не интересуют статьи без цитирований?
первая задача вот так
const articles = [3, 0, 6, 1, 5];
articles.sort((a, b) => b - a)
for (let i = 0; i < articles.length; i++) {
if (i + 1 > articles[i]) {
console.log(i);
break;
}
}
Отсортированный массив быстрее линейного времени можно наверное, только если делить список пополам?
Допустим у нас 1000 статей. Берем сразу индекс по середине т.е. 500(порядковый номер) и сравниваем его с 500(h_index). Если он меньше, берем оставшуюся правую часть и также делим пополам, т.е. берем уже индекс 250(порядковый номер) и сравниваем с 250(h_index). Допустим он тоже меньше. Опять берем правую часть. Индекс 125 сравниваем с 125. Допустим опять меньше. Берем опять правую часть, сравниваем с 62(порядковый номер) и пусть тут уже будет значение больше 62(h_index), тогда берем левую часть и ее середину, со значением 93. сравниваем с 93, допустим опять меньше, берем снова середину между 93 и 62. Это 78 значение, сравниваем его с 78 (h_index) и допустим значение меньше, тогда берем середину между 78 и 62, это значение 70 и сравниваем его с 70 (h_index). Опять меньше, берем число между 70 и 62, это 66 сравниваем с 66, меньше. Берем между 62 и 66, это 64. Сравниваем, опять меньше. И остается только 63, проверяем его, если 63 >= 63(h_index), то ответ будет 63, иначе ответ 62.
Метод поиска вроде называется как разделяй и властвуй, но это не точно. И интересно узнать, что может быть быстрее этого... По сути из 1000 значений я нашел ответ за 11 итераций и это рассмотрен худший случай.
Это вроде будет log n, поправьте если ошибаюсь.
Да, сработает.
Вариант решения первоначальной задачи:
Сортируем массив подсчётом, параллельно считая общее значение всех элементов (все значения большие чем длины массива считая как его длину)
Затем находим среднее арифметическое значений и переходим к элементу с индексом равным среднему арифметическому.
Если удовлетворяет h, то проверяем h+1 и тд. иначе проверяем h-1 и тд.
В худшем случае будет O(n), но в остальных должно быть чуть быстрее, наверное😅
Под "удовлетворяет h" подразумевается сравнение значение элемента массива под номером среднего арифметического со средним арифметическим. Если оно >= то удовлетворяет, иначе неудовлетворяет
При маленьком значении n, O(n) и O(n*logn) тоже не будут сильно отличаться. Неочевидно будет ли сортировка методом подсчета быстрее чем обычная сортировка. для массива из n элементов, значения которых могут быть 0 до n, при средних значениях n.
к тому же для сортировки подсчетом надо выделять и освобождать память. А это реально операции с неведомой трудоемкостью, зависящей от фрагментации памяти.
@@MichailLLevin между затратами памяти и лучшей скорости в современном мире, скорость всегда будет стоять на 1 месте
Задача собеседующего определить обладает ли кандидат минимальными знаниями, что необходимы для работы, а не может ли он решать искуственные олимпиадные задачи в неествественных условиях.
Я б искал максимальное из элементов от 0 по N-i. И сравнивал бы его значение с i. Как только значение меньше или равно i ответ получен. До O(n) не додумался бы точно)
Первая же мысль: отсортировать массив и пройтись бинарным поиском или типа того