Собеседование на Backend в Лондон за $12.000 в Месяц
Вставка
- Опубліковано 24 тра 2023
- Разбираем задачу из собеседования на позицию Backend Software Developer в Goldman Sachs. Это банк у которого есть куча офисов по всему миру. Один из крупных находится здесь в Лондоне.
Средняя зарплата на позицию с 3 годами опыта работы - 12.000 долларов в месяц.
Задача на Leetcode: leetcode.com/problems/h-index...
Первый дополнительный вопрос: leetcode.com/problems/h-index...
Пост на литкоде: leetcode.com/discuss/intervie...
Сайт по зарплатам: www.levels.fyi/companies/gold...
Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin
Так, у нас собеседование. Вам необходимо решить 10 алгоритмических задач и 10 задач на логику, рассказать как работают алгоритм A*, красно-чёрные деревья, написать функцию извлечения корня без sqrt, ...
Вы отлично справились с собеседованием, вы приняты! Ура! Босс, я готов начинать, какие у нас задачи? Там в юай надо 10 кнопок добавить, одну сделать красной, приступайте
По крайней мере слово с корнем «красн» встретилось и на собеседовании и в реальной работе. Это уже что-то!
За $200к в год можно и кнопку покрасить 😀
@@algoseekee это точно, люди за 200 долларов красят заборы, а тут за 200к какую-то кнопку покрасить
А вот Вам реальность, а не реклама курсов и больших зарплат. Вам придётся тягаться с молодыми людьми с профильным образованием (спойлер - это бесполезно) и вы будете получать в два раза меньше чем они и они вас потом могут оптимизировать. К тому же тот факт что работу можно делать удаленно это огромный минус а не плюс, вас могут заменить в любой момент или дать пинка под зад, и на основании этого превратить в раба на галере. Работа программистом это постоянный стресс потому что каждый день новые задачи в половине случаев которые ещё никто не решал, а в каком нибудь Яндексе которые в 95% случаев никто не решал! Задачи эти надо решать вовремя т.к дед-лайны и неустойки по бизнесу никто не отменял и зачастую приходится рапрощаться с личной жизнью и сном в поисках решения. Это вам не оператор станка с ЧПУ где заранее известно как делать деталь и сколько времени уходит на её изготовление.
@@alexsmirniy Не знаю, у меня никакого стресса нету. Решаю столько времени, сколько мне потребуется, а замены это скорее в европейских странах, в РФ законодательно человека сложно уволить, а нового искать ещё сложнее
Спасибо большое за то что делаешь. Продолжай дальше, а мы с удовольствием будем смотреть)
Первая мысль была - решить задачу с сортировкой, как во втором способе. Посмотрев видео до конца понял: Я НЕ УЕДУ ЖИТЬ В ЛОНДОН....
@@ez4sayk сколько ты прошел собесов в Гугл, умник? Это сидя на диване она легкая (хотя на литкоде она Medium).
Тут очень важен опыт решения алгоритмических задач. Чем больше вы решите, тем проще будет решать новые. Это задача, например, достаточно типовая.
"Посмотрев видео до конца дня понял"
мораль: не принимай решения вечером, утром - ты решился бы уехать жить в Лондон =)
Такого канала не видел вообще. Просто бомба
низкий поклон за ваш труд, хоть я ничего не понял , было очень интересно. Я сам являюсь мидл+ дата аналитиком в одной международной компании, но очень хотел бы перейти в МААНГ компанию. Надеюсь ваши видео помогут)
отличный разбор, побольше бы таких
Для решения с непрерывным потоком поступающих данных можно добавить второй массив, с элементами уже участвовавшими в подсчете h-index, и при последующем добавление элемента, удалять не подходящие элементы. Те при каждом новом n элементе, алгоритм будет бегать по дополнительному массиву из h+1 элементов.
Клас, выходишь на новый уровень!
Если массив отсортирован, можно двоичным поиском искать, число из массива, которое больше или равно своего индекса + 1, если индекс считать справа и расположенным максимально к левому концу. Т.е. сначала в центр посмотреть, потом, если нашли такое число, сдвинутся на четверть в лево и т.д.
Sus 😳
Саша спасибо за такие видео, коротко и по дело, а главное объяснения решений очень понятны и хорошо разжеванны.
Может запишешь видео о тонкостях работы в лондоне, какие часть зп удерживается налогом , про саму жизнь в Лондоне и т.п.
Ага, думаю такие видео сделать
Думаю, что 2 и 3 этап можно заменить одним. Можно бежать справа налево добавляя к сумме значения, а когда сумма будет больше или равна индексу на котором находится цикл возращать это число
Я думаю он разделил для наглядности
Хорошая мысль! Алгоритм будет быстрее, но сложность этого не покажет 😄
Вот я также для себя решил эту задачу и удивился когда в видео предложили сформировать отсортированный массив, но может и правда для наглядности.
Спасибо за записи! ٩(｡•́‿•̀｡)۶
Спасибо Саша за видео, рад что ты вернулся! ❤ Видео можно проще делать для монтирования, главное наличие! Интересно что на leetcode полно задач, но смотреть видео гораздо интересней
смотреть не мешки ворочать :)
@@andreypopov6166 можно чередовать просмотр с ворочанием мешков, я всегда так делаю =)
(ну, правда, не мешки - а так, спортивный упражнения всякие)
Интересная задачка, спасибо. Только не вижу необходимости после того, как есть массив вхождений, еще раз алоцировать отсортированный массив, вместо этого можно в обратном порядке пробежаться по массиву вхождений, складывая его значения до тех пор, пока агрегированная сумма не догонит индекс.
Можешь выложить побольше видео с решениями задач? Интересно 😅
Yeeeaah! My guy is back!
Я сидел, думал, что как-то надо плясать от размера массива. Но чтобы так... Круто, в очередной раз кайфанул, спасибо
Класс, хочу ещё видео разборы пожалуйста
Решил без этой вашей сортировки, про использовав мап. Довольно простая задача.
@sashalukin А для последнего цикла мы же можем использовать двоичный поиск? Хотя на сложность алгоритма это не повлияет верно?
Прикольно! Делитесь интересными задачками с реальных собеседований, Саша Лукин.
Суперценные вести - [ценные] и технологически-научно (для изучения программирования), и рыночно-экономически (для изучения рынка работодателей).
Подписка, мы следим за вашими выпусками
Побольше подобных видео)
Задача койфовая, особенно с доп. вопросами! Спасибо за контент
Насчет первого вопроса дополнительного. Я бы использовал бинарный поиск. Например [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)
Как я понял 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)
Возможно это решение не оптимально.
Офигеть мне прям сразу идея решения пришла, я даже не думал почти, я удивлен
Спасибо за видео! Зарплата указана до вычета налогов?
Первое решение, которое пришло в голову для 1-ой задачи. можно двигаться от числа h, попутно сокращая его. Берём h-индекс и начинаем линейно пробегать по элементам, попутно удаляя их из масива, если они подходят под условие, складывая эти же элементы в новую структуру данных. В том случае, если у нас условие не выполнилось, пробегаем снова по массиву, но в нём уже будет меньше элементов, добавляем их в структуру, где лежат элементы, подходящие под условие на этом цикле h + 1. И так до момента, пока мы не найдём удовлетворяющее условие. То есть, мы на каждом этапе сокращаем изначальный массив.
решение на вторую, о котором я в начале подумал наверно не хуже, скажи свое мнение:
возможно напишу с ошибками, не в редакторе все таки, понадобится только цикл в цикле и две переменных
function Fn() {
let i = 1, count = 1
while (i {
if (item > i) {
count--;
if (count 0) {
// тут невыполнилось условие, значит в предыдущей итерации был нужный результат:
return i - 1;
}
})
}
}
Fn();
я пока в тему О(n) не вникал, но думаю 2 переменных это хорошее решение
Спасибо, прикольная задачка. Решил примерно вторым способом.
Любопытно, что этот h index у учёного будет 0, если у него мало статей, но их все хорошо цитируют :)
При наличии цитирований h-индекс априори не может быть нулевым
@@SayXaNow да, верно
Допустим 2 статьи, у каждой по 1000 ссылок. Получается h только 2.
Какие же все таки есть умные люди,говорила же мама Учись сынок ,не прогуливай уроки )))
По сути 27 задача из ЕГЭ. А последний вопрос прямо наводит на решение вообще в один цикл :) Спасибо за интересные задачи.
Один цикл не значит что это максимально быстро. Если поддерживать какую то структуру в упорядочении виде это будет сложно log(n) на каждую вставку
@@Gribozhuy Я про то, что можно совместить подсчет статей с определенным цитированием и сразу же считать индекс, без повторного обхода массива количества цитирований с конца для поиска индекса цитирования. Опять же, смотрим ЕГЭ 27, там много подобных задач.
В оригинальном решении не нужен шаг с перезаписыванием массива, достаточно идти по k,v мапы в обратном порядке
Решение - бин. поиск по ответу. Мы за линию от количества проверяем любое конкретное h, и при том очевидно, что если h = h0 подходит, то подходят и меньшие, а если не подходят, то не подходят и большие. В итоге O(n*log(max-min)), либо, если макс и мин сильно отличаются, можно заметить ( в коде тупо заифать), что h от 0 до n точно, и в итоге то же самое но за O(n*log(n))
Можно построить дерево отрезков на сумму и добавление значения, потом при добавлении нового числа будем прибалять 1 в дереве(как в массиве при сортировке подсчетом) и бинарным поиском подбирать h и проверять можем мы его получить или нет. Ели сумма с индекса n - h +- 1 до n >= h, то сдвигаем левую границу бин поиска , иначе правую и когда отрезок станет равен 1 это наш ответ
Задача №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 - у нас не отсортированная последовательность
@@PavelIvanovskii 10:16 а если условие послушать внимательно?
супер! спасибо за пояснения и код.
Та же мысль была, отсортировать. бинарным поиском добить)
добавление в отсортированный массив - уже O(n). Погуглите алгоритм частичной сортировки, он же nth element, он есть готовый в STL. Суть в том, что мы просим поставить n-q элемент на то место, где бы он стоял, если бы массив был отсортированный, а также переместить элементы, которые больше или указанного вверх, которые меньше или равны - вниз. По реализации - похоже на qsort, но в рекурсии смотрим не на обе половинки, а только на ту, где наш элемент. В итоге - O(n).
У нас индекс может или увеличиться на 1 или остаться прежним. Значит, достаточно добавить новую статью в массив и выполнить nth element для индекса на 1 больше старого и проверить этот элемент. Итого, O(log n) на шаг.
2 вариант рассмотрен не верно. Если попадется несколько одинаковых ссылок то озвученный подсчет индекса не корректно отработает😅
задача про 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, после того как досмотрел - понял слабые места в своем коде, спасибо!
Первая задача с помощью 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))
в 1 задаче можно также решить через прибавление на отрезке префиксными суммами
Второе решение на питоне, только вместо сортировки я использовал преобразование листа во множество и обратно, и т.о. мы получаем отсортированный массив из уникальных элементов:
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))
Мне нравится решать задчи визуальным способом
В третьем способе решения ведь необязательно после подсчёта элементов снова записывать их в массив. Можно массив подсчета пройти справа налево до момента пока сумма значений пройденных элементов массива не станет больше или равна индеску текущего элемента. Так как он начинается с 0, то даже n-1 делать не нужно.
Вместо двух первых действий в 3-ем решении можно как в JS создать мапу:
const a = {};
for (let i = 0; i < citations.length; i++) {
if (!a[i]) {
a[i = 1];
} else {
a[i]++;
}
}
сounts получится быстрее. Или нет?
У меня первая мысль была после сортировки, это заменить, что полностью сортировать массив не нужно. За O(n) в данном массиве находится медиана и разбивается массив на две части. Если медиана больше, чем половина от размера массива (грубо говоря n/2), то индекс Хирша по крайней мере n/2 и не зависит от значений, больших чем медиана. Если меньше, чем n/2, то индекс Хирша меньше, чем n/2, и нас интересуют только числа, большие медианы. После этого мы находим медиану в нужной нам половине и т.д. Весь алгоритм будет работать за O(n).
Если вместо медианы использовать случайный элемент, то алгоритм получится проще и в среднем будет также работать за O(n), но хочется все-таки детерминированно.
Нахождение медианы детерминированно за O(n) это отдельный вопрос, алгоритм есть.
В целом на придумывание этого решения потратил минуты 2-3, но вот объяснить его за 20 минут может быть квестом.
Тоже так подумал на паузе. По сути квиксорт, но по одной ветке.
1. бинарный поиск. O(log n)
2. nth_element (он же в других источниках partitial sort). держим весь массив и последний посчитанный индекс Херша. Если новая статья улучшила индекс - она могла улучшить только на 1, ухудшить вообще нельзя. Значит, добавляем статью в хвост массива и делаем nth_element для номера на 1 больше старого индекса. Проверяем указанное место - если проверка прошла, индекс увеличился на 1, если нет - остался прежний. O(log n) на каждый шаг.
Второй доп. вопрос: нужна куча, чтобы на верху был минимальный элемент, и если входящие число меньше h индекса, его просто откидываем, если нет- добавляем в кучу, пробуем увеличить h, смотрим, сколько элементов придется выкинуть. Куча может повторяющиеся элементы.
и какая трудоемкость с учетом того, что вы не знаете, сколько придется отбрасывать на каждом шагу? Там же по одному элементу не определить.
Что-то не сходится. Каким образом в массиве из "n" элементов, диапазон значений может быть больше "n", он всегда будет "n" или меньше, т.е. всегда нужно использовать сортировку подсчетом и зачем изобретали другие сортировки непонятно.
массив citations совершенно необязательно переписывать - для решения достаточно заполненного массива count. можно взять его последний элемент и сравнить с индексом - если он больше то решение найдено. если меньше то мы прибавляем значение этого элемента к предыдущему и так пока не найдем или не дойдем до индекса -1. аналогично решается и вторая допзадача, но вместо массива count нужно хранить какой-нть map где ключ - значение из массива citation & value - число таких элементов + нужно наибольшее значение чтобы начинать поиск по этому словарю с него
по первой задаче решение такое увидел ,
циклом проходим каждое число
в итерации выполняем второй цикл от 1 до текущего значения числа
формируем выходной массив где индекс итерации является индексом выходного массива и просто прибавляем к значению под этим индексом единицу
в итоге на выходе получим массив с нашими H индексами ,
останется найти максимальный H индекс , просто перебираем массив с H индексами и по условию значение массива больше или равно текущему индексу , если да то переопределяем число H индекса
по итогу возвращаем переменную с H индексом из цикла
а посмотрел и понял что можно второй цикл ограничить длиной входного массива , но тогда количество итераций будет где то в длину основного массива помноженное на количество интераций цикла до длины первого .
Для решения доп вопроса подойдет использование дерева поиска с поддержкой размера поддерева. Но я не тестил. Чисто на вскидку
на питоне
a = sorted([3, 0, 6, 1, 5])
for i in range(len(a))[::-1]:
if i+1 >= a[i]:
print(a[i])
break
В последнем решении не нужен второй шаг. проще уже идти по массиву от последнего индекса к первому и смотреть какое число записано (и инкрементировать общий счетчик) если в 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+.
Уважаемый, у вам вопрос есть. Правда, что в IT действует принцип "Дорогу осилит идущий" ?
После того как мы посчитали можно не сортировать, а работать непосредственно с массивом подсчитанных значений. Идём с конца и если значение больше или равно индексу, то возвращаем его, если нет , то увеличиваем следующее значение (индекс - 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]
}
}
еще не досмотрел, но не очень понимаю, зачем из count на 9.36 создавать сортированый массив cotations, если достаточно пройтись в обратном порядке по массиву count, cумируя count-ы? типа
index == valuesum?
valuesum += valuesum + count[index ]
Итерируемся по массиву начиная с 1 индекса
Запоминаем нулевой индекс - В данном случае 3 - пусть будет переменная x и вторая такая же y
Далее сравниваем y и все последующие элементы
Если i >=y то x+=1 иначе x-=1
Return x
Для массива 1, 1, 1, 1, 1 не работает.
Через хэш таблицу , в значение добавляем для каждого индекса
lst = sorted(lst)
begin = 0
end = len(lst)-1
while begin +1 < end:
i = begin + (end-begin) // 2
if lst[i]
Пришел в комментарии написать, что неплохо было бы ссылку на литкод с этой задачей дать, а она итак в описании есть :)
Я пока не знаю алгоритмов, так что первую задачу решил на JS с помощью цикла while и вызовом filter на каждой итерации
Лютая задачка
Забавно, мне как раз финальный метод пришёл в голову , но я подумал что как-то просто для этого канала и решил что не то😅
А если изначально предположить, что hindex равен 5 и потом пробежаться по массиву не сортирую, а просто проверяя. Если значение меньше пяти, то потенциальный индекс стал 4, если нет остался пять. И так уменьшать или оставлять индекс без изменения до самого конца. Вроде должно получиться.
При входящих статьях думаю двусвязный список?
Если меньше влево вставлять, если больше вправо.
А дальше справа налево бежим.
вместо 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;
};
Можно решить ещё быстрее и проще (я про основное решение а не про дополнительные вопросы), тоже за 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 Не, виноват, херню придумал
count[] сортировать не нужно было, нужен был просто второй цикл по count[] в обратном порядке for (q = 0, h = n; h >= 0; h--), суммируя значения массива q += count[h] до первого элемента для которого выполняется q >= h. h при этом будет h-индексом просто по определению.
с последним кодом может не сильно уменьшится время, но по идее мы же знаем сколько у нас 6+ элементов и по сути их можно не проверят а начинать сразу с n - 1 - (кол 6+) и h-индекс = кол 6+
У меня есть вариант для решения с отсортированным массивом со сложностью 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. Я не считал, просто построил графики в десмосе)
Я хочу в дальнейшем развиваться в области в IT,где мне учиться,может курсы какие либо или IT школы,подскадите пожалуйста где получать знания
не понял сложности - мои обычные будни... и сразу оптимизируем код с учетом вероятности нормального распределения цитирования.
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) Если приходит меньше или равный Н-индекса - игнорируешь, иначе сохраняешь в карту и проверяешь сумму количеств чисел больше Н-индекса (сумма всех исключив равного Н-индексу).
1.1) Если сумма больше или равна - увеличивашь Н-индекс на 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
А как насчет того чтобы использовать HashMap ?
Первую задачу можно еще решить бинпоиском по ответу, типо перебирать ответ от 0 до n за logn, и проверять для каждого предполагаемого ответа подойдет ли он за n, таким образом мы сможем найти ответ за n log n.
Классно!!! Подскажи плиз книги, материалы, на основе которых ты прокачивался по алгоритмам и не только
Моё решение такое. Сортируем массив O(NlogN), бежим по индексам, берём разницу между размером массива и текущим индексом (кол-во оставшихся статей), бежим до тех пор, пока кол-во оставшихся статей >= значению по текущему индексу
Time: O(N logN)
Space: O(1)
Да, действительно, справа-налево более красиво выглядит чем моё
При маленьком значении n, O(n) и O(n*logn) тоже не будут сильно отличаться. Неочевидно будет ли сортировка методом подсчета быстрее чем обычная сортировка. для массива из n элементов, значения которых могут быть 0 до n, при средних значениях n.
к тому же для сортировки подсчетом надо выделять и освобождать память. А это реально операции с неведомой трудоемкостью, зависящей от фрагментации памяти.
@@MichailLLevin между затратами памяти и лучшей скорости в современном мире, скорость всегда будет стоять на 1 месте
Для бекенда обязателен Java?
Очень рад за Сашу что он устроился в Google.
Понятно одно, по этим собеседованиям ищут математиков. Главное чтобы задачи потом были не из разряда CRUD
Именно такие и будут. На собесе решаешь на нобелевку, по факту кнопки расставляешь
Скорее на усидчивость. Большинство кто проходит успешно эти собесы не придумывают решения задач на ходу, они их либо уже прорешали, либо решали аналогичные и знают принцип.
На самом деле просто долбежка задач на литкоде) ищут они чуваков кто будет писать адекватный код который обработает миллиарды записей за адекватное время. У нас в СНГ таких нагрузок особо нет, по этому с этой точки зрения у нас проще собесы
@@inoob2624 неа не сходится. Архитектура и математика не одно и тоже. Одно дело сделать СУБД с нуля, которое будет миллионы записей в секунду обрабатывать. Другое дело применить правильные паттерны, подобрать подходящий яп, инфраструктуру, наладить работу в команде. После этого нормальный код и джун накидает по шаблону 😅
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
4:09 'citations' нужно заменить на 'quotations', пишем readable code.
ЗП на таких сайтах обычно в gross пишут?
Саня, как ты английский учил ?
Быстрее линии только логарифм (ну и константа), значит бин поиском. Т.е. смотрим на средний элемент массива - а не больше ли он, чем длина половины массива. Если да, ставим h-index равным половине длины массива и идёт в левый полумассив проверить тоже самое. В общем, бинпоиск. Основная сложность - всякие граничные условия правильно учесть
Для второй - нам пофиг на значения
бин поиск только для отсортированного списка подойдёт
@@ic6406 как раз как в первом допвопросе в конце видео
Ещё есть ln(n)
На второй допвопрос. Следует проверять каждое новое выпадающее значение на величину относительно эйч_индекса. Если оно больше или равно эйч_индексу, то эйч_индекс инкриминируется. Положить эйч_индекс изначально равным нулю.
последовательно приходят 1 2 3 4 5. по вашему решению получится инкремент на каждое число и на выходе 5, хотя должно быть 3.
@@TheSanSanch мммда
Не легче в каунт записывать на первом цыкле в каждый индекс сколько раз ты встретил число такое же или больше , а во втором цикле вернуть найбольший индекс каунт в котором записанное число равно или больше индекса
Тем, кто решил обе доп.задачи за O(log n), предлагаю чуть-чуть усложнить задачу, приблизив ее к реальности. В жизни же сначала статью пишут, потом она годами набирает ссылки.
Итак: в программу идет вперемежку поток сообщений вида "Написана новая статья" (у новой статьи - 0 ссылок) или "у статьи 232 добавилось 11 ссылок". В любой момент у программы можно спросить индекс Хирша ученого. Естественно, все 3 эти операции желательно проделывать за O(log n).
Жалко что не сказал про ограничения на n вначале, сортировка посчетом это круто, но массив интов на 10^8 тяжеловато заводить, по памяти будет же O(n)
так это ограничение искуственное. большие числа редуцируются к N+1 ибо от этого результат не исказится. 1000 можно свести к N+1. Для индекса цитирования 1000 мы не наберем 1000 статей в 5 элементном массиве. также как и для 5+1 поэтому смело меням 1000 на 5+1. Если я все правильно понял.
интересно, а эту задачу можно решить через факториал или матричную степень? а как распараллелить эту задачу, если массивов цитирования статей несколько частично-пересекающихся? а как быстро пересчитать индекс Хирша, если добавилось число цитирования одной статьи в массиве? а что если построить дерево или граф, вместо плоского массива? а можно описать это в декларативном или функциональном, вместо императивного, языке программирования? а если БД с индексами вместо массива с сортировкой, и в SQL? а на конечных автоматах? а какая универсальная архитектура нейронных сетей могла бы доучиться до приблизительного решения с приемлемой точностью, начав с полностью необученного состояния?
Так, я не программист, но вопрос такой, мы получаем в решении Саши для заполнения массива вложенные циклы, разве там не будет сложность O(n*m), а не O(n)?
Нет, суммарное кол-во итераций будет гарантировано равно длине массива
Да, цикла два, но во втором цикле количество итераций всегда будет строькотде сколько чисел всего изначально. То есть это фактически 2*n, а не n ^2
Я б искал максимальное из элементов от 0 по N-i. И сравнивал бы его значение с i. Как только значение меньше или равно i ответ получен. До O(n) не додумался бы точно)
Почему мой комментарий с ответом всё время удаляют?
На втором шаге последнего решения массив наполняется с помощью цикла в цикле. Такое дейсвтие не делает сложность O(n^2) ?
Сумма чисел в массиве count всегда равна длине исходного массива, поэтому внутренний цикл не может быть выполнен более n раз.
Если цифры сложить и поделить на количество цифр получится ответ.
Первая же мысль: отсортировать массив и пройтись бинарным поиском или типа того
первая задача вот так
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;
}
}
я не прогер, нифига не понял, но Саша молодец