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

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

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

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+1 элементов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Yeeeaah! My guy is back!

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

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

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

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

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

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

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

Задача №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 задаче можно также решить через прибавление на отрезке префиксными суммами

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

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

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

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

Можно построить дерево отрезков на сумму и добавление значения, потом при добавлении нового числа будем прибалять 1 в дереве(как в массиве при сортировке подсчетом) и бинарным поиском подбирать h и проверять можем мы его получить или нет. Ели сумма с индекса n - h +- 1 до n >= 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 индекса, его просто откидываем, если нет- добавляем в кучу, пробуем увеличить h, смотрим, сколько элементов придется выкинуть. Куча может повторяющиеся элементы.

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

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

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

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

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

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

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

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

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

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

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

по первой задаче решение такое увидел , циклом проходим каждое число в итерации выполняем второй цикл от 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]

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

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

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

У меня есть вариант для решения с отсортированным массивом со сложностью 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) на количество в данной ячейке (вед 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] } }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для бекенда обязателен Java?

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

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

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

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

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

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

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

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

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

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

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

На втором шаге последнего решения массив наполняется с помощью цикла в цикле. Такое дейсвтие не делает сложность O(n^2) ?

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

Про задачу с hIndex вообще не понял почему все так сложно и не показано простое решение через while function hIndex(arr: number[]) { let i = 0; while(arr.filter(el => el >= i+1).length >= i+1) { i++; } return i; }

Почему мой комментарий с ответом всё время удаляют?

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

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

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

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

Для решения второй задачи можно также использовать метод с отсортировкой элементов, но кроме того еще несколько упрощений. Можно увидеть что только элемент со значением больше предыдущего h индекса может увеличить его, и нам незачем хранить элементы hIndexVal) { sortedElements.offer(newElement); if (sortedElements.size() > hIndexVal) { hIndexVal++; // Remove up to hIndexVal elements that are less or equal hIndexVal // and will not be useful to calculate next hIndex while(sortedElements.size() > 0 && sortedElements.peek()