Перечень тегов:
#sql - SQL
#window - оконные функции

#sql #window
Вот такой вопрос появился на канале @data_engineerette

Моё решение такое:

SELECT event_type, date_start, date_end
FROM (
  SELECT event_type, 
  FIRST_VALUE(date) OVER (PARTITION BY event_mark ORDER BY date) AS date_start,
  LAST_VALUE(next_date) OVER (PARTITION BY event_mark ORDER BY date) AS date_end,
  last_event
  FROM (
      SELECT event_type, date, next_date, last_event, 
      sum(cng_event) over (order by date rows between unbounded preceding and current row) AS event_mark
      FROM (
        SELECT event_type, date,
        LEAD(date, 1, NULL) OVER (PARTITION BY 1 ORDER BY date) AS next_date,
        CASE WHEN LAG(event_type, 1, 0) OVER (PARTITION BY 1 ORDER BY date) = event_type THEN 0 ELSE 1 END AS cng_event,
        CASE WHEN LEAD(event_type, 1, 0) OVER (PARTITION BY 1 ORDER BY date) <> event_type THEN 1 ELSE 0 END AS last_event
        FROM events
        ORDER BY date) AS inn
    ) AS outt) AS final_tab
WHERE last_event = 1
ORDER BY 2;

Поиграться можно здесь или здесь

#python
Вопрос: Назовите изменяемые и неизменяемые типы данных

К неизменяемым (immutable) типам относятся:
целые числа (int);
числа с плавающей точкой (float);
комплексные числа (complex);
логические переменные (bool);
кортежи (tuple);
строки (str);
неизменяемые множества (frozen set).

К изменяемым ( mutable ) типам относятся:
списки (list);
множества (set);
словари (dict)

#leetcode
1. Two Sum
Easy

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.



Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]


Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.


Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Для решения данной задачи можно использовать хеш-таблицу (словарь), что позволит найти пару чисел с суммой, равной целевому числу, за время меньшее, чем O(n^2). Этот метод обеспечит решение задачи за линейное время O(n).

Вот пошаговое решение задачи:

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

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Создаем пустой словарь для хранения числа и его индекса
        num_to_index = {}
        
        # Проходим по каждому числу в списке nums
        for index, num in enumerate(nums):
            # Вычисляем значение, которое в сумме с текущим числом даст target
            complement = target - num
            
            # Проверяем, есть ли это значение в словаре
            if complement in num_to_index:
                # Если есть, возвращаем текущий индекс и индекс числа из словаря
                return [num_to_index[complement], index]
            
            # Если нет, добавляем текущее число и его индекс в словарь
            num_to_index[num] = index

# Примеры использования:
solution = Solution()

# Пример 1:
nums1 = [2, 7, 11, 15]
target1 = 9
# Объяснение: nums[0] + nums[1] == 9, поэтому возвращаем [0, 1]
print(solution.twoSum(nums1, target1))  # Output: [0, 1]

# Пример 2:
nums2 = [3, 2, 4]
target2 = 6
# Объяснение: nums[1] + nums[2] == 6, поэтому возвращаем [1, 2]
print(solution.twoSum(nums2, target2))  # Output: [1, 2]

# Пример 3:
nums3 = [3, 3]
target3 = 6
# Объяснение: nums[0] + nums[1] == 6, поэтому возвращаем [0, 1]
print(solution.twoSum(nums3, target3))  # Output: [0, 1]

#leetcode
76. Minimum Window Substring
Hard

Given two strings s and t of lengths m and n respectively, return the minimum window
substring
of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.



Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.
Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.


Constraints:

m == s.length
n == t.length
1 <= m, n <= 105
s and t consist of uppercase and lowercase English letters.


Follow up: Could you find an algorithm that runs in O(m + n) time?

Для решения задачи нахождения минимального окна в строке s, которое включает все символы из строки t, мы можем использовать алгоритм с использованием техники скользящего окна и хеш-таблиц. Этот подход позволяет достичь временной сложности O(m + n), где m и n — длины строк s и t соответственно.

Использовать два словаря: один для подсчета частоты символов в строке t, другой для отслеживания текущего состояния окна в строке s.
Два указателя для окна (левый и правый), чтобы двигаться по строке s.
Двигать правый указатель, расширяя окно, до тех пор, пока окно не станет валидным (содержит все символы из t).
После этого двигать левый указатель, чтобы найти минимальное валидное окно.
Обновлять минимальное окно при каждом валидном состоянии.
Вернуть найденное минимальное окно или пустую строку, если такого окна нет.

from collections import Counter, defaultdict
from typing import List

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # Если t длиннее s, то минимальное окно невозможно
        if len(t) > len(s):
            return ""
        
        # Подсчет частот символов в t
        dict_t = Counter(t)
        required = len(dict_t)  # Количество уникальных символов в t

        # Словарь для отслеживания состояния окна
        window_counts = defaultdict(int)
        l, r = 0, 0  # Левый и правый указатели
        formed = 0  # Количество уникальных символов в текущем окне, которые удовлетворяют требуемым частотам

        # (длина окна, левый, правый) для хранения минимального окна
        ans = float("inf"), None, None

        while r < len(s):
            char = s[r]
            window_counts[char] += 1

            # Если текущий символ в окне соответствует требуемому количеству в t
            if char in dict_t and window_counts[char] == dict_t[char]:
                formed += 1

            # Пытаться сузить окно, если все символы t присутствуют
            while l <= r and formed == required:
                char = s[l]

                # Обновляем минимальное окно
                if r - l + 1 < ans[0]:
                    ans = (r - l + 1, l, r)

                # Убираем текущий символ из окна
                window_counts[char] -= 1
                if char in dict_t and window_counts[char] < dict_t[char]:
                    formed -= 1

                l += 1  # Двигаем левый указатель вправо

            r += 1  # Двигаем правый указатель вправо

        return "" if ans[0] == float("inf") else s[ans[1]:ans[2] + 1]

# Примеры использования:
solution = Solution()

# Пример 1:
s1 = "ADOBECODEBANC"
t1 = "ABC"
print(solution.minWindow(s1, t1))  # Output: "BANC"

# Пример 2:
s2 = "a"
t2 = "a"
print(solution.minWindow(s2, t2))  # Output: "a"

# Пример 3:
s3 = "a"
t3 = "aa"
print(solution.minWindow(s3, t3))  # Output: ""