День четыреста девятый. #Оффтоп #ЗадачиНаСобеседовании
Давненько у нас не было задачек с собеседований. Сегодня относительно простая.
Дан массив длины N, который содержит числа в диапазоне от 1 до N, найдите число, дубликат которого встречается первым. Другими словами, если имеется более 1 дублированного числа, нужно вернуть число, для которого второе вхождение имеет наименьший индекс. Если таких элементов нет, вернуть -1.
Например:
Для
Для
Есть 2 дубликата: числа 2 и 3. Второй вхождение числа 3 имеет меньший индекс, чем второе вхождение числа 2, поэтому ответ 3.
Усложнённый вариант: Написать решение со сложностью
Как обычно, приглашаю всех предлагать варианты решения в чате @netdeveloperschat
Давненько у нас не было задачек с собеседований. Сегодня относительно простая.
Дан массив длины N, который содержит числа в диапазоне от 1 до N, найдите число, дубликат которого встречается первым. Другими словами, если имеется более 1 дублированного числа, нужно вернуть число, для которого второе вхождение имеет наименьший индекс. Если таких элементов нет, вернуть -1.
Например:
Для
[2, 4, 3, 5, 1] вывод должен быть -1.Для
[2, 3, 3, 1, 5, 2] вывод должен быть 3.Есть 2 дубликата: числа 2 и 3. Второй вхождение числа 3 имеет меньший индекс, чем второе вхождение числа 2, поэтому ответ 3.
Усложнённый вариант: Написать решение со сложностью
O(n) по времени и O(1) по памяти.Как обычно, приглашаю всех предлагать варианты решения в чате @netdeveloperschat
День четыреста десятый. #ЗадачиНаСобеседовании
Ответ на задачу
Как я и говорил, задача была довольно простая, и в чате быстро предложили решение. Поэтому давайте на этом примере рассмотрим советы, которые помогут решать такие задачи.
1. Найдите решение «в лоб» (brute-force).
Чаще всего это не должно быть проблемой. В нашем случае можно для каждого элемента перебирать массив (после этого элемента) и искать индекс следующего за ним дубликата. Ищем наименьший индекс дубликата. В конце выдаём элемент по найденному индексу. Это вполне рабочее решение, но его сложность по времени будет O(n!): для первого элемента перебираем N-1 элементов, для второго N-2 и т.д.
2. Рассмотрите более простой вариант проблемы.
В данном случае это уже есть в задании. Допустим, у нас нет ограничения по использованию памяти.
3. Изучите (хотя бы в общих чертах) алгоритмы и структуры данных.
Например, знание того, что коллекция HashSet вне зависимости от размера имеет постоянное время на поиск вхождения элемента, очень поможет в данном случае. Мы можем перебирать массив и добавлять найденные элементы в коллекцию HashSet. Одновременно проверяем, есть ли текущий элемент уже в коллекции. И если есть, то первый найденный в коллекции элемент и будет ответом. Сложность этого алгоритма O(N) по времени и O(N) по памяти, т.к. нам нужно будет хранить дополнительную коллекцию элементов.
4. Визуализируйте проблему.
Изобразите проблему на рисунке. Убедитесь, что вы правильно понимаете задание. Например, что в данном массиве
5. Придумайте несколько простых примеров и попытайтесь найти закономерность.
В этом конкретном случае этот совет мало полезен. Но в других задачах, например, про лестницу, очень может помочь. Рассмотрите простейший вариант, затем чуть более сложный, ещё более сложный. Что изменилось? Заметна ли закономерность? Изобразите решения графически, возможно, это поможет.
6. Перечитайте условие задачи, учли ли вы все нюансы?
В условии задачи сказано, что значения элементов находятся в диапазоне от 1 до N. Значит мы можем использовать для «запоминания» индексы элементов массива, которые тоже в диапазоне от 1 до N. Идея в том, чтобы, двигаясь по массиву «помечать» элемент по индексу, равному значению текущего элемента. Допустим, для массива
Посмотрим дальше: второй элемент 3 (по модулю), элемент с индексом 3 положительный, значит «помечаем» его
Замечания:
- в коде, конечно, нужно будет учесть, что индексы начинаются с 0 и отнимать 1 при обращении по индексу.
- в реальных условиях мы изменяем элементы массива, поэтому после нахождения ответа, возможно, нужно будет пройтись по массиву ещё раз сменить знак отрицательных элементов обратно.
7. Испытайте ваше решение на нескольких примерах, чтобы убедиться в его правильности.
Источники:
- Видео с подробным объяснением решения
- Видео с советами и ещё одной задачей и решением
Ответ на задачу
Как я и говорил, задача была довольно простая, и в чате быстро предложили решение. Поэтому давайте на этом примере рассмотрим советы, которые помогут решать такие задачи.
1. Найдите решение «в лоб» (brute-force).
Чаще всего это не должно быть проблемой. В нашем случае можно для каждого элемента перебирать массив (после этого элемента) и искать индекс следующего за ним дубликата. Ищем наименьший индекс дубликата. В конце выдаём элемент по найденному индексу. Это вполне рабочее решение, но его сложность по времени будет O(n!): для первого элемента перебираем N-1 элементов, для второго N-2 и т.д.
2. Рассмотрите более простой вариант проблемы.
В данном случае это уже есть в задании. Допустим, у нас нет ограничения по использованию памяти.
3. Изучите (хотя бы в общих чертах) алгоритмы и структуры данных.
Например, знание того, что коллекция HashSet вне зависимости от размера имеет постоянное время на поиск вхождения элемента, очень поможет в данном случае. Мы можем перебирать массив и добавлять найденные элементы в коллекцию HashSet. Одновременно проверяем, есть ли текущий элемент уже в коллекции. И если есть, то первый найденный в коллекции элемент и будет ответом. Сложность этого алгоритма O(N) по времени и O(N) по памяти, т.к. нам нужно будет хранить дополнительную коллекцию элементов.
4. Визуализируйте проблему.
Изобразите проблему на рисунке. Убедитесь, что вы правильно понимаете задание. Например, что в данном массиве
[2, 3, 1, 3, 5, 2]ответом будет 3 (дубликат с наименьшим индексом), а не 2 (дубликат элемента с наименьшим индексом).
5. Придумайте несколько простых примеров и попытайтесь найти закономерность.
В этом конкретном случае этот совет мало полезен. Но в других задачах, например, про лестницу, очень может помочь. Рассмотрите простейший вариант, затем чуть более сложный, ещё более сложный. Что изменилось? Заметна ли закономерность? Изобразите решения графически, возможно, это поможет.
6. Перечитайте условие задачи, учли ли вы все нюансы?
В условии задачи сказано, что значения элементов находятся в диапазоне от 1 до N. Значит мы можем использовать для «запоминания» индексы элементов массива, которые тоже в диапазоне от 1 до N. Идея в том, чтобы, двигаясь по массиву «помечать» элемент по индексу, равному значению текущего элемента. Допустим, для массива
[2, 3, 1, 3, 5, 2]первый элемент 2, тогда мы «помечаем» элемент с индексом 2. Это будет первая тройка. Проще всего сделать значение отрицательным. Получим
[2, -3, 1, 3, 5, 2]Двигаясь дальше, проверяем, не «помечен» ли уже элемент с индексом равным текущему значению. И если он помечен, значит такое число уже встречалось ранее, и это первый дубликат.
Посмотрим дальше: второй элемент 3 (по модулю), элемент с индексом 3 положительный, значит «помечаем» его
[2, -3, -1, 3, 5, 2]Третий элемент 1. Первый элемент положительный, «помечаем»:
[-2, -3, -1, 3, 5, 2]Четвёртый элемент 3. Третий элемент отрицательный (уже помечен), значит первый дубликат 3. Таким образом мы решили задачу за один проход массива - O(N) по времени и не используя дополнительную память – O(1) по памяти.
Замечания:
- в коде, конечно, нужно будет учесть, что индексы начинаются с 0 и отнимать 1 при обращении по индексу.
- в реальных условиях мы изменяем элементы массива, поэтому после нахождения ответа, возможно, нужно будет пройтись по массиву ещё раз сменить знак отрицательных элементов обратно.
7. Испытайте ваше решение на нескольких примерах, чтобы убедиться в его правильности.
Источники:
- Видео с подробным объяснением решения
- Видео с советами и ещё одной задачей и решением
День пятьсот двадцать восьмой. #Оффтоп #ЗадачиНаСобеседовании
В чате просили ещё задачек. Вот вам на выходные)))
Дан массив целых положительных чисел, представляющих цену акции в разные дни (каждый элемент массива представляет день). Также дано целое число k, которое представляет количество сделок, которые вам разрешено совершить. Одна сделка состоит из покупки акции в определённый день и продажи в более поздний день (ВНИМАНИЕ: 1 сделка = 2 транзакции: покупка и продажа).
Найдите максимальную прибыль, которую вы можете получить, покупая и продавая акции, используя максимум k сделок.
Обратите внимание, что в определённый момент вы можете держать только одну акцию. То есть вы не можете купить более одной акции, и не можете купить акцию, если она у вас уже есть. Кроме того, не обязательно использовать все k сделок. Также допустим, что бюджет на покупку не ограничен.
Например,
Как обычно, приглашаю всех предлагать варианты решения в чате.
Источник: https://www.algoexpert.io/
В чате просили ещё задачек. Вот вам на выходные)))
Дан массив целых положительных чисел, представляющих цену акции в разные дни (каждый элемент массива представляет день). Также дано целое число k, которое представляет количество сделок, которые вам разрешено совершить. Одна сделка состоит из покупки акции в определённый день и продажи в более поздний день (ВНИМАНИЕ: 1 сделка = 2 транзакции: покупка и продажа).
Найдите максимальную прибыль, которую вы можете получить, покупая и продавая акции, используя максимум k сделок.
Обратите внимание, что в определённый момент вы можете держать только одну акцию. То есть вы не можете купить более одной акции, и не можете купить акцию, если она у вас уже есть. Кроме того, не обязательно использовать все k сделок. Также допустим, что бюджет на покупку не ограничен.
Например,
prices = [5, 11, 3, 50, 60, 90]
k = 2
Результат: 93
//Покупка: 5, продажа: 11 (+6); покупка: 3, продажа: 90 (+87)
prices = [12, 14, 17, 10, 14, 13, 12, 15]
k = 3
Результат: 12
prices = [100, 30, 15, 10, 8, 25, 80]
k = 3
Результат: 72
//Только одна сделка
Усложнённый вариант: Написать решение со сложностью O(n*k) по времени и O(n) по памяти.Как обычно, приглашаю всех предлагать варианты решения в чате.
Источник: https://www.algoexpert.io/
День пятьсот тридцатый. #Оффтоп #ЗадачиНаСобеседовании
Ответ на задачу
Сначала попробуем решить задачу вручную. Создадим таблицу
Теперь рассмотрим для 2х сделок. Первые 3 дня изменений не принесут. 1 сделка, прибыль 6:
1) Прибылью за предыдущий день (
2) Если мы продаём, то нужно сложить цену за текущий день (
Таким образом, для 2й сделки в 6й день выгоднее всего купить в 3й день. Получим: цена в 6й день 90 + максимальная выгода от предыдущей сделки 3 = 93, что больше, чем прибыль за предыдущий день 63.
Ответом будет прибыль от последней сделки за последний день.
Сложность по времени: обход
Сложность по объёму: двумерный массив –
Оптимизации:
1) Мы можем рассчитывать максимальную выгоду по дням по мере заполнения таблицы прибылей, чтобы исключить дополнительный вложенный цикл. Таким образом, сложность по времени будет
2) Если внимательно посмотреть на алгоритм, нам не нужно хранить все
Полный код на C#
Более подробное объяснение решения на английском
Источник: https://www.algoexpert.io/
Ответ на задачу
Сначала попробуем решить задачу вручную. Создадим таблицу
profits. В столбцах будут дни (day), как в исходном массиве, в строках – сделки (t) от 0 до k. Значениями массива будет максимальная возможная прибыль, полученная от каждой сделки в определённый день. Например:Цены: 5 11 3 50 60 90Если доступно 0 сделок, то и прибыль будет 0:
t=0 : 0 0 0 0 0 0Если доступна 1 сделка, ищем максимальную прибыль от единственной сделки (прибыль в 1й день всегда 0):
t=1 : 0 6 6 47 57 87Продажа во второй день даёт прибыль 6. Продажа в 3й день не даёт прибыли, поэтому максимум остаётся 6. Покупка в 3й день и продажа в 4й даёт прибыль 47 (больше 6, и больше покупки в 1й день по 5, поэтому максимум 47). Аналогично в 5й и 6й день максимальная прибыль будет 57 и 87 соответственно.
Теперь рассмотрим для 2х сделок. Первые 3 дня изменений не принесут. 1 сделка, прибыль 6:
t=2 : 0 6 6В 4й день мы можем закрыть вторую сделку, получить прибыль 47 и сложить её с прибылью от первой сделки:
t=2 : 0 6 6 53В 5й день нам нужно определить, принесёт ли продажа больше прибыли, чем уже есть. Прибыль от второй сделки принесёт 57, общая прибыль будет 63:
t=2 : 0 6 6 53 63Продажа в 6й день даст нам прибыль в 87 (итого 93), что больше, чем текущий максимум 63:
t=2 : 0 6 6 53 63 93Таким образом, можно заметить закономерность. Прибыль в определённый день для текущей сделки (profit[t,day]) будет рассчитываться как максимум между:
1) Прибылью за предыдущий день (
profit[t,day-1]), если мы не продаём.2) Если мы продаём, то нужно сложить цену за текущий день (
prices[day]) с максимально выгодной покупкой в предыдущие дни. То есть за каждый предыдущий день x нам нужно найти разницу между прибылью от предыдущей(-их) сделки(-ок) в этот день (profit[t-1,x]) и покупкой в этот день (prices[x]). Максимум этой разницы за предыдущие дни и будет наиболее выгодной покупкой. Для второй сделки выгода по дням будет:x=1: 0–5=-5 (прибыль 0 минус покупка за 5).x=2: 6-11=-5 (прибыль от 1й сделки 6 минус покупка за 11).x=3: 6-3=3 (прибыль от 1й сделки 6 минус покупка за 3).x=4: 47-50=-3 (максимальная прибыль от 1й сделки 47 минус покупка за 50).x=5: 57-60=-3 (максимальная прибыль от 1й сделки 57 минус покупка за 60).Таким образом, для 2й сделки в 6й день выгоднее всего купить в 3й день. Получим: цена в 6й день 90 + максимальная выгода от предыдущей сделки 3 = 93, что больше, чем прибыль за предыдущий день 63.
Ответом будет прибыль от последней сделки за последний день.
Сложность по времени: обход
n дней k раз - O(n*k) и расчёт максимальной выгоды в каждом случае O(n) – итого O(n^2*k).Сложность по объёму: двумерный массив –
O(n*k).Оптимизации:
1) Мы можем рассчитывать максимальную выгоду по дням по мере заполнения таблицы прибылей, чтобы исключить дополнительный вложенный цикл. Таким образом, сложность по времени будет
O(n*k).2) Если внимательно посмотреть на алгоритм, нам не нужно хранить все
k+1 рядов прибыли. Для расчёта каждого следующего ряда нам нужны данные только предыдущего. Тогда, таблицу можно сократить до двух рядов, соответственно сложность по объёму памяти будет O(n).Полный код на C#
Более подробное объяснение решения на английском
Источник: https://www.algoexpert.io/
День пятьсот шестьдесят шестой. #ЗадачиНаСобеседовании
Топ 10 Умений Которые Понадобятся на Собеседовании
На собеседовании вам могут как задать самые разные вопросы по теории, так и дать практическое задание. Некоторые из них я уже приводил на канале: 1, 2, 3, 4.
Заучить их все просто нереально. Но большинство из них тестирует одно из следующих базовых умений, которым должен обладать каждый «уважающий себя» программист.
1. Двоичный (бинарный) поиск — классический алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины. Используется не только в элементарном нахождении элемента в отсортированном массиве. Он встречается настолько часто, что может быть скрыт даже в задании не на кодирование. К примеру, нужно найти в логах git версию, где в приложении допущена ошибка.
2. Умение строить структуры данных. Практически во всех задачах требуется правильная инкапсуляция данных. Особенно это относится к ООП. Иногда сложность задачи даже не столько в алгоритме, сколько в построении правильной структуры или класса. Поэтому без умения создавать лаконичные и непротиворечивые структуры данных никуда.
3. Рекурсия. Несмотря на то, что рекурсия – тема множества мемов и шуточек про программистов, в реальности она встречается довольно редко (а в таких мемах – почти никогда). Есть хорошее выражение: «Существует несколько задач, которые красиво и эффективно решаются рекурсией. Есть множество задач, которые красиво, но неэффективно решаются рекурсией. Подавляющее большинство задач решать рекурсией и некрасиво, и неэффективно». Тем не менее, знать принципы рекурсивного решения очень полезно. Пример: решение судоку.
4. Основы сортировки. Это не значит, что вам нужно заучить алгоритмы сортировки слиянием или быстрой сортировки. Но важно понимать общие принципы работы, почему сортировка слиянием быстрее сортировки пузырьком, время работы в O-нотации, уметь использовать факт, что коллекция уже отсортирована и т.п.
5. Разворачивание связанного списка. Вариантами задачи могут быть нахождение дубликатов в списке или определение, является ли связанный список зацикленным. Кроме того, важно правильно создать структуру элемента списка (данные и указатель).
6. Манипулирование несколькими переменными/указателями одновременно. Канонический пример: разворот строки, определение, является ли строка палиндромом, нахождение самого длинного палиндрома в тексте, - движение указателей в обе стороны, либо с разной скоростью.
7. Использование Хеш-таблиц (или множеств). Здесь вариантами могут быть задачи на оптимальное нахождение парного числа в массиве, задачи на обход графа с сохранением пути, мемоизация в рекурсии и т.п.
8. Нахождение закрывающей скобки. Вариантами могут быть проверка, все ли скобки закрыты в строке, либо нахождение, сколько скобок нужно добавить. Кандидат для использования стека. Добавляем открывающие скобки в стек, при нахождении закрывающей скобки – удаляем элемент из стека.
9. Поиск в глубину (Depth-first search) — один из методов обхода графа, который состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Можно реализовать с помощью стека и рекурсии. Для заданной вершины добавляем всех её потомков в стек, далее извлекаем первый элемент стека и повторяем процедуру для него рекурсивно.
10. Поиск в ширину (Breadth-first search) — обход всех ребер для «открытия» всех вершин, достижимых из заданной вершины. Можно реализовать с помощью очереди. Для заданной вершины добавляем всех её потомков в очередь. Далее, проходя по очереди добавляем всех потомков каждого элемента в конец очереди.
Источники:
- https://www.youtube.com/watch?v=r1MXwyiGi_U
- https://youtu.be/zHczhZn-z30
Топ 10 Умений Которые Понадобятся на Собеседовании
На собеседовании вам могут как задать самые разные вопросы по теории, так и дать практическое задание. Некоторые из них я уже приводил на канале: 1, 2, 3, 4.
Заучить их все просто нереально. Но большинство из них тестирует одно из следующих базовых умений, которым должен обладать каждый «уважающий себя» программист.
1. Двоичный (бинарный) поиск — классический алгоритм поиска элемента в отсортированном массиве, использующий дробление массива на половины. Используется не только в элементарном нахождении элемента в отсортированном массиве. Он встречается настолько часто, что может быть скрыт даже в задании не на кодирование. К примеру, нужно найти в логах git версию, где в приложении допущена ошибка.
2. Умение строить структуры данных. Практически во всех задачах требуется правильная инкапсуляция данных. Особенно это относится к ООП. Иногда сложность задачи даже не столько в алгоритме, сколько в построении правильной структуры или класса. Поэтому без умения создавать лаконичные и непротиворечивые структуры данных никуда.
3. Рекурсия. Несмотря на то, что рекурсия – тема множества мемов и шуточек про программистов, в реальности она встречается довольно редко (а в таких мемах – почти никогда). Есть хорошее выражение: «Существует несколько задач, которые красиво и эффективно решаются рекурсией. Есть множество задач, которые красиво, но неэффективно решаются рекурсией. Подавляющее большинство задач решать рекурсией и некрасиво, и неэффективно». Тем не менее, знать принципы рекурсивного решения очень полезно. Пример: решение судоку.
4. Основы сортировки. Это не значит, что вам нужно заучить алгоритмы сортировки слиянием или быстрой сортировки. Но важно понимать общие принципы работы, почему сортировка слиянием быстрее сортировки пузырьком, время работы в O-нотации, уметь использовать факт, что коллекция уже отсортирована и т.п.
5. Разворачивание связанного списка. Вариантами задачи могут быть нахождение дубликатов в списке или определение, является ли связанный список зацикленным. Кроме того, важно правильно создать структуру элемента списка (данные и указатель).
6. Манипулирование несколькими переменными/указателями одновременно. Канонический пример: разворот строки, определение, является ли строка палиндромом, нахождение самого длинного палиндрома в тексте, - движение указателей в обе стороны, либо с разной скоростью.
7. Использование Хеш-таблиц (или множеств). Здесь вариантами могут быть задачи на оптимальное нахождение парного числа в массиве, задачи на обход графа с сохранением пути, мемоизация в рекурсии и т.п.
8. Нахождение закрывающей скобки. Вариантами могут быть проверка, все ли скобки закрыты в строке, либо нахождение, сколько скобок нужно добавить. Кандидат для использования стека. Добавляем открывающие скобки в стек, при нахождении закрывающей скобки – удаляем элемент из стека.
9. Поиск в глубину (Depth-first search) — один из методов обхода графа, который состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Можно реализовать с помощью стека и рекурсии. Для заданной вершины добавляем всех её потомков в стек, далее извлекаем первый элемент стека и повторяем процедуру для него рекурсивно.
10. Поиск в ширину (Breadth-first search) — обход всех ребер для «открытия» всех вершин, достижимых из заданной вершины. Можно реализовать с помощью очереди. Для заданной вершины добавляем всех её потомков в очередь. Далее, проходя по очереди добавляем всех потомков каждого элемента в конец очереди.
Источники:
- https://www.youtube.com/watch?v=r1MXwyiGi_U
- https://youtu.be/zHczhZn-z30
День пятьсот семьдесят седьмой. #Оффтоп #ЗадачиНаСобеседовании
В пандан ко вчерашнему посту про простоту и понятность решений, сегодня задачка на выходные.
Прямоугольная любовь
Команда учёных-любителей создала новый сайт знакомств. Отличительной особенностью его является инновационный способ представления профилей людей в виде прямоугольников на плоскости. Чем больше пересечение прямоугольников, тем больше у них шансов на успешные отношения.
Команде нужна помощь в написании алгоритма, находящего пересечение прямоугольников. Как показано на картинке ниже, стороны прямоугольников параллельны осям
Метод должен получать на вход 2 объекта класса
- координаты левой нижней точки
- длина
- ширина
На выходе должен получаться такой же объект
Особенность этой задачи не в оптимизации по времени или памяти, а в получении результата, который работает, а главное легко читается. Многие могут описать решение на высоком уровне, но спотыкаются, когда вникают в детали. Поэтому:
1. Продумайте и нарисуйте все возможные варианты.
2. Используйте конкретные и информативные имена переменных.
Как обычно, приглашаю всех предлагать варианты решения в чате.
В пандан ко вчерашнему посту про простоту и понятность решений, сегодня задачка на выходные.
Прямоугольная любовь
Команда учёных-любителей создала новый сайт знакомств. Отличительной особенностью его является инновационный способ представления профилей людей в виде прямоугольников на плоскости. Чем больше пересечение прямоугольников, тем больше у них шансов на успешные отношения.
Команде нужна помощь в написании алгоритма, находящего пересечение прямоугольников. Как показано на картинке ниже, стороны прямоугольников параллельны осям
x и y.Метод должен получать на вход 2 объекта класса
Rectangle, имеющего свойства:- координаты левой нижней точки
- длина
- ширина
На выходе должен получаться такой же объект
Rectangle, представляющий собой пересечение.Особенность этой задачи не в оптимизации по времени или памяти, а в получении результата, который работает, а главное легко читается. Многие могут описать решение на высоком уровне, но спотыкаются, когда вникают в детали. Поэтому:
1. Продумайте и нарисуйте все возможные варианты.
2. Используйте конкретные и информативные имена переменных.
Как обычно, приглашаю всех предлагать варианты решения в чате.
День пятьсот семьдесят девятый. #Оффтоп #ЗадачиНаСобеседовании
Ответ на субботнюю задачу
Задача не очень сложная, главное грамотно разбить её на части.
Мы можем рассматривать «горизонтальное» пересечение прямоугольников (по оси x) отдельно от пересечения «по вертикали» (по оси y). Например, мы рассмотрим ширину прямоугольников как отрезки на одномерной числовой прямой x. Какие возможные случаи расположения этих отрезков?
1) Пересекаются частично
2) Один отрезок полностью содержится в другом
3) Не пересекаются
4) "Касаются" в одной точке
См. рисунок ниже.
Если рассматривать первые два варианта, можно заметить, что пересечение отрезков всегда начинается в точке старта с бОльшей координатой. Поэтому чтобы найти начало пересечения, выбираем максимум из значений S1 и S2. Аналогично конец пересечения будет в меньшей из точек E1 и E2.
Таким образом, найдя начало и конец отрезка, нам остаётся только узнать его длину. Если она положительная (конечная точка больше начальной), то пересечение есть, отрицательная – отрезки не пересекаются, нулевая – отрезки касаются.
Замечание: в зависимости от условий задачи надо рассмотреть, допустимы ли варианты нулевых ширины и высоты (когда прямоугольники касаются сторонами, либо касаются в одной точке).
PPS: да, в коде не хватает валидации исходных данных.
PPPS: строго говоря, решение можно слегка оптимизировать, не проверяя пересечение по y, если нет пересечения по x.
Источник: https://www.interviewcake.com/question/csharp/rectangular-love
Ответ на субботнюю задачу
Задача не очень сложная, главное грамотно разбить её на части.
Мы можем рассматривать «горизонтальное» пересечение прямоугольников (по оси x) отдельно от пересечения «по вертикали» (по оси y). Например, мы рассмотрим ширину прямоугольников как отрезки на одномерной числовой прямой x. Какие возможные случаи расположения этих отрезков?
1) Пересекаются частично
2) Один отрезок полностью содержится в другом
3) Не пересекаются
4) "Касаются" в одной точке
См. рисунок ниже.
Если рассматривать первые два варианта, можно заметить, что пересечение отрезков всегда начинается в точке старта с бОльшей координатой. Поэтому чтобы найти начало пересечения, выбираем максимум из значений S1 и S2. Аналогично конец пересечения будет в меньшей из точек E1 и E2.
Таким образом, найдя начало и конец отрезка, нам остаётся только узнать его длину. Если она положительная (конечная точка больше начальной), то пересечение есть, отрицательная – отрезки не пересекаются, нулевая – отрезки касаются.
static Segment Overlap(Segment s1, Segment s2)В результате мы найдём отрезки пересечения по оси x и по оси y. Всё, что нам остаётся сделать – это совместить их. Начальные точки отрезков будут координатами левой нижней точки прямоугольника пересечения, длина отрезка по оси x будет шириной, а длина отрезка по оси y – высотой.
{
// начальная точка (максимальная из начальных)
double start = Math.Max(s1.StartPoint, s2.StartPoint);
// конечная точка (минимальная из конечных)
double end = Math.Min(s1.StartPoint + s1.Length, s2.StartPoint + s2.Length);
// отрезки не пересекаются
if (start > end)
return null;
return new Segment(start, end - start);
}
Замечание: в зависимости от условий задачи надо рассмотреть, допустимы ли варианты нулевых ширины и высоты (когда прямоугольники касаются сторонами, либо касаются в одной точке).
public static Rectangle RectangularOverlap(Rectangle r1, Rectangle r2)PS: я в коде использовал новый тип записи. Вот весь код объявления:
{
// пересечение по оси x
Segment xOverlap = Overlap(
new Segment(r1.StartPoint.X, r1.Width),
new Segment(r2.StartPoint.X, r2.Width));
// пересечение по оси у
Segment yOverlap = Overlap(
new Segment(r1.StartPoint.Y, r1.Height),
new Segment(r2.StartPoint.Y, r2.Height));
if (xOverlap?.Length >= 0 && yOverlap?.Length >= 0)
return new Rectangle(
new Point(xOverlap.StartPoint, yOverlap.StartPoint),
xOverlap.Length,
yOverlap.Length
);
// не пересекаются
return null;
}
public record Point(double X, double Y);Можно использовать класс или структуру, но их описание со свойствами и конструкторами гораздо длиннее)))
public record Segment(double StartPoint, double Length);
public record Rectangle(Point StartPoint, double Width, double Height);
PPS: да, в коде не хватает валидации исходных данных.
PPPS: строго говоря, решение можно слегка оптимизировать, не проверяя пересечение по y, если нет пересечения по x.
Источник: https://www.interviewcake.com/question/csharp/rectangular-love
День пятьсот девяносто восьмой. #Оффтоп #ЗадачиНаСобеседовании
Как насчёт задачки на выходные?)))
Думаю, большинство застало кнопочные телефоны с буками. А олды ещё помнят, что буквы были и на стационарных телефонах, особенно импортных (см. картинку).
На самом деле это довольно популярная система в основном в США для запоминания «красивых» корпоративных номеров. Номеров типа
Итак, к задаче. Дан номер телефона, например
Нужно определить, какие слова из списка содержатся в номере телефона. Номер телефона может быть разной длины, но в разумных пределах. Слова должны содержаться целиком как подстроки.
Как насчёт задачки на выходные?)))
Думаю, большинство застало кнопочные телефоны с буками. А олды ещё помнят, что буквы были и на стационарных телефонах, особенно импортных (см. картинку).
На самом деле это довольно популярная система в основном в США для запоминания «красивых» корпоративных номеров. Номеров типа
8-800-700-8000 (кстати, это техподдержка Билайна, не спрашивайте, почему я его помню) на всех не хватит. Тогда придумали расположить алфавит на кнопках, и клиент должен был просто нажимать кнопки, соответствующие буквам. Например:1-800-flowers означало номер 1-800-3569377
Сам номер «некрасивый», а слово легко запомнить.Итак, к задаче. Дан номер телефона, например
3662277 и список слов, например ["foo", "bar", "baz", "foobar", "cap", "car", "cat"].Нужно определить, какие слова из списка содержатся в номере телефона. Номер телефона может быть разной длины, но в разумных пределах. Слова должны содержаться целиком как подстроки.
День шестьсот первый. #Оффтоп #ЗадачиНаСобеседовании
Ответ на задачу про телефонные номера
На первый взгляд, всё довольно просто. Сначала для удобства представим все слова в виде соответствующих цифр. Таким образом, вместо
["foo", "bar", "baz", "foobar", "cap", "car", "cat"]
у нас получится
["366", "227", "229", "366227", "227", "227", "228"]
Это можно сделать, например, через функцию маппинга. Составим массив из 26 цифр, соответствующих каждой букве на кнопке:
Простой вариант
Для каждой цифры номера телефона составим древовидную структуру из цифр, где корень – текущая цифра телефона, а потомки – все цифры после неё. Таким образом, для числа из задачи 3662277 у нас получится нечто подобное:
- Корень –
- Дочерний узел –
- Дочерний узел –
- Слово закончилось, значит это слово содержится в исходном номере.
Для
- Корень –
- Дочерний узел –
- Дочерний узел –
Вариант "посложнее"
Как вы понимаете, этот алгоритм не слишком эффективный. Хотя, для цифр это ещё куда ни шло, а представьте размер дерева из всех возможных символов. Для таких случаев в 1975 году изобретён алгоритм Ахо—Корасик. Суть его в том, что дерево строится не на основе исходной строки, а специальным образом на основе искомых строк с прямыми и обратными ссылками на узлы. Если интересно и хочется поломать голову, можете почитать о нём. Алгоритм позволяет производить поиск подстрок за линейное время.
«Кандидат» на видео (ссылка ниже) о нём знал (не зря работает в Facebook), и ему даже приходилось его реализовывать. Но не пугайтесь, от вас на собеседовании этого вряд ли потребуют))).
Источник: https://www.youtube.com/watch?v=PIeiiceWe_w
Ответ на задачу про телефонные номера
На первый взгляд, всё довольно просто. Сначала для удобства представим все слова в виде соответствующих цифр. Таким образом, вместо
["foo", "bar", "baz", "foobar", "cap", "car", "cat"]
у нас получится
["366", "227", "229", "366227", "227", "227", "228"]
Это можно сделать, например, через функцию маппинга. Составим массив из 26 цифр, соответствующих каждой букве на кнопке:
int[] map = {2,2,2,3,3,3,4,4,4,…};
Затем в цикле проходим по буквам в слове, ищем соответствующую цифру и добавляем в результирующий массив:int[] res = new int[word.Length];Дальше интереснее.
for (int i = 0; i < res.Length; i++)
res[i] = map[word[i] - 'a'];
Простой вариант
Для каждой цифры номера телефона составим древовидную структуру из цифр, где корень – текущая цифра телефона, а потомки – все цифры после неё. Таким образом, для числа из задачи 3662277 у нас получится нечто подобное:
3-6-6-2-2-7-7Одинаковые корни объединим. То есть, например, у корня 2 будет 2 ветки, начинающиеся на 2 и 7:
6-6-2-2-7-7
6-2-2-7-7
2-2-7-7
2-7-7
7-7
2-2-7-7Теперь для каждого слова мы будем по порядку его символов (цифр) проходить по этому дереву и искать, есть ли узлы со значением текущего символа слова. Например, для
\
7-7
"bar" => 227:- Корень –
2 – есть,- Дочерний узел –
2 (2-2) – есть,- Дочерний узел –
7 (2-2-7) – есть,- Слово закончилось, значит это слово содержится в исходном номере.
Для
"map" => 627:- Корень –
6 – есть,- Дочерний узел –
2 (6-2) – есть,- Дочерний узел –
7 (6-2-7) – нет, значит такого слова нет.Вариант "посложнее"
Как вы понимаете, этот алгоритм не слишком эффективный. Хотя, для цифр это ещё куда ни шло, а представьте размер дерева из всех возможных символов. Для таких случаев в 1975 году изобретён алгоритм Ахо—Корасик. Суть его в том, что дерево строится не на основе исходной строки, а специальным образом на основе искомых строк с прямыми и обратными ссылками на узлы. Если интересно и хочется поломать голову, можете почитать о нём. Алгоритм позволяет производить поиск подстрок за линейное время.
«Кандидат» на видео (ссылка ниже) о нём знал (не зря работает в Facebook), и ему даже приходилось его реализовывать. Но не пугайтесь, от вас на собеседовании этого вряд ли потребуют))).
Источник: https://www.youtube.com/watch?v=PIeiiceWe_w
День шестьсот пятьдесят четвёртый. #Оффтоп
Отвлечёмся ненадолго от жизненного цикла запроса в ASP.NET Core. Вчера в нашем чате завязалась дискуссия про базы данных, прелести и недостатки SQL и хранимых процедур. Вот решил вам на выходные дать задачку из собственной практики. Можно рассматривать её как из цикла #ЗадачиНаСобеседовании.
Допустим, у нас есть интернет-магазин (или любой аналогичный каталог товаров и их производителей/поставщиков, скажем, Алиэкспресс). Количество товаров очень большое. Пользователь ищет товар по названию или по категории, и ему выдаётся некоторый набор товаров с их характеристиками и производителем/поставщиком. Предположим для простоты, что из-за большого количества товаров, вся информация в рамках одного поискового запроса собирается в хранимой процедуре и кэшируется во временную таблицу в БД. То есть, если пользователь изменил сортировку или фильтры в текущем поиске, нам не нужно каждый раз извлекать данные из нескольких таблиц, все они уже кэшированы.
Пользователю нужно выдать только определённое количество результатов (разбив на страницы или просто выдавать только ТопХХХ). Пользователь может сортировать результаты (по цене, релевантности, рейтингу и т.п.), применять фильтры или переходить по страницам. Все эти запросы в рамках одного поискового запроса идут к временной таблице, которая создана ранее.
Теперь собственно задача. Производители хотят знать, сколько раз, по каким поисковым запросам и с какими товарами они появлялись на страницах сайта. То есть, если был запрос на «смартфон», который вернул 20000 результатов во временную таблицу, пользователю из них показали 1000 на первой странице и 1000 на второй, а дальше он смотреть не стал. Нам нужно сохранить для статистики данные только тех производителей, которые реально были показаны пользователю (попали в 2000 из 20000). (Да, я специально взял большие числа, а не стандартные 10 на страницу, потому что с 10 товарами решение вполне очевидно и не затратно).
Вопрос: как вы это реализуете? Оцените преимущества и недостатки каждого варианта.
Поскольку я сам с этим столкнулся, мне будет очень интересно узнать ваши версии в комментариях. Как такового правильного ответа тут, наверное, нет.
Жду ваших комментариев. Свою реализацию тоже опишу в комментариях позже.
Отвлечёмся ненадолго от жизненного цикла запроса в ASP.NET Core. Вчера в нашем чате завязалась дискуссия про базы данных, прелести и недостатки SQL и хранимых процедур. Вот решил вам на выходные дать задачку из собственной практики. Можно рассматривать её как из цикла #ЗадачиНаСобеседовании.
Допустим, у нас есть интернет-магазин (или любой аналогичный каталог товаров и их производителей/поставщиков, скажем, Алиэкспресс). Количество товаров очень большое. Пользователь ищет товар по названию или по категории, и ему выдаётся некоторый набор товаров с их характеристиками и производителем/поставщиком. Предположим для простоты, что из-за большого количества товаров, вся информация в рамках одного поискового запроса собирается в хранимой процедуре и кэшируется во временную таблицу в БД. То есть, если пользователь изменил сортировку или фильтры в текущем поиске, нам не нужно каждый раз извлекать данные из нескольких таблиц, все они уже кэшированы.
Пользователю нужно выдать только определённое количество результатов (разбив на страницы или просто выдавать только ТопХХХ). Пользователь может сортировать результаты (по цене, релевантности, рейтингу и т.п.), применять фильтры или переходить по страницам. Все эти запросы в рамках одного поискового запроса идут к временной таблице, которая создана ранее.
Теперь собственно задача. Производители хотят знать, сколько раз, по каким поисковым запросам и с какими товарами они появлялись на страницах сайта. То есть, если был запрос на «смартфон», который вернул 20000 результатов во временную таблицу, пользователю из них показали 1000 на первой странице и 1000 на второй, а дальше он смотреть не стал. Нам нужно сохранить для статистики данные только тех производителей, которые реально были показаны пользователю (попали в 2000 из 20000). (Да, я специально взял большие числа, а не стандартные 10 на страницу, потому что с 10 товарами решение вполне очевидно и не затратно).
Вопрос: как вы это реализуете? Оцените преимущества и недостатки каждого варианта.
Поскольку я сам с этим столкнулся, мне будет очень интересно узнать ваши версии в комментариях. Как такового правильного ответа тут, наверное, нет.
Жду ваших комментариев. Свою реализацию тоже опишу в комментариях позже.
День семьсот первый. #Оффтоп
5 обязательных навыков для разработчиков 2021. Окончание
Начало
3. Будьте «нанимаемым»
Компании хотят знать гораздо больше, чем просто о ваших навыках программирования. Они хотят видеть ваши достижения и подтверждения вашей квалификации, а также хотят убедиться, что у вас есть необходимые навыки хорошего работника.
- Задавайте профессиональные вопросы
Вам нужно научиться задавать профессиональные вопросы. Как на собеседовании, так и просто в разговоре с коллегами. Это скажет вашим работодателям о том, что вы обладаете обширными знаниями в своей области.
- Очистите свои социальные сети
Это может показаться паранойей, и вообще, это ваша личная жизнь. Но всё больше кадровиков ищут информацию о кандидатах в Интернете перед принятием решения о приёме на работу (иногда даже перед собеседованием). И довольно часто кандидаты отсеиваются уже на этом этапе. Поищите себя в сети и посмотрите, какие результаты вы получите. Вы бы приняли себя на работу?
- Обновите своё резюме
Убедитесь, что ваше резюме всегда отражает самую последнюю информацию, а также не содержит неактуальной или вводящей в заблуждение информации.
4. Навыки коммуникации
Ещё один отличный навык, который вам стоит освоить, - это создание социальных связей, знакомств, сотрудничество с коллегами в компании или в вашей сфере специализации. Никто не является кладезем знаний. Нужно сотрудничать с людьми, чтобы вы могли получать помощь, вместе работать над проектами и обмениваться навыками. Быть самым умным парнем с лучшими навыками тайм-менеджмента и знанием всех технических деталей - это хорошо, но рано или поздно найдётся проблема, которая даже вам окажется не под силу. Именно тут помогут сотрудничество и связи. Вы легко сможете найти решение при помощи других специалистов в этой области.
5. Навыки программирования
Как бы банально это ни звучало, будьте профессионалом в том, что вы делаете. Чтобы хорошо программировать, нужно много терпения, времени и постоянная практика. Практикуйте задачи на алгоритмы и частые задачи с собеседований (см. #ЗадачиНаСобеседовании), чтобы тренировать навыки решения задач, а также просматривайте частые вопросы на собеседовании (см. #ВопросыНаСобеседовании), чтобы не забывать теорию. Вы должны отлично владеть хотя бы одним языком программирования, что облегчит для вас изучение других языков.
Какими ещё важными навыками должен, по-вашему, обладать современный программист? Пишите в комментариях. И с наступающим всех!
Источник: https://medium.com/backenders-club/5-must-have-skills-for-developers-2021-e64d91f273cc
Автор оригинала – Solomon Eseme
5 обязательных навыков для разработчиков 2021. Окончание
Начало
3. Будьте «нанимаемым»
Компании хотят знать гораздо больше, чем просто о ваших навыках программирования. Они хотят видеть ваши достижения и подтверждения вашей квалификации, а также хотят убедиться, что у вас есть необходимые навыки хорошего работника.
- Задавайте профессиональные вопросы
Вам нужно научиться задавать профессиональные вопросы. Как на собеседовании, так и просто в разговоре с коллегами. Это скажет вашим работодателям о том, что вы обладаете обширными знаниями в своей области.
- Очистите свои социальные сети
Это может показаться паранойей, и вообще, это ваша личная жизнь. Но всё больше кадровиков ищут информацию о кандидатах в Интернете перед принятием решения о приёме на работу (иногда даже перед собеседованием). И довольно часто кандидаты отсеиваются уже на этом этапе. Поищите себя в сети и посмотрите, какие результаты вы получите. Вы бы приняли себя на работу?
- Обновите своё резюме
Убедитесь, что ваше резюме всегда отражает самую последнюю информацию, а также не содержит неактуальной или вводящей в заблуждение информации.
4. Навыки коммуникации
Ещё один отличный навык, который вам стоит освоить, - это создание социальных связей, знакомств, сотрудничество с коллегами в компании или в вашей сфере специализации. Никто не является кладезем знаний. Нужно сотрудничать с людьми, чтобы вы могли получать помощь, вместе работать над проектами и обмениваться навыками. Быть самым умным парнем с лучшими навыками тайм-менеджмента и знанием всех технических деталей - это хорошо, но рано или поздно найдётся проблема, которая даже вам окажется не под силу. Именно тут помогут сотрудничество и связи. Вы легко сможете найти решение при помощи других специалистов в этой области.
5. Навыки программирования
Как бы банально это ни звучало, будьте профессионалом в том, что вы делаете. Чтобы хорошо программировать, нужно много терпения, времени и постоянная практика. Практикуйте задачи на алгоритмы и частые задачи с собеседований (см. #ЗадачиНаСобеседовании), чтобы тренировать навыки решения задач, а также просматривайте частые вопросы на собеседовании (см. #ВопросыНаСобеседовании), чтобы не забывать теорию. Вы должны отлично владеть хотя бы одним языком программирования, что облегчит для вас изучение других языков.
Какими ещё важными навыками должен, по-вашему, обладать современный программист? Пишите в комментариях. И с наступающим всех!
Источник: https://medium.com/backenders-club/5-must-have-skills-for-developers-2021-e64d91f273cc
Автор оригинала – Solomon Eseme