Гробы

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

Написать функцию kDiffPairs(arr, k), которая принимает на вход массив целых чисел arr и целое число k и возвращает количество таких пар чисел в массиве, разность которых по модулю равна k.

Например, если arr = [3, 5, 8, 3, 2, 8] и k = 3, то функция должна вернуть 3, так как в массиве ровно три подходящие пары чисел:

• arr[1] = 5 и arr[2] = 8 (8 - 5 = 3)
• arr[1] = 5 и arr[5] = 8 (8 - 5 = 3)
• arr[1] = 5 и arr[4] = 2 (5 - 2 = 3)

Если не встречались с такой задачей, попробуйте за 10 минут придумать решение за O(N) или хотя бы за O(NlogN) и написать в комментариях

Я хз что это

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

Энивей, не дай бог увидеть такое на собесе на должность, где платят меньше, чем в MAANG. Они же оттуда понабрались алгоритмических задач, но платят почему-то меньше

haHAA сказал(а):↑

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

Энивей, не дай бог увидеть такое на собесе на должность, где платят меньше, чем в MAANG. Они же оттуда понабрались алгоритмических задач, но платят почему-то меньше

Нажмите, чтобы раскрыть...

Так с сортировкой же в любом случае logN будет, быстрее не получится, не? 

Kujivunia сказал(а):↑

Так с сортировкой же в любом случае logN будет, быстрее не получится, не? 

Нажмите, чтобы раскрыть...

Да, в большинстве случаев сортировка дает сложность минимум O(N*logN). В очень редких случая можно отсортировать за O(N), но для этого должны быть специфичные данные

Здесь сортировка это странная идея, я бы ее не рассматривал

I=0

For x in range(0,Len(Arr)):

   D=Arr[x]-arr[x+1]

 

   If abs(D)==k:

      I+=1

 Print(I)

В голове так понравилось

Понятное дело не стал писать прям функцию, главное момент идеи

Что-то вроде такого можно наговнокодить сходу:

def kDiffPairs(arr,k):

    counter = 0

    def increase_counter():

        nonlocal counter

        counter+=1    

    for i, elem in enumerate(arr):

        &increase_counter() for elem_ in arr&i:] if abs(elem_ - elem) == k]

    return counter

Бтв д2ру ломает код, вместо символа & должна быть открывающая квадратная скобка [

SonicWaveAnd сказал(а):↑

I=0

For x in range(0,Len(Arr)):

   D=Arr[x]-arr[x+1]

   If abs(D)==k:

      I+=1

 Print(I)

В голове так понравилось

Понятное дело не стал писать прям функцию, главное момент идеи

Нажмите, чтобы раскрыть...

хм, так у тебя же проверяет разность только соседних элементов. А пара может быть по любым индексам в исходном массиве.

iChrome[BY] сказал(а):↑

хм, так у тебя же проверяет разность только соседних элементов. А пара может быть по любым индексам в исходном массиве.

Нажмите, чтобы раскрыть...

Да я внимательно сейчас задачу прочитал

Задумался теперь

в чем проблема если не хочешь ничего гадать написать тупо простейший перебор пар и проверку их на условие???

Islamic_crusader сказал(а):↑

в чем проблема если не хочешь ничего гадать написать тупо простейший перебор пар и проверку их на условие???

Нажмите, чтобы раскрыть...

Ну потому что это неэффективное решение. Тебе скажут "молодец, но давай подумаем над более эффективным решением".

 

FreeM@n сказал(а):↑

Что-то вроде такого можно наговнокодить сходу:

def kDiffPairs(arr,k):

    counter = 0

    def increase_counter():

        nonlocal counter

        counter+=1    

    for i, elem in enumerate(arr):

        &increase_counter() for elem_ in arr&i:] if abs(elem_ - elem) == k]

    return counter

Бтв д2ру ломает код, вместо символа & должна быть открывающая квадратная скобка [ &/QUOTE]

 

 

Нажмите, чтобы раскрыть...

 

По-моему здесь O(N^2). Не пойдет

I=0

 

For x in range(0,Len(Arr)):

    For m in range(x+1, Len(Arr)):

         D=Arr[x]-arr[m]

 

         If abs(D)==k:

            I+=1

 Print(I)

Поправил

@iChrome[BY] 

Скажите что я лс  , я и так это знаю

SonicWaveAnd сказал(а):↑

I=0

 

For x in range(0,Len(Arr)):

    For m in range(x+1, Len(Arr)):

         D=Arr[x]-arr[m]

         If abs(D)==k:

            I+=1

 Print(I)

Поправил

@iChrome[BY] 

Скажите что я лс  , я и так это знаю

Нажмите, чтобы раскрыть...

 

Работать будет, но это неэффективное решение. Здесь сложность по времени O(N^2), а нам нужно хотя бы O(N*logN)

public static int countOfPairs(List source, Integer desired) {
    Set occurrences = new HashSet<>();
    int result = 0;
    for (Integer value : source) {
        Integer difference1 = value - desired;
        Integer difference2 = desired + value;
        if (occurrences.contains(difference1)) {
            result++;
        } else if (occurrences.contains(difference2)) {
            result++;
        }
        occurrences.add(value);
    }
    return result;
}

Добавляем элементы в Set, поиск вхождения в котором работает за O(1). Потом проходимся один раз по массиву, ищем в Set элемент разница с которым будет давать нужное значение. Т.к. проходимся по массиву только один раз, то сложность алгоритма равна O(N)

 

p.s. дженерики форум не захотел отображать

iChrome[BY] сказал(а):↑

public static int countOfPairs(List source, Integer desired) {
    Set occurrences = new HashSet<>();
    int result = 0;
    for (Integer value : source) {
        Integer difference1 = value - desired;
        Integer difference2 = desired + value;
        if (occurrences.contains(difference1)) {
            result++;
        } else if (occurrences.contains(difference2)) {
            result++;
        }
        occurrences.add(value);
    }
    return result;
}

Добавляем элементы в Set, поиск вхождения в котором работает за O(1). Потом проходимся один раз по массиву, ищем в Set элемент разница с которым будет давать нужное значение. Т.к. проходимся по массиву только один раз, то сложность алгоритма равна O(N)

Нажмите, чтобы раскрыть...

Добавление элементов в сет уже N 

Glazic сказал(а):↑

Добавление элементов в сет уже N 

Нажмите, чтобы раскрыть...

Добавление происходит в рамках одного прохода по циклу. Если ты в цикле выполняешь конечное количество операций, то сложность все равно будет считаться как O(N).

Сама операция добавления в Set работает за O(1) благодаря тому, как работает хеш-функция

iChrome[BY] сказал(а):↑

Добавление происходит в рамках одного прохода по циклу. Если ты в цикле выполняешь конечное количество операций, то сложность все равно будет считаться как O(N)

Нажмите, чтобы раскрыть...

Да, память то резиновая.

Данил Низамов сказал(а):↑

 

Работать будет, но это неэффективное решение. Здесь сложность по времени O(N^2), а нам нужно хотя бы O(N*logN)

Нажмите, чтобы раскрыть...

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

Я к сожелению пока что пайтоном в процедурном ввиде владею и капелькой ООП

Плюс ещё bash, Linux, метрики ещё пытаюсь делать. И не получается окунуться, время бесит 

 

Но даже так мне прям хорошо стало, что кто то написал работать будет

 

Glazic сказал(а):↑

Да, память то резиновая.

Нажмите, чтобы раскрыть...

Ничего страшного, здесь максимальная затрата памяти это создать копию массива. Это ок, так как во времени очень много выигрываем

Glazic сказал(а):↑

Да, память то резиновая.

Нажмите, чтобы раскрыть...

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

В моем решении сложность O(N) и память O(N)

Ребята сверху скидывали решения за O(N^2) но зато по памяти там было O(1)

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

Данил Низамов сказал(а):↑

решение за O(N)

Нажмите, чтобы раскрыть...

Ну прямо честное-пречестное O(N) в принципе наверное не возможно, любые ограничения на модель памяти и вычислений — по сути деграднём до pointer machine при существенно великих целых числах, а их я напомню, бесконечное число.

А все машинки, что умеют точно такое перемалывать за O(N) — это какие-то монстры с бесконечными лентами и телепортацией в ячейку.

 

А если на них есть ограничения, то есть M = O(1), то можно вот такой мем сделать:

 

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

 

Доступ к ячейке всегда можно организовать за log(M), где M — номер ячейки.

В самом деле ячейка находится в бинарном дереве под ≈ O(log(M)) номером, с поправкой на направление, спустится к самой ячейке в дереве можно будет тоже за O(log(M)). Суммарно понятно, O(log(M)) + O(log(M)) = O(log(M))

 

Теперь с помощью ленты просто будем делать следующее:

def diff(numbers, k):

    freq = Cells()

    for number in numbers:

        freq[number] += 1

 

   

    return sum(freq[number + k] for number in numbers)

 

 

ну и всё любая операция с Cells это O(log(M)), памяти ячейки, если реализовать их лениво, жрут O(N ∙ log(M)) памяти, и в итоге O(log(M) ∙ N) по памяти и времени получаем.

 

Но, теперь вспоминаем, что M = O(1), и по итогу решение за O(N)

 

iChrome[BY] сказал(а):↑

public static int countOfPairs(List source, Integer desired) {
    Set occurrences = new HashSet<>();
    int result = 0;
    for (Integer value : source) {
        Integer difference1 = value - desired;
        Integer difference2 = desired + value;
        if (occurrences.contains(difference1)) {
            result++;
        } else if (occurrences.contains(difference2)) {
            result++;
        }
        occurrences.add(value);
    }
    return result;
}

Добавляем элементы в Set, поиск вхождения в котором работает за O(1). Потом проходимся один раз по массиву, ищем в Set элемент разница с которым будет давать нужное значение. Т.к. проходимся по массиву только один раз, то сложность алгоритма равна O(N)

 

p.s. дженерики форум не захотел отображать

Нажмите, чтобы раскрыть...

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

но сначала надо добавить в сет все числа, а потом считать вхождения

 

пример где ты повалишься [1, 1, 2], k = 1

   

step	set before	value	result	set after
1	{}	1	0	{1}
2	{1}	1	0	{1}
3	{1}	2	1	{1, 2}

 

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

 

пример:

1 1 1 1 1 2 2 2 2 2 , каждая единица имеет пары с 5 индексами у двойки, а двойки имеют в паре 5 единиц

итого тут 25 пар минимум, ты же при всём желании насчитаешь 20: 10 чисел, каждое даст +2

 

так, короче можно на самом деле, но надо всё равно хранить frequency count на отрезке

 

что-то типо

на очередном шаге посчитаны пары для подотрезка <0, j), добавляем элемент j

тогда надо внести следующие изменения:

 

1) freq[ value ] += 1

 

 

2) result += freq[value + k] + freq[value - k]

 

 

с первым шагом я думаю всё ясно

 

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

 

амортизированное матожидание работы операций хешмапы при хорошей хешфункции — E[T'(n)] = O(1)

ну и потому матожидание работы алгосы — O(n)

 

но надо понимать, что матожидание — это матожидание, средняя температура по больнице

если там какое-то вечно плохое распределение... ну ладно это можно пофиксить рандомным выбором хешфукнции

 

но тем не менее можно нарваться на случайный O(n²), особенно когда счёт идёт на миллионы операций

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

YoshkinKot сказал(а):↑

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

Нажмите, чтобы раскрыть...

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

 

YoshkinKot сказал(а):↑

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

но сначала надо добавить в сет все числа, а потом считать вхождения

Нажмите, чтобы раскрыть...

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

 

YoshkinKot сказал(а):↑

но надо понимать, что матожидание — это матожидание, средняя температура по больнице

если там какое-то вечно плохое распределение... ну ладно это можно пофиксить рандомным выбором хешфукнции

Нажмите, чтобы раскрыть...

Да, понятно, что при плохой хеш функции поиск в сете станет работать за O(N) и тогда весь алгоритм превращается в O(N^2).

Спасибо за большой ответ и найденную ошибку)

Данил Низамов сказал(а):↑

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

Написать функцию kDiffPairs(arr, k), которая принимает на вход массив целых чисел arr и целое число k и возвращает количество таких пар чисел в массиве, разность которых по модулю равна k.

Например, если arr = [3, 5, 8, 3, 2, 8] и k = 3, то функция должна вернуть 3, так как в массиве ровно три подходящие пары чисел:

• arr[1] = 5 и arr[2] = 8 (8 - 5 = 3)
• arr[1] = 5 и arr[5] = 8 (8 - 5 = 3)
• arr[1] = 5 и arr[4] = 2 (5 - 2 = 3)

Если не встречались с такой задачей, попробуйте за 10 минут придумать решение за O(N) или хотя бы за O(NlogN) и написать в комментариях

Нажмите, чтобы раскрыть...

Ну так покажи решение за  O(N)

 

YoshkinKot сказал(а):↑

 

def diff(numbers, k):

    freq = Cells()

    for number in numbers:

        freq[number] += 1

   

    return sum(freq[number] * freq[number + k] for number in numbers)

 

Но, теперь вспоминаем, что M = O(1), и по итогу решение за O(N)

 

Нажмите, чтобы раскрыть...

Как у тебя проход по массиву дважды вдруг уложился в O(n)?

Meepka сказал(а):↑

Ну так покажи решение за  O(N)

 

Как у тебя проход по массиву дважды вдруг уложился в O(n)?

Нажмите, чтобы раскрыть...

O(n) + O(n) = O(n)

Meepka сказал(а):↑

Ну так покажи решение за  O(N)

 

Как у тебя проход по массиву дважды вдруг уложился в O(n)?

Нажмите, чтобы раскрыть...

там не вложенный цикл

ну и это «условный» O(n), потому что я потребовал max({a_i}) = O(1)

 

Данил Низамов сказал(а):↑

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

Написать функцию kDiffPairs(arr, k), которая принимает на вход массив целых чисел arr и целое число k и возвращает количество таких пар чисел в массиве, разность которых по модулю равна k.

Например, если arr = [3, 5, 8, 3, 2, 8] и k = 3, то функция должна вернуть 3, так как в массиве ровно три подходящие пары чисел:

• arr[1] = 5 и arr[2] = 8 (8 - 5 = 3)
• arr[1] = 5 и arr[5] = 8 (8 - 5 = 3)
• arr[1] = 5 и arr[4] = 2 (5 - 2 = 3)

Если не встречались с такой задачей, попробуйте за 10 минут придумать решение за O(N) или хотя бы за O(NlogN) и написать в комментариях

Нажмите, чтобы раскрыть...

создай двумерный массив и записывай туда в x[0] - уникальное число, а в x[1] - количество повторений.

 

Вернуть макс значение x[n][1].

Можно сделать через DICT, где ключ - число, а значение - кол-во повторений.

 

Либо можно спихнуть массив в словарь (сбросить дубликаты),  сам массив конвертнуть в строку (с разделителем) и искать через text.count( element of dict)