Минимальная разница между временными метками
Дан массив временных меток в формате HH:MM в пределах одних суток.
Нужно вернуть минимальную разницу в минутах между любыми двумя метками. Сутки считаются циклическими, поэтому разница между 23:59 и 00:00 равна 1.
Гарантируется, что во входе минимум две метки.
Сигнатура
def min_time_difference(times: list[str]) -> int:Пример
min_time_difference(["23:59", "00:00"]) -> 1Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Подсказки
- Ограниченный домен
В сутках только 1440 возможных минут, поэтому сортировку можно заменить counting-подходом.
- Полночь
Не забудьте сравнить последнюю метку суток с первой через переход 24:00 -> 00:00.
Идея решения
Переводим каждую строку HH:MM в минуту от начала суток.
Так как возможных значений всего 1440, используем массив seen. Если одна и та же минута встречается дважды, ответ сразу 0.
Дальше идем по всем минутам от 0 до 1439, запоминаем предыдущую встреченную минуту и обновляем минимальный зазор. В конце отдельно проверяем циклический зазор между последней и первой минутой через полночь.
Эталонный код
def min_time_difference(times: list[str]) -> int:
seen = [False] * 1440
for value in times:
hours, minutes = map(int, value.split(":"))
current = hours * 60 + minutes
if seen[current]:
return 0
seen[current] = True
first = -1
previous = -1
best = 1440
for minute, exists in enumerate(seen):
if not exists:
continue
if first == -1:
first = minute
if previous != -1:
best = min(best, minute - previous)
previous = minute
best = min(best, first + 1440 - previous)
return bestМножество с O(1) add, delete и getRandom
Реализуйте структуру данных RandomizedSet, которая хранит уникальные целые числа и поддерживает операции:
add(value): добавить значение, если его еще нет;delete(value): удалить значение, если оно есть;get_random(): вернуть случайный текущий элемент.
Все операции должны работать за O(1) в среднем.
Интерфейс
class RandomizedSet:
def add(self, value: int) -> None:
...
def delete(self, value: int) -> None:
...
def get_random(self) -> int:
...get_random не вызывается на пустой структуре.Решение прямо на странице
Напишите код, запустите проверки и только потом открывайте разбор.
Нажмите «Запустить проверки» или Ctrl+Enter.
Показать разбор
Подсказки
- Почему не set
set дает быстрые add/delete, но не дает O(1) равномерный выбор случайного элемента по индексу.
- Удаление из середины
Чтобы удалить за O(1), замените удаляемый элемент последним и удалите последний.
Идея решения
Ключевая идея — хранить элементы одновременно в массиве и в словаре позиций.
values нужен для get_random: выбираем случайный индекс от 0 до len(values) - 1.
pos хранит позицию каждого значения в массиве. При удалении из середины массива нельзя делать pop(index), потому что это O(n). Вместо этого меняем удаляемый элемент с последним, обновляем позицию последнего элемента в словаре и делаем pop() последнего элемента.Эталонный код
import random
class RandomizedSet:
def __init__(self):
self.values: list[int] = []
self.pos: dict[int, int] = {}
def add(self, value: int) -> None:
if value in self.pos:
return
self.pos[value] = len(self.values)
self.values.append(value)
def delete(self, value: int) -> None:
if value not in self.pos:
return
index = self.pos[value]
last = self.values[-1]
self.values[index] = last
self.pos[last] = index
self.values.pop()
del self.pos[value]
def get_random(self) -> int:
return random.choice(self.values)
def randomized_set_x5_operations(operations: list[list[object]]) -> list[object]:
randomized_set = RandomizedSet()
result: list[object] = []
for operation, value in operations:
if operation == 'add':
randomized_set.add(value)
result.append(None)
elif operation == 'delete':
randomized_set.delete(value)
result.append(None)
elif operation == 'get_random':
result.append(randomized_set.get_random())
else:
raise ValueError(f'unknown operation: {operation}')
return resultВопрос
How can you get a sentence embedding from BERT, how do sentence transformers differ, and why is this similar to metric learning for image pairs?
Сначала проговорите ответ вслух или тезисами.
Формулы, план решения, риски и примеры.
Откройте разбор только после своей попытки.
Показать разбор
Короткий ответ
Basic BERT pooling uses CLS, mean or max pooling over token embeddings. Sentence transformers are trained with pair/triplet/contrastive objectives so sentence-level embeddings have useful similarity geometry, similar to image metric learning.
Подробный разбор
A vanilla BERT encoder returns contextual token embeddings and often a CLS representation. To get a single sentence vector, common baselines are CLS pooling, mean pooling over non-padding tokens, max pooling, or a learned pooling head. CLS from vanilla BERT is not automatically a high-quality semantic embedding for nearest-neighbor search.
Sentence transformers modify the training objective. They are usually fine-tuned on sentence pairs, triplets or contrastive data so that semantically close texts are close in embedding space and unrelated texts are far. This makes cosine similarity meaningful for retrieval, clustering or semantic search.
The analogy to image metric learning is direct. For car-photo matching, hard positives and hard negatives plus contrastive/triplet losses teach the embedding space what should be close. For sentence transformers, text pairs/triplets play the same role. In both cases, mining hard negatives is often as important as the architecture.
Типичные ошибки
- Assume vanilla BERT CLS is always a good sentence embedding.
- Describe sentence transformers as a completely different Transformer architecture.
- Forget hard-negative mining in metric-learning setups.