Какой LiveCoding начали спрашивать на Java собеседованиях?

[@bob-gd9kg]

Вот это прорыв, никто не мог придумать структуру которая бы за O(1) работала как со вставкой так и с получением min/max в динамике, а тут на коленке смогли, лучший ментор 😂

[@sorokinpavel]

Задача решена корректно, по крайней мере концептуально. И она решается за О(1). Есть некоторые недочеты, например со строгим неравенством при сравнениях минимального с текущим элементом. Если я не прав, то где ошибка?

[@bob-gd9kg]

​@@sorokinpavelесли добавили 1,2,3 , удалили 1, то минимальный больше не найдет, так как все элементы больше минимального не попадали во вторую структуру

[@sorokinpavel]

@@bob-gd9kg Это стек, удаление элементов идет только сверху. Если добавляли в порядке 1 2 3, то удаление с верхушки стека будет в порядке 3 2 1

[@bob-gd9kg]

@@sorokinpavel если удаление произвольного элемента не требуется, то ты прав, решение верное👍

[@ГеоргийКоломейченко]

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

[@_vaneks2179]

Как называется плагин который ему помогает с написанием кода?

[@vollkovfamilly]

Да, подскажите пожалуйста

[@kergshi9847]

Это не плагин,в самой idea функция

[@_vaneks2179]

@@kergshi9847 как называется? у него идеа сама дописывает код

[@ЕвгенийП-д8л]

В первой задаче не учтены дубли. На добавление нужно нестрогое неравенство, либо счëтчик на каждое значение добавить. Первый вариант, очевидно, проще.

[@ovsyannikovo]

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

[@bob-gd9kg]

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

[@ЯрославМаринов]

А как pop и push на базе ArrayList за константное время работать будут? LinkedList так может, ArrayList - нет.

[@ПавелОрашков]

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

[@ЯрославМаринов]

​​@@ПавелОрашковпо поводу pop согласен, дополнительной релокации массива не происходит если пишем в конец, не стал смотреть дальше когда про ArrayList услышал . По поводу push: оценка сложности, обычно, осуществляется с помощью O большое. Что происходит под капотом - детали. По факту операция не имеет константного времени выполнения.

[@ПавелОрашков]

@@ЯрославМаринов О большое для вставки в конец arrayList - 0(1)

[@АлександрКононов-п5т]

@@ПавелОрашков The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation. Амортизированное O(n) все еще не O(1). Интересно, что в документации операция удаления не упомянута в перечне константных.

[@ПавелОрашков]

@@АлександрКононов-п5т чем сложность n для n операций отличается от n операций сложностью O(1)? Ну и в догонку, почему тогда рекомендуемая с точки зрения быстроты имплементации стека в java это arrayDeque?

[@Dmitry_Kuznetsov]

Молодец что выкрутился с первой задачей, но видно не знает что такое PriorityQueue. С ней было бы проще

[@maksymz6695]

По идее можно использовать простой массив для стека и для мин элемента и при добавлении делать проверку Math.min для value и minStack ну и если меньше то обновлять а если нет то нет. Ну и метод getMin будет возвращать minStack. Кто что думает?

[@МаксимШильвян-ж4ы]

вообще, по хорошему, хранить бы мин значение для каждого элемента, ну или хотя бы равенство добавить при добавлении в мин (высчитывать мин с тем, что лежит в minValues и которое добавляем и этот min ложить напротив добавляемого числа) и потом, как только удаляется элемент в основной структуре удалять и верхний из мин. Так у нас всегда будет консистентное состояние. В их же решении, при некоторых случаях, метод getMin не будет возвращать наименьшее значение (например: 6, 6, 7, 8, 9 и 3, 4, 5, 3, 8, 9) как только мы начнем забирать элементы из стэка(конца списка) и дойдем до 3 и 6 соответственно мы удалим их из minValues, а значения в самом стеке у нас еще есть).

[@maksymz6695]

@@МаксимШильвян-ж4ы ну я так и предложил, добавлять в минВал значения от макс до мин, и потом когда забирать из стека удалять последний єлемент в минВал

[@AliBaba-lf5nr]

Это интервью на джуна или мидла?

[@symryvvin]

на терпилу

[@алексавы-р5к]

какого джуна? какого мидла? чел не знает left join без связей. это трейни.

[@ЕвгенийП-д8л]

На поржать.

[@dimaskusidze]

С hashSet еще проще было бы 😅