Собеседование на Backend в Лондон за $12.000 в Месяц

Разбираем задачу из собеседования на позицию 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...

[@sashalukin]

Создал Telegram канал, в котором рассказываю о жизни в Лондоне, работе в Google и подготовке к собеседованиям. Подписывайтесь: t.me/saschalukin

[@ic6406]

Так, у нас собеседование. Вам необходимо решить 10 алгоритмических задач и 10 задач на логику, рассказать как работают алгоритм A*, красно-чёрные деревья, написать функцию извлечения корня без sqrt, ... Вы отлично справились с собеседованием, вы приняты! Ура! Босс, я готов начинать, какие у нас задачи? Там в юай надо 10 кнопок добавить, одну сделать красной, приступайте

[@phat80]

По крайней мере слово с корнем «красн» встретилось и на собеседовании и в реальной работе. Это уже что-то!

[@algoseekee]

За $200к в год можно и кнопку покрасить 😀

[@experimental_microbiology]

@@algoseekee это точно, люди за 200 долларов красят заборы, а тут за 200к какую-то кнопку покрасить

[@alexsmirniy]

А вот Вам реальность, а не реклама курсов и больших зарплат. Вам придётся тягаться с молодыми людьми с профильным образованием (спойлер - это бесполезно) и вы будете получать в два раза меньше чем они и они вас потом могут оптимизировать. К тому же тот факт что работу можно делать удаленно это огромный минус а не плюс, вас могут заменить в любой момент или дать пинка под зад, и на основании этого превратить в раба на галере. Работа программистом это постоянный стресс потому что каждый день новые задачи в половине случаев которые ещё никто не решал, а в каком нибудь Яндексе которые в 95% случаев никто не решал! Задачи эти надо решать вовремя т.к дед-лайны и неустойки по бизнесу никто не отменял и зачастую приходится рапрощаться с личной жизнью и сном в поисках решения. Это вам не оператор станка с ЧПУ где заранее известно как делать деталь и сколько времени уходит на её изготовление.

[@ic6406]

@@alexsmirniy Не знаю, у меня никакого стресса нету. Решаю столько времени, сколько мне потребуется, а замены это скорее в европейских странах, в РФ законодательно человека сложно уволить, а нового искать ещё сложнее

[@hopelesssuprem1867]

Спасибо большое за то что делаешь. Продолжай дальше, а мы с удовольствием будем смотреть)

[@silkcode3178]

Такого канала не видел вообще. Просто бомба

[@galymzhankenesbekov7242]

низкий поклон за ваш труд, хоть я ничего не понял , было очень интересно. Я сам являюсь мидл+ дата аналитиком в одной международной компании, но очень хотел бы перейти в МААНГ компанию. Надеюсь ваши видео помогут)

[@Anton_K15]

Первая мысль была - решить задачу с сортировкой, как во втором способе. Посмотрев видео до конца понял: Я НЕ УЕДУ ЖИТЬ В ЛОНДОН....

[@Gribozhuy]

@@ez4sayk сколько ты прошел собесов в Гугл, умник? Это сидя на диване она легкая (хотя на литкоде она Medium).

[@nikitabeletskii7342]

Тут очень важен опыт решения алгоритмических задач. Чем больше вы решите, тем проще будет решать новые. Это задача, например, достаточно типовая.

[@user-sl4jq9op9l]

"Посмотрев видео до конца дня понял" мораль: не принимай решения вечером, утром - ты решился бы уехать жить в Лондон =)

[@user-ow9ep1rj1f]

отличный разбор, побольше бы таких

[@Santa_murai]

Клас, выходишь на новый уровень!

[@sobirabdulxair9001]

Саша спасибо за такие видео, коротко и по дело, а главное объяснения решений очень понятны и хорошо разжеванны. Может запишешь видео о тонкостях работы в лондоне, какие часть зп удерживается налогом , про саму жизнь в Лондоне и т.п.

[@sashalukin]

Ага, думаю такие видео сделать

[@user-zf9gl8fr5g]

Класс, хочу ещё видео разборы пожалуйста

[@TheChosenOne171]

Yeeeaah! My guy is back!

[@maxjonson9114]

Для решения с непрерывным потоком поступающих данных можно добавить второй массив, с элементами уже участвовавшими в подсчете h-index, и при последующем добавление элемента, удалять не подходящие элементы. Те при каждом новом n элементе, алгоритм будет бегать по дополнительному массиву из h+1 элементов.

[@vacsa]

Спасибо за записи! ٩(｡•́‿•̀｡)۶

[@VasillaRobocraft]

Я сидел, думал, что как-то надо плясать от размера массива. Но чтобы так... Круто, в очередной раз кайфанул, спасибо

[@dmitry7464]

Спасибо Саша за видео, рад что ты вернулся! ❤ Видео можно проще делать для монтирования, главное наличие! Интересно что на leetcode полно задач, но смотреть видео гораздо интересней

[@andreypopov6166]

смотреть не мешки ворочать :)

[@user-sl4jq9op9l]

@@andreypopov6166 можно чередовать просмотр с ворочанием мешков, я всегда так делаю =) (ну, правда, не мешки - а так, спортивный упражнения всякие)

[@user-sl4jq9op9l]

Прикольно! Делитесь интересными задачками с реальных собеседований, Саша Лукин. Суперценные вести - [ценные] и технологически-научно (для изучения программирования), и рыночно-экономически (для изучения рынка работодателей). Подписка, мы следим за вашими выпусками

[@honcharov17]

Побольше подобных видео)

[@user-zg9bv8zh1s]

Можешь выложить побольше видео с решениями задач? Интересно 😅

[@deusexmachine2834]

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

[@ivanovchin]

Офигеть мне прям сразу идея решения пришла, я даже не думал почти, я удивлен

[@timusbelkin]

Если массив отсортирован, можно двоичным поиском искать, число из массива, которое больше или равно своего индекса + 1, если индекс считать справа и расположенным максимально к левому концу. Т.е. сначала в центр посмотреть, потом, если нашли такое число, сдвинутся на четверть в лево и т.д.

[@endlessvd]

Sus 😳

[@RubicsGuide]

По сути 27 задача из ЕГЭ. А последний вопрос прямо наводит на решение вообще в один цикл :) Спасибо за интересные задачи.

[@Gribozhuy]

Один цикл не значит что это максимально быстро. Если поддерживать какую то структуру в упорядочении виде это будет сложно log(n) на каждую вставку

[@RubicsGuide]

@@Gribozhuy Я про то, что можно совместить подсчет статей с определенным цитированием и сразу же считать индекс, без повторного обхода массива количества цитирований с конца для поиска индекса цитирования. Опять же, смотрим ЕГЭ 27, там много подобных задач.

[@andrei_storchous]

Интересная задачка, спасибо. Только не вижу необходимости после того, как есть массив вхождений, еще раз алоцировать отсортированный массив, вместо этого можно в обратном порядке пробежаться по массиву вхождений, складывая его значения до тех пор, пока агрегированная сумма не догонит индекс.

[@verwelius9170]

Думаю, что 2 и 3 этап можно заменить одним. Можно бежать справа налево добавляя к сумме значения, а когда сумма будет больше или равна индексу на котором находится цикл возращать это число

[@fakelIPI]

Я думаю он разделил для наглядности

[@Vitek_23]

Хорошая мысль! Алгоритм будет быстрее, но сложность этого не покажет 😄

[@user-lr1wo1wu2e]

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

[@calmingnaturesounds6761]

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[...] массиве). Меня зовут Лёша и я безработный©

[@tomahawk777]

Какие же все таки есть умные люди,говорила же мама Учись сынок ,не прогуливай уроки )))

[@limbo11111]

Первое решение, которое пришло в голову для 1-ой задачи. можно двигаться от числа h, попутно сокращая его. Берём h-индекс и начинаем линейно пробегать по элементам, попутно удаляя их из масива, если они подходят под условие, складывая эти же элементы в новую структуру данных. В том случае, если у нас условие не выполнилось, пробегаем снова по массиву, но в нём уже будет меньше элементов, добавляем их в структуру, где лежат элементы, подходящие под условие на этом цикле h + 1. И так до момента, пока мы не найдём удовлетворяющее условие. То есть, мы на каждом этапе сокращаем изначальный массив.

[@anubisxayc1286]

Как я понял 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) Возможно это решение не оптимально.

[@YU-tb4st]

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

[@alfeigo]

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

[@alexanderivanov899]

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

[@user-pk7ei5wc6w]

Задача койфовая, особенно с доп. вопросами! Спасибо за контент

[@mikemerinoff]

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

[@ilya5008]

Можно построить дерево отрезков на сумму и добавление значения, потом при добавлении нового числа будем прибалять 1 в дереве(как в массиве при сортировке подсчетом) и бинарным поиском подбирать h и проверять можем мы его получить или нет. Ели сумма с индекса n - h +- 1 до n >= h, то сдвигаем левую границу бин поиска , иначе правую и когда отрезок станет равен 1 это наш ответ

[@Smiranin]

@sashalukin А для последнего цикла мы же можем использовать двоичный поиск? Хотя на сложность алгоритма это не повлияет верно?

[@3ombieautopilot]

Спасибо за видео! Зарплата указана до вычета налогов?

[@user-jp8jl5mg3v]

Решение - бин. поиск по ответу. Мы за линию от количества проверяем любое конкретное h, и при том очевидно, что если h = h0 подходит, то подходят и меньшие, а если не подходят, то не подходят и большие. В итоге O(n*log(max-min)), либо, если макс и мин сильно отличаются, можно заметить ( в коде тупо заифать), что h от 0 до n точно, и в итоге то же самое но за O(n*log(n))

[@user-xz4vj2ne4u]

Для решения доп вопроса подойдет использование дерева поиска с поддержкой размера поддерева. Но я не тестил. Чисто на вскидку

[@vladimirklyavin2254]

В третьем способе решения ведь необязательно после подсчёта элементов снова записывать их в массив. Можно массив подсчета пройти справа налево до момента пока сумма значений пройденных элементов массива не станет больше или равна индеску текущего элемента. Так как он начинается с 0, то даже n-1 делать не нужно.

[@dmitriy4415]

Спасибо, прикольная задачка. Решил примерно вторым способом. Любопытно, что этот h index у учёного будет 0, если у него мало статей, но их все хорошо цитируют :)

[@SayXaNow]

При наличии цитирований h-индекс априори не может быть нулевым

[@dmitriy4415]

@@SayXaNow да, верно Допустим 2 статьи, у каждой по 1000 ссылок. Получается h только 2.

[@timusbelkin]

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

[@MichailLLevin]

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

[@leva529125]

У меня первая мысль была после сортировки, это заменить, что полностью сортировать массив не нужно. За O(n) в данном массиве находится медиана и разбивается массив на две части. Если медиана больше, чем половина от размера массива (грубо говоря n/2), то индекс Хирша по крайней мере n/2 и не зависит от значений, больших чем медиана. Если меньше, чем n/2, то индекс Хирша меньше, чем n/2, и нас интересуют только числа, большие медианы. После этого мы находим медиану в нужной нам половине и т.д. Весь алгоритм будет работать за O(n). Если вместо медианы использовать случайный элемент, то алгоритм получится проще и в среднем будет также работать за O(n), но хочется все-таки детерминированно. Нахождение медианы детерминированно за O(n) это отдельный вопрос, алгоритм есть. В целом на придумывание этого решения потратил минуты 2-3, но вот объяснить его за 20 минут может быть квестом.

[@user-nv5ik7tx9u]

Тоже так подумал на паузе. По сути квиксорт, но по одной ветке.

[@hy_tech_tips]

задача про 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, после того как досмотрел - понял слабые места в своем коде, спасибо!

[@busipac1467]

Первая задача с помощью 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))

[@hopelesssuprem1867]

Второе решение на питоне, только вместо сортировки я использовал преобразование листа во множество и обратно, и т.о. мы получаем отсортированный массив из уникальных элементов: 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))

[@SayXaNow]

Задача №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-ы, поэтому пусть остаётся так.

[@PavelIvanovskii]

Задача №1 - у нас не отсортированная последовательность

[@SayXaNow]

@@PavelIvanovskii 10:16 а если условие послушать внимательно?

[@IlyaShaforostoff]

супер! спасибо за пояснения и код.

[@vladgribennikov]

Та же мысль была, отсортировать. бинарным поиском добить)

[@MichailLLevin]

добавление в отсортированный массив - уже O(n). Погуглите алгоритм частичной сортировки, он же nth element, он есть готовый в STL. Суть в том, что мы просим поставить n-q элемент на то место, где бы он стоял, если бы массив был отсортированный, а также переместить элементы, которые больше или указанного вверх, которые меньше или равны - вниз. По реализации - похоже на qsort, но в рекурсии смотрим не на обе половинки, а только на ту, где наш элемент. В итоге - O(n). У нас индекс может или увеличиться на 1 или остаться прежним. Значит, достаточно добавить новую статью в массив и выполнить nth element для индекса на 1 больше старого и проверить этот элемент. Итого, O(log n) на шаг.

[@pandalove6795]

Насчет первого вопроса дополнительного. Я бы использовал бинарный поиск. Например [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)

[@holy-del]

Пришел в комментарии написать, что неплохо было бы ссылку на литкод с этой задачей дать, а она итак в описании есть :)

[@Sen1ch]

Лютая задачка

[@dpechurkin]

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

[@dpechurkin]

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

[@MichailLLevin]

1. бинарный поиск. O(log n) 2. nth_element (он же в других источниках partitial sort). держим весь массив и последний посчитанный индекс Херша. Если новая статья улучшила индекс - она могла улучшить только на 1, ухудшить вообще нельзя. Значит, добавляем статью в хвост массива и делаем nth_element для номера на 1 больше старого индекса. Проверяем указанное место - если проверка прошла, индекс увеличился на 1, если нет - остался прежний. O(log n) на каждый шаг.

[@latebloomer817]

Я пока не знаю алгоритмов, так что первую задачу решил на JS с помощью цикла while и вызовом filter на каждой итерации

[@trickster-cat]

При входящих статьях думаю двусвязный список? Если меньше влево вставлять, если больше вправо. А дальше справа налево бежим.

[@dmitry7464]

Через хэш таблицу , в значение добавляем для каждого индекса

[@arsenykuz]

У меня есть вариант для решения с отсортированным массивом со сложностью 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. Я не считал, просто построил графики в десмосе)

[@sidhott]

count[] сортировать не нужно было, нужен был просто второй цикл по count[] в обратном порядке for (q = 0, h = n; h >= 0; h--), суммируя значения массива q += count[h] до первого элемента для которого выполняется q >= h. h при этом будет h-индексом просто по определению.

[@user-sk5du7ni2g]

с последним кодом может не сильно уменьшится время, но по идее мы же знаем сколько у нас 6+ элементов и по сути их можно не проверят а начинать сразу с n - 1 - (кол 6+) и h-индекс = кол 6+

[@DrAlan3]

В последнем решении не нужен второй шаг. проще уже идти по массиву от последнего индекса к первому и смотреть какое число записано (и инкрементировать общий счетчик) если в 6 записано 2 значи мало запоминаем 2. если в 5 записано 0 то 2+0=2 это тоже меньше 5 запоминаем 2. если в 4 0 то 2+0=2 и тоде меньше 4. если в 3 - 1 то 2+1 =3 подходит и индекс равен 3

[@OstapP]

Тоже так подумал. Единственное думал не массив количества, а словарь делать, чтобы на нули не тратиться. 2 дополнительный вопрос вы с какой сложностью решили? Я так понимаю там вообще О(1). Добавил к частоте 1 за О(1). Проверил соседа справа в словаре частот за О(1) и все. Только нужно хранить старое h и словарь частот жолжен быть полным а не укророченым типа 6+.

[@redplait5046]

массив citations совершенно необязательно переписывать - для решения достаточно заполненного массива count. можно взять его последний элемент и сравнить с индексом - если он больше то решение найдено. если меньше то мы прибавляем значение этого элемента к предыдущему и так пока не найдем или не дойдем до индекса -1. аналогично решается и вторая допзадача, но вместо массива count нужно хранить какой-нть map где ключ - значение из массива citation & value - число таких элементов + нужно наибольшее значение чтобы начинать поиск по этому словарю с него

[@VasjaG]

Вместо двух первых действий в 3-ем решении можно как в JS создать мапу: const a = {}; for (let i = 0; i < citations.length; i++) { if (!a[i]) { a[i = 1]; } else { a[i]++; } } сounts получится быстрее. Или нет?

[@user-lt7lp3fb6g]

Уважаемый, у вам вопрос есть. Правда, что в IT действует принцип "Дорогу осилит идущий" ?

[@user-wm9ec1wg5c]

lst = sorted(lst) begin = 0 end = len(lst)-1 while begin +1 < end: i = begin + (end-begin) // 2 if lst[i]

[@yurigorohov9575]

на питоне a = sorted([3, 0, 6, 1, 5]) for i in range(len(a))[::-1]: if i+1 >= a[i]: print(a[i]) break

[@Banan904]

Итерируемся по массиву начиная с 1 индекса Запоминаем нулевой индекс - В данном случае 3 - пусть будет переменная x и вторая такая же y Далее сравниваем y и все последующие элементы Если i >=y то x+=1 иначе x-=1 Return x

[@RealMrPitsa]

Для массива 1, 1, 1, 1, 1 не работает.

[@user-oj7ct4lt4x]

На второй допвопрос. Следует проверять каждое новое выпадающее значение на величину относительно эйч_индекса. Если оно больше или равно эйч_индексу, то эйч_индекс инкриминируется. Положить эйч_индекс изначально равным нулю.

[@TheSanSanch]

последовательно приходят 1 2 3 4 5. по вашему решению получится инкремент на каждое число и на выходе 5, хотя должно быть 3.

[@user-oj7ct4lt4x]

@@TheSanSanch мммда

[@d31m07y1988]

Очень рад за Сашу что он устроился в Google. Понятно одно, по этим собеседованиям ищут математиков. Главное чтобы задачи потом были не из разряда CRUD

[@ic6406]

Именно такие и будут. На собесе решаешь на нобелевку, по факту кнопки расставляешь

[@Gribozhuy]

Скорее на усидчивость. Большинство кто проходит успешно эти собесы не придумывают решения задач на ходу, они их либо уже прорешали, либо решали аналогичные и знают принцип.

[@inoob2624]

На самом деле просто долбежка задач на литкоде) ищут они чуваков кто будет писать адекватный код который обработает миллиарды записей за адекватное время. У нас в СНГ таких нагрузок особо нет, по этому с этой точки зрения у нас проще собесы

[@odys-wise]

@@inoob2624 неа не сходится. Архитектура и математика не одно и тоже. Одно дело сделать СУБД с нуля, которое будет миллионы записей в секунду обрабатывать. Другое дело применить правильные паттерны, подобрать подходящий яп, инфраструктуру, наладить работу в команде. После этого нормальный код и джун накидает по шаблону 😅

[@sergeyefimov1692]

Жалко что не сказал про ограничения на n вначале, сортировка посчетом это круто, но массив интов на 10^8 тяжеловато заводить, по памяти будет же O(n)

[@alexnedelin7646]

так это ограничение искуственное. большие числа редуцируются к N+1 ибо от этого результат не исказится. 1000 можно свести к N+1. Для индекса цитирования 1000 мы не наберем 1000 статей в 5 элементном массиве. также как и для 5+1 поэтому смело меням 1000 на 5+1. Если я все правильно понял.

[@MichailLLevin]

Тем, кто решил обе доп.задачи за O(log n), предлагаю чуть-чуть усложнить задачу, приблизив ее к реальности. В жизни же сначала статью пишут, потом она годами набирает ссылки. Итак: в программу идет вперемежку поток сообщений вида "Написана новая статья" (у новой статьи - 0 ссылок) или "у статьи 232 добавилось 11 ссылок". В любой момент у программы можно спросить индекс Хирша ученого. Естественно, все 3 эти операции желательно проделывать за O(log n).

[@the_huge_knight]

4:09 'citations' нужно заменить на 'quotations', пишем readable code.

[@mr.geekey]

вместо 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; };

[@iljakot_tran4131]

еще не досмотрел, но не очень понимаю, зачем из count на 9.36 создавать сортированый массив cotations, если достаточно пройтись в обратном порядке по массиву count, cумируя count-ы? типа index == valuesum? valuesum += valuesum + count[index ]

[@DeniusZZR]

Я б искал максимальное из элементов от 0 по N-i. И сравнивал бы его значение с i. Как только значение меньше или равно i ответ получен. До O(n) не додумался бы точно)

[@AlexDesyatnik]

А если изначально предположить, что hindex равен 5 и потом пробежаться по массиву не сортирую, а просто проверяя. Если значение меньше пяти, то потенциальный индекс стал 4, если нет остался пять. И так уменьшать или оставлять индекс без изменения до самого конца. Вроде должно получиться.

[@user-dk4mm8mt2t]

После того как мы посчитали можно не сортировать, а работать непосредственно с массивом подсчитанных значений. Идём с конца и если значение больше или равно индексу, то возвращаем его, если нет , то увеличиваем следующее значение (индекс - 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] } }

[@dmitriierofeev3588]

Для перой задчи: бинарный поиск нужен (будет 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]

Вторая задача: проверь, что выдаст твой алгоритм на последовательность [8, 8, 8, 8, 8, 8, 8] (семь восьмерок) :)

[@dmitriierofeev3588]

@@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

[@user-qm5fv5by5z]

решение на вторую, о котором я в начале подумал наверно не хуже, скажи свое мнение: возможно напишу с ошибками, не в редакторе все таки, понадобится только цикл в цикле и две переменных function Fn() { let i = 1, count = 1 while (i { if (item > i) { count--; if (count 0) { // тут невыполнилось условие, значит в предыдущей итерации был нужный результат: return i - 1; } }) } } Fn(); я пока в тему О(n) не вникал, но думаю 2 переменных это хорошее решение

[@user-sl4jq9op9l]

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

[@user-dg5sv8el5w]

Можно решить ещё быстрее и проще (я про основное решение а не про дополнительные вопросы), тоже за O(n) но тем не менее быстрее, за один проход. Алгоритм такой, изначально считаем h индекс == n, проходим по массиву если встречаем число меньше h, то декрементируем h (h=h-1) и продолжаем проход с того же числа (т.к. знаем что все числа которые прошли до этого точно больше нового h) таким образом задача решается за один проход без сортировки

[@Fritz131415]

Не получится, проверь на массиве [6, 0, 3, 1, 5] По твоему алгоритму h будет меняться так: 5, 4, 3, 2, 2. А ответом должна быть 3.

[@user-dg5sv8el5w]

​@@Fritz131415 спасибо за ответ, я имел ввиду концепцию, а не готовый алгоритм. В этом случае нужны две переменные. Как бы двусторонний счетчик. И проходя по массиву уменьшаешь максимальный h - встречая меньший элемент, и увеличиваешь минимальный h если встреченный элемент >= минимальному h. Надеюсь понятно объяснил. Возможно нужно будет ещё хранить индекс... Хммм.. стоит сперва попробовать решить на литкоде

[@user-dg5sv8el5w]

@@Fritz131415 Не, виноват, херню придумал

[@HeXataB]

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

[@ic6406]

Моё решение такое. Сортируем массив O(NlogN), бежим по индексам, берём разницу между размером массива и текущим индексом (кол-во оставшихся статей), бежим до тех пор, пока кол-во оставшихся статей >= значению по текущему индексу Time: O(N logN) Space: O(1)

[@ic6406]

Да, действительно, справа-налево более красиво выглядит чем моё

[@Loutistic]

В реальных интервью ограничения накладываются не только на комплексити, но и на потребляемую память.

[@user-sz1jw2wt7v]

При маленьком значении n, O(n) и O(n*logn) тоже не будут сильно отличаться. Неочевидно будет ли сортировка методом подсчета быстрее чем обычная сортировка. для массива из n элементов, значения которых могут быть 0 до n, при средних значениях n.

[@MichailLLevin]

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

[@user-iq9ll8lz9m]

@@MichailLLevin между затратами памяти и лучшей скорости в современном мире, скорость всегда будет стоять на 1 месте

[@chert_15]

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

[@vasili.logvinov]

первый вопрос: нужно использовать бинарный поиск. Если "количество элементов справа" больше чем "значение элемента" идем правее, меньше - левее. Итерация прерывается если "количество элементов справа" РАВНО "значению элемента" Заканчивается на правом у которого "количество элементов справа" всё ещё больше чем "значение элемента". Ответ - количество элементов справа. второй вопрос: хранишь(в карте) числа больше Н-индекса и их количаства. 1) Если приходит меньше или равный Н-индекса - игнорируешь, иначе сохраняешь в карту и проверяешь сумму количеств чисел больше Н-индекса (сумма всех исключив равного Н-индексу). 1.1) Если сумма больше или равна - увеличивашь Н-индекс на 1, иначе ничего.

[@user-vo4oe4np6x]

Первую задачу можно еще решить бинпоиском по ответу, типо перебирать ответ от 0 до n за logn, и проверять для каждого предполагаемого ответа подойдет ли он за n, таким образом мы сможем найти ответ за n log n.

[@LObSTer9303]

ЗП на таких сайтах обычно в gross пишут?

[@CrossBend]

не понял сложности - мои обычные будни... и сразу оптимизируем код с учетом вероятности нормального распределения цитирования. 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])

[@TheChosenOne171]

в 3м собесе была задача на 3 лошади - это тебе даны 25 лошадей и стадион, где одновременно может бегать 5 лошадей, сколько нужно сделать забегов, чтобы выбрать 3 самые быстрые лошади)) недавно ее решал

[@fulltobenhouse]

Прикольная. Сначала хочется ответить 9 - не сразу очевидно, что 7)

[@DrampiRUS]

Ну вообще каждая лошадь бежит н времени, значит надо всего лишь 5 забегов. Из 5 забегов берешь первые места и берешь три лучших время забега.

[@JohnSmith-rh2ry]

@@DrampiRUS Не сработает :) Не учитываешь, что не первые места какого-либо забега могут быть быстрее первых мест других забегов

[@RealMrPitsa]

а секундомер есть? =)

[@TheChosenOne171]

@@RealMrPitsa нет) было бы слишком просто

[@user-yk3ez5un1g]

Классно!!! Подскажи плиз книги, материалы, на основе которых ты прокачивался по алгоритмам и не только

[@nikolaiandrianov1856]

👏👏👏👏👏

[@paemox]

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

[@nicholasspezza9449]

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

[@user-jg5iy6zs7k]

первая задача, на js const sortArrayWithIndexH = (arr) => { for (let h = 0; h < arr.length; h++) { if (arr.includes(h) && (arr.filter(el => el >= h).length === h)) return h || 0 } }

[@w01fer86]

Быстрее линии только логарифм (ну и константа), значит бин поиском. Т.е. смотрим на средний элемент массива - а не больше ли он, чем длина половины массива. Если да, ставим h-index равным половине длины массива и идёт в левый полумассив проверить тоже самое. В общем, бинпоиск. Основная сложность - всякие граничные условия правильно учесть Для второй - нам пофиг на значения

[@ic6406]

бин поиск только для отсортированного списка подойдёт

[@w01fer86]

@@ic6406 как раз как в первом допвопросе в конце видео

[@artemartem842]

Ещё есть ln(n)

[@user-ny9ux9ss8n]

Саня, как ты английский учил ?

[@abdullaabdurashidov5057]

А как насчет того чтобы использовать HashMap ?

[@orcsword]

Так, я не программист, но вопрос такой, мы получаем в решении Саши для заполнения массива вложенные циклы, разве там не будет сложность O(n*m), а не O(n)?

[@ic6406]

Нет, суммарное кол-во итераций будет гарантировано равно длине массива

[@Gribozhuy]

Да, цикла два, но во втором цикле количество итераций всегда будет строькотде сколько чисел всего изначально. То есть это фактически 2*n, а не n ^2

[@ktrgamesbigskelleton2193]

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

[@user-ls6ro8hi9u]

Hash set (multi): Проходясь по массиву записываем подходящие числа для h-index, пока не наберем h штук. O(1) h-index увеличиваем и удаляем все меньшие h числа из сета O(1), эти числа всегда будут равны h - 1 Time = Memory = O(n)

[@Back2Nix]

А затем, этот вариант легко превращается в решение, где цифры подаются по одной: ```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

[@user-nc7il2em1s]

почему не исключить 0 из массива? нас же не интересуют статьи без цитирований?