Задача с собеседования в Zeta
Зима близко! Во время соревнования ваша первая задача - спроектировать стандартный обогреватель с фиксированным радиусом обогрева, чтобы обогреть все дома.
Каждый дом может быть обогрет, если он находится в пределах радиуса действия обогревателя.
Даны позиции домов и обогревателей на горизонтальной прямой. Верните минимальный стандартный радиус обогревателей, чтобы они могли покрыть все дома.
Обратите внимание, что все обогреватели соответствуют вашему стандарту радиуса, и радиус зоны нагрева будет одинаковым.
Пример 1:
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: Единственный обогреватель был установлен в позиции 2, и при использовании стандарта радиуса 1, все дома могут быть обогреты.
Пример 2:
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: Два обогревателя были установлены в позициях 1 и 4. Нам нужно использовать стандарт радиуса 1, тогда все дома можно будет обогреть.
Пример 3:
Input: houses = [1,5], heaters = [2]
Output: 3
Ограничения:
1 <= houses.length, heaters.length <= 3 * 10⁴
1 <= houses[i], heaters[i] <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Итак, каждый обогреватель греет на фиксированное расстояние слева и справа, нужно найти минимальный радиус, чтобы все дома могли быть согреты.
Сортируем массивы houses и heaters, чтобы использовать метод двух указателей. Так как дома отсортированы, индекс ближайшего обогревателя для следующего дома не будет меньше, чем индекс для предыдущего дома => указатель по обогревателям движется монотонно вправо.
Указатели:
pos - индекс текущего кандидата в ближайший обогреватель
house - неявный указатель по домам в цикле for
Проходим по массиву houses, ища ближайший обогреватель для каждого дома:
Пока следующий обогреватель находится ближе к дому, чем текущий, или на том же расстоянии:
- сдвигаем pos вправо, переходя к следующему обогревателю.
Используем abs(), так как heaters[pos] может быть как слева (в таком случае heaters[pos] - house будет иметь отрицательное значение, а нам нужна положительная величина для корректного вычисления расстояния), так и справа от дома.
После выхода из цикла while:
heaters[pos] - ближайший обогреватель к текущему дому.
Вычисляем расстояние до него и обновляем res, беря максимальное расстояние до ближайшего обогревателя по всем домам - это и будет минимальный радиус, покрывающий самый удалённый от своего ближайшего обогревателя дом.
Сложность
O(n log n + m log m) - по времени (сортируем массивы; проход двумя указателями - за O(n + m), где n - кол-во домов, а m - кол-во обогревателей)
O(1) - по памяти (без учёта сортировки; храним некоторое кол-во переменных)
Код
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
m = len(heaters)
res = 0
pos = 0
for house in houses:
while pos < m - 1 and abs(heaters[pos + 1] - house) <= abs(heaters[pos] - house):
pos += 1
res = max(res, abs(heaters[pos] - house))
return res
@algoses
Зима близко! Во время соревнования ваша первая задача - спроектировать стандартный обогреватель с фиксированным радиусом обогрева, чтобы обогреть все дома.
Каждый дом может быть обогрет, если он находится в пределах радиуса действия обогревателя.
Даны позиции домов и обогревателей на горизонтальной прямой. Верните минимальный стандартный радиус обогревателей, чтобы они могли покрыть все дома.
Обратите внимание, что все обогреватели соответствуют вашему стандарту радиуса, и радиус зоны нагрева будет одинаковым.
Пример 1:
Input: houses = [1,2,3], heaters = [2]
Output: 1
Explanation: Единственный обогреватель был установлен в позиции 2, и при использовании стандарта радиуса 1, все дома могут быть обогреты.
Пример 2:
Input: houses = [1,2,3,4], heaters = [1,4]
Output: 1
Explanation: Два обогревателя были установлены в позициях 1 и 4. Нам нужно использовать стандарт радиуса 1, тогда все дома можно будет обогреть.
Пример 3:
Input: houses = [1,5], heaters = [2]
Output: 3
Ограничения:
1 <= houses.length, heaters.length <= 3 * 10⁴
1 <= houses[i], heaters[i] <= 10⁹
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Сортируем массивы houses и heaters, чтобы использовать метод двух указателей. Так как дома отсортированы, индекс ближайшего обогревателя для следующего дома не будет меньше, чем индекс для предыдущего дома => указатель по обогревателям движется монотонно вправо.
Указатели:
pos - индекс текущего кандидата в ближайший обогреватель
house - неявный указатель по домам в цикле for
Проходим по массиву houses, ища ближайший обогреватель для каждого дома:
Пока следующий обогреватель находится ближе к дому, чем текущий, или на том же расстоянии:
- сдвигаем pos вправо, переходя к следующему обогревателю.
Используем abs(), так как heaters[pos] может быть как слева (в таком случае heaters[pos] - house будет иметь отрицательное значение, а нам нужна положительная величина для корректного вычисления расстояния), так и справа от дома.
После выхода из цикла while:
heaters[pos] - ближайший обогреватель к текущему дому.
Вычисляем расстояние до него и обновляем res, беря максимальное расстояние до ближайшего обогревателя по всем домам - это и будет минимальный радиус, покрывающий самый удалённый от своего ближайшего обогревателя дом.
Сложность
O(1) - по памяти (без учёта сортировки; храним некоторое кол-во переменных)
Код
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
houses.sort()
heaters.sort()
m = len(heaters)
res = 0
pos = 0
for house in houses:
while pos < m - 1 and abs(heaters[pos + 1] - house) <= abs(heaters[pos] - house):
pos += 1
res = max(res, abs(heaters[pos] - house))
return res
@algoses
🔥3🤯1
This media is not supported in your browser
VIEW IN TELEGRAM
Залетаем с ноги в Яндекс: регистрация проходит до октября, а задания уже лежат тут.
А чтобы ты точно получил оффер, мы уже сделали разбор контеста и технических этапов, они доступны нашим студентам на наших курсах:
Помимо разборов, которые проходят все скрытые тесты на наличие ИИ в решениях, на наших курсах вы получаете:
🔽 Доступ к закрытой базе собесов и тестовых заданий🔽 Разбор стажировки ДС Авито (на МЛ ПРО и ИИ агенты ПРО)🔽 Курс по выходу на доход в валюте🔽 Гарантия оффера🔽 Рефералка в бигтех после защиты пет-проекта🔽 mock-собеседования с обратной связью
Успей написать администратору и не откладывай: задания могут скоро поменять!
Please open Telegram to view this post
VIEW IN TELEGRAM
Полный цикл отбора в Spectral на SWE (HFT)
Недавно рассказывали про отбор в Fast Forward на кванта, теперь расскажем как проходит отбор на SWE. Здесь уже намного меньше математики и ML, зато гораздо больше плюсов, алгоритмов, многопоточности, сетей и понимания того, как код работает непосредственно на железе. Полтора года назад наш выпускник проходил туда отбор, делимся как прошли этапы.
Условия (hr созвон)
Первый созвон был с hr, поспрашивали про опыт, проекты и достижения. Здесь, как и на кванта, стоит заранее подготовить нормальный рассказ про себя и мотивацию идти именно в HFT. Желательно уметь объяснить, почему вам интересна низкоуровневая разработка, оптимизация и работа с производительностью. Касательно зп назвали только диапазон (это было полтора года назад и вижу что вилки сильно уже изменились, тогда мне назвали 50-60к долларов)
Тестовое
На тестовое также лучше заранее выделить почти целый день. Здесь уже задача была ближе к разработке инфраструктуры для обработки биржевых данных. Нужно было реализовать обработку большого потока событий и поддерживать некоторое состояние системы. Сам алгоритм был достаточно простой, основной упор скорее был на качество реализации и производительность. Смотрели на количество аллокаций, копирований, выбор структур данных и в целом насколько человек понимает, где код может начать тормозить. То есть здесь опять же главное не намудрить с архитектурой, а написать достаточно простое и быстрое решение.
Первый тех собес
Первый тех собес был в основном посвящен C++ и низкоуровневой части. По времени примерно полтора часа, при этом ощущение опять же что жесткого тайминга особо нет. Очень много спрашивали по самому языку: работа памяти, object lifetime, move semantics, виртуальные методы, smart pointers, RAII, undefined behavior. Отдельно достаточно подробно проходились по STL и внутреннему устройству основных структур данных. Например могли спросить как устроены vector, map, unordered_map, чем они отличаются не только по асимптотике, но и по тому как лежат в памяти и как это влияет на производительность. Дальше достаточно быстро перешли к компьютерной архитектуре. Спрашивали про кэши процессора, cache lines, locality, branch prediction, virtual memory, page faults и TLB. Были небольшие устные кейсы, где нужно было объяснить почему два одинаковых по асимптотике куска кода могут работать с очень разной скоростью. Отдельный большой блок был по многопоточности: mutex, spinlock, atomics, data race, false sharing, memory ordering. Здесь скорее проверяли понимание, а не знание стандарта C++ наизусть. Также немного поспрашивали Linux: процессы, потоки, context switch, syscalls, профилирование и какие инструменты можно использовать чтобы искать bottleneck'и.
Второй тех собес
Второй тех собес уже был намного больше похож на классическое алгоритмическое интервью. Было несколько задач уровня выше хард литкода по сути со школьных олимпиад 1го уровня или всоша. Задачи в основном были на структуры данных, одну даже дали на разделяйку на дереве (центроиды) . Отдельно была задача на объединение нескольких потоков отсортированных данных и задача на реализацию кольцевого буфера. После решения обычно начинали задавать дополнительные вопросы: можно ли сделать быстрее, уменьшить память, убрать лишние аллокации или как решение изменится если оно будет использоваться из нескольких потоков. То есть здесь важно не только написать правильный алгоритм, но и уметь рассуждать о том, насколько хорошо он будет работать в реальной системе. Также немного погоняли по сетям: TCP/UDP, multicast, сокеты, blocking/non-blocking IO, почему в HFT часто используют UDP для market data и где вообще может появляться лишняя задержка.
Для подготовки советую наш курс алгоритмы про.
➡ Записаться.
System design
Отдельный кусок собеса был посвящен небольшому систем дизайну, но это не классические задачи из бигтеха в духе "спроектируйте Twitter". Здесь дали кейс вокруг обработки market data и отправки ордеров. Нужно было примерно рассказать как разбить систему на компоненты, где будут отдельные потоки, как передавать данные между ними и что делать если один компонент начинает работать медленнее остальных. В процессе в основном спрашивали про latency: где появятся копирования, блокировки, аллокации, системные вызовы и как это можно оптимизировать.
Финал
На финале уже встречался с лидом в офисе. В начале была еще одна небольшая алгоритмическая задача (по ощущениям рейтинга 2к на кфе), ничего сильно сложного, скорее очередной брейнтизер чтобы посмотреть как человек рассуждает. После этого собеседование уже больше превратилось в разговор про опыт и интересы. Много спрашивали про проекты, где приходилось оптимизировать код, искать сложные баги, разбираться с многопоточностью или читать большой чужой код. Также, как и на квант позицию, достаточно сильно смотрят на достижения. Олимпиады, ICPC, Codeforces, сильные пет-проекты или open source будут большим плюсом, особенно если коммерческого опыта пока мало.
Отбор на SWE оказался не столько сложным по задачам, сколько очень широким по количеству тем. Алгоритмы там нужны все задачи были рейтинга от 1800 на кфе (запрашивали по сути достаточно высокий уровень алгоритмического аппарата) , а также очень важно хорошо понимать C++ и то, как программа работает непосредственно на компьютере: память, кэши, потоки, операционная система и сеть.
Подписаться: @postyapshki_old
Недавно рассказывали про отбор в Fast Forward на кванта, теперь расскажем как проходит отбор на SWE. Здесь уже намного меньше математики и ML, зато гораздо больше плюсов, алгоритмов, многопоточности, сетей и понимания того, как код работает непосредственно на железе. Полтора года назад наш выпускник проходил туда отбор, делимся как прошли этапы.
Условия (hr созвон)
Первый созвон был с hr, поспрашивали про опыт, проекты и достижения. Здесь, как и на кванта, стоит заранее подготовить нормальный рассказ про себя и мотивацию идти именно в HFT. Желательно уметь объяснить, почему вам интересна низкоуровневая разработка, оптимизация и работа с производительностью. Касательно зп назвали только диапазон (это было полтора года назад и вижу что вилки сильно уже изменились, тогда мне назвали 50-60к долларов)
Тестовое
На тестовое также лучше заранее выделить почти целый день. Здесь уже задача была ближе к разработке инфраструктуры для обработки биржевых данных. Нужно было реализовать обработку большого потока событий и поддерживать некоторое состояние системы. Сам алгоритм был достаточно простой, основной упор скорее был на качество реализации и производительность. Смотрели на количество аллокаций, копирований, выбор структур данных и в целом насколько человек понимает, где код может начать тормозить. То есть здесь опять же главное не намудрить с архитектурой, а написать достаточно простое и быстрое решение.
Первый тех собес
Первый тех собес был в основном посвящен C++ и низкоуровневой части. По времени примерно полтора часа, при этом ощущение опять же что жесткого тайминга особо нет. Очень много спрашивали по самому языку: работа памяти, object lifetime, move semantics, виртуальные методы, smart pointers, RAII, undefined behavior. Отдельно достаточно подробно проходились по STL и внутреннему устройству основных структур данных. Например могли спросить как устроены vector, map, unordered_map, чем они отличаются не только по асимптотике, но и по тому как лежат в памяти и как это влияет на производительность. Дальше достаточно быстро перешли к компьютерной архитектуре. Спрашивали про кэши процессора, cache lines, locality, branch prediction, virtual memory, page faults и TLB. Были небольшие устные кейсы, где нужно было объяснить почему два одинаковых по асимптотике куска кода могут работать с очень разной скоростью. Отдельный большой блок был по многопоточности: mutex, spinlock, atomics, data race, false sharing, memory ordering. Здесь скорее проверяли понимание, а не знание стандарта C++ наизусть. Также немного поспрашивали Linux: процессы, потоки, context switch, syscalls, профилирование и какие инструменты можно использовать чтобы искать bottleneck'и.
Второй тех собес
Второй тех собес уже был намного больше похож на классическое алгоритмическое интервью. Было несколько задач уровня выше хард литкода по сути со школьных олимпиад 1го уровня или всоша. Задачи в основном были на структуры данных, одну даже дали на разделяйку на дереве (центроиды) . Отдельно была задача на объединение нескольких потоков отсортированных данных и задача на реализацию кольцевого буфера. После решения обычно начинали задавать дополнительные вопросы: можно ли сделать быстрее, уменьшить память, убрать лишние аллокации или как решение изменится если оно будет использоваться из нескольких потоков. То есть здесь важно не только написать правильный алгоритм, но и уметь рассуждать о том, насколько хорошо он будет работать в реальной системе. Также немного погоняли по сетям: TCP/UDP, multicast, сокеты, blocking/non-blocking IO, почему в HFT часто используют UDP для market data и где вообще может появляться лишняя задержка.
Для подготовки советую наш курс алгоритмы про.
System design
Отдельный кусок собеса был посвящен небольшому систем дизайну, но это не классические задачи из бигтеха в духе "спроектируйте Twitter". Здесь дали кейс вокруг обработки market data и отправки ордеров. Нужно было примерно рассказать как разбить систему на компоненты, где будут отдельные потоки, как передавать данные между ними и что делать если один компонент начинает работать медленнее остальных. В процессе в основном спрашивали про latency: где появятся копирования, блокировки, аллокации, системные вызовы и как это можно оптимизировать.
Финал
На финале уже встречался с лидом в офисе. В начале была еще одна небольшая алгоритмическая задача (по ощущениям рейтинга 2к на кфе), ничего сильно сложного, скорее очередной брейнтизер чтобы посмотреть как человек рассуждает. После этого собеседование уже больше превратилось в разговор про опыт и интересы. Много спрашивали про проекты, где приходилось оптимизировать код, искать сложные баги, разбираться с многопоточностью или читать большой чужой код. Также, как и на квант позицию, достаточно сильно смотрят на достижения. Олимпиады, ICPC, Codeforces, сильные пет-проекты или open source будут большим плюсом, особенно если коммерческого опыта пока мало.
Отбор на SWE оказался не столько сложным по задачам, сколько очень широким по количеству тем. Алгоритмы там нужны все задачи были рейтинга от 1800 на кфе (запрашивали по сути достаточно высокий уровень алгоритмического аппарата) , а также очень важно хорошо понимать C++ и то, как программа работает непосредственно на компьютере: память, кэши, потоки, операционная система и сеть.
Подписаться: @postyapshki_old
Please open Telegram to view this post
VIEW IN TELEGRAM
👍5
Задача с собеседования в Zoho
Даны две строки s и t. Определите, являются ли они изоморфными.
Две строки s и t называют изоморфными, если символы в строке s можно заменить так, чтобы получить t.
Все вхождения определённого символа должны быть заменены другим символом с сохранением порядка следования символов. Никакие два разных символа не могут заменяться одним и тем же символом, однако, символ может быть заменён на самого себя.
Пример 1:
Input: s = "egg", t = "add"
Output: true
Explanation: Строки s и t можно сделать идентичными, если:
Заменить "e" на "a".
Заменить "g" на "d".
Пример 2:
Input: s = "f11", t = "b23"
Output: false
Explanation: Строки s и t невозможно сделать идентичными, так как символ "1" должен соответствовать одновременно и "2" и, "3".
Пример 3:
Input: s = "paper", t = "title"
Output: true
Ограничения:
1 <= s.length <= 5 * 10⁴
t.length == s.length
s и t состоят из любых допустимых символов ASCII.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Для изоморфности двух строк необходимо, чтобы обеспечивалось взаимно-однозначное соответствие:
- каждому эл-ту первой строки соответствует ровно один эл-т второй строки;
- и наоборот, каждый эл-т второй строки связан ровно с одним эл-том первой строки.
Создаём два словаря для двусторонней проверки соответствия:
s_to_t - гарантирует, что один и тот же символ из s не будет превращён в разные символы в t
t_to_s - гарантирует обратное условие: один и тот же символ из t не будет получаться из разных символов s
Проходим по двум строкам одновременно с помощью функции zip(), объединяющей эл-ты из двух строк в пары символов:
Если char_s уже встречался ранее и соответствовал другому символу, а не char_t ИЛИ
Если char_t уже был получен из другого символа строки s, а не из char_s:
- изоморфность нарушена => возвращаем False.
Иначе - записываем новые двухсторонние соответствия:
- в какой символ t превращается символ из s;
- из какого символа s получается символ t.
Если правила ни разу не нарушились, значит, строки изоморфны => возвращаем True.
Сложность
O(n) - по времени (проходим по строке один раз; операции со словарем - за O(1))
O(n) - по памяти (в худшем случае, когда все символы уникальные)
Код
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
s_to_t, t_to_s = {}, {}
for char_s, char_t in zip(s, t):
if (char_s in s_to_t and s_to_t[char_s] != char_t) or \
(char_t in t_to_s and t_to_s[char_t] != char_s):
return False
s_to_t[char_s] = char_t
t_to_s[char_t] = char_s
return True
@algoses
Даны две строки s и t. Определите, являются ли они изоморфными.
Две строки s и t называют изоморфными, если символы в строке s можно заменить так, чтобы получить t.
Все вхождения определённого символа должны быть заменены другим символом с сохранением порядка следования символов. Никакие два разных символа не могут заменяться одним и тем же символом, однако, символ может быть заменён на самого себя.
Пример 1:
Input: s = "egg", t = "add"
Output: true
Explanation: Строки s и t можно сделать идентичными, если:
Заменить "e" на "a".
Заменить "g" на "d".
Пример 2:
Input: s = "f11", t = "b23"
Output: false
Explanation: Строки s и t невозможно сделать идентичными, так как символ "1" должен соответствовать одновременно и "2" и, "3".
Пример 3:
Input: s = "paper", t = "title"
Output: true
Ограничения:
1 <= s.length <= 5 * 10⁴
t.length == s.length
s и t состоят из любых допустимых символов ASCII.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
- каждому эл-ту первой строки соответствует ровно один эл-т второй строки;
- и наоборот, каждый эл-т второй строки связан ровно с одним эл-том первой строки.
Создаём два словаря для двусторонней проверки соответствия:
s_to_t - гарантирует, что один и тот же символ из s не будет превращён в разные символы в t
t_to_s - гарантирует обратное условие: один и тот же символ из t не будет получаться из разных символов s
Проходим по двум строкам одновременно с помощью функции zip(), объединяющей эл-ты из двух строк в пары символов:
Если char_s уже встречался ранее и соответствовал другому символу, а не char_t ИЛИ
Если char_t уже был получен из другого символа строки s, а не из char_s:
- изоморфность нарушена => возвращаем False.
Иначе - записываем новые двухсторонние соответствия:
- в какой символ t превращается символ из s;
- из какого символа s получается символ t.
Если правила ни разу не нарушились, значит, строки изоморфны => возвращаем True.
Сложность
O(n) - по памяти (в худшем случае, когда все символы уникальные)
Код
def isIsomorphic(self, s: str, t: str) -> bool:
s_to_t, t_to_s = {}, {}
for char_s, char_t in zip(s, t):
if (char_s in s_to_t and s_to_t[char_s] != char_t) or \
(char_t in t_to_s and t_to_s[char_t] != char_s):
return False
s_to_t[char_s] = char_t
t_to_s[char_t] = char_s
return True
@algoses
👍5❤2
Как залететь в хфт и стать миллионером, залутать сочную зумершку? Обсудим в новом ролике. Смотрим! Смотрим!
https://www.youtube.com/watch?v=zXQSoJjgQG8
https://www.youtube.com/watch?v=zXQSoJjgQG8
YouTube
Как стать quant resercher и попасть в HFT
Как реально попасть в HFT-фонд и стать квантом? В этом ролике — пошаговый разбор: какие роли есть в фондах, что нужно знать, какие достижения ценятся, как готовиться к собеседованиям и куда подаваться.
Внутри:
— кто такой «квант» в HFT и почему это не одна…
Внутри:
— кто такой «квант» в HFT и почему это не одна…
🔥3
Задача с собеседования в Zoho
Даны две строки: s и goal. Верните true, если можно поменять местами два символа в строке s так, чтобы в результате она стала равна строке goal. В противном случае верните false.
Под обменом символов понимается выбор двух индексов i и j (индексация начинается с 0) таких, что i != j, и перестановка символов s[i] и s[j] местами.
Например, обмен символов по индексам 0 и 2 в "abcd" даёт "cbad".
Пример 1:
Input: s = "ab", goal = "ba"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "b", чтобы получить "ba", что равно goal.
Пример 2:
Input: s = "ab", goal = "ab"
Output: false
Explanation: Единственные символы, которые можно поменять местами - это s[0] = "a" and s[1] = "b", в результате чего "ba" != goal.
Пример 3:
Input: s = "aa", goal = "aa"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "a", чтобы получить "aa", что равно goal.
Ограничения:
1 <= s.length, goal.length <= 2 * 10⁴
s и goal состоят из строчных букв.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
Итак, нам нужно обменять ровно две позиции строки s, в которых s и goal различаются; остальные позиции должны совпадать сразу.
=> различий между строками должно быть либо 2 (так как один обмен исправляет только два различия), либо 0 (то есть строки уже эквивалентны).
Обрабатываем следующие случаи:
- Если длина s и goal различается:
False, так как обмен символов не изменит разницу в кол-ве символов.
- Если строки уже эквивалентны:
Необходимо наличие повторяющегося символа (проверяем, есть ли он, через сравнение строки со множеством), так как только обмен одинаковых символов не изменит строку s, уже равную goal. В этом случае возвращается true, иначе - false.
- Если строки разные:
Ищем две различающиеся позиции и проверяем, можно ли поменять два символа ровно одним обменом, чтобы получить goal.
diff - массив индексов, где s[i] != goal[i].
Проходим по строке s:
Если символ по текущему индексу в s отличается от символа по текущему индексу в goal:
- добавляем индекс в diff.
Если кол-во различающихся индексов становится больше 2:
- False, так как одного обмена, затрагивающего две позиции, недостаточно для исправления различий.
Если не нашли 2 различающихся индекса (len(diff) == 1):
- False, так как обмен меняет две позиции и не может покрыть одну позицию без создания нового различия в другой позиции.
Если нашли ровно 2 различающихся индекса:
- проверяем, можем ли перекрёстно поменять символы местами, чтобы получить goal.
Сложность
O(n) - по времени (в худшем случае (когда строки равны) делаем два линейных прохода)
O(1) - по памяти (diff хранит не более трёх индексов (на третьем - выход), set(s) хранит только уникальные символы, т.е. не более 26 эл-в)
Код
class Solution:
def buddyStrings(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
if s == goal:
return len(set(s)) < len(s)
diff = []
for i in range(len(s)):
if s[i] != goal[i]:
diff.append(i)
if len(diff) > 2:
return False
if len(diff) != 2:
return False
i, j = diff
return s[i] == goal[j] and s[j] == goal[i]
Подписаться: @algoses
Даны две строки: s и goal. Верните true, если можно поменять местами два символа в строке s так, чтобы в результате она стала равна строке goal. В противном случае верните false.
Под обменом символов понимается выбор двух индексов i и j (индексация начинается с 0) таких, что i != j, и перестановка символов s[i] и s[j] местами.
Например, обмен символов по индексам 0 и 2 в "abcd" даёт "cbad".
Пример 1:
Input: s = "ab", goal = "ba"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "b", чтобы получить "ba", что равно goal.
Пример 2:
Input: s = "ab", goal = "ab"
Output: false
Explanation: Единственные символы, которые можно поменять местами - это s[0] = "a" and s[1] = "b", в результате чего "ba" != goal.
Пример 3:
Input: s = "aa", goal = "aa"
Output: true
Explanation: Вы можете поменять местами s[0] = "a" and s[1] = "a", чтобы получить "aa", что равно goal.
Ограничения:
1 <= s.length, goal.length <= 2 * 10⁴
s и goal состоят из строчных букв.
НАШ ЧАТ АЛГОРИТМИСТОВ
Решение
=> различий между строками должно быть либо 2 (так как один обмен исправляет только два различия), либо 0 (то есть строки уже эквивалентны).
Обрабатываем следующие случаи:
- Если длина s и goal различается:
False, так как обмен символов не изменит разницу в кол-ве символов.
- Если строки уже эквивалентны:
Необходимо наличие повторяющегося символа (проверяем, есть ли он, через сравнение строки со множеством), так как только обмен одинаковых символов не изменит строку s, уже равную goal. В этом случае возвращается true, иначе - false.
- Если строки разные:
Ищем две различающиеся позиции и проверяем, можно ли поменять два символа ровно одним обменом, чтобы получить goal.
diff - массив индексов, где s[i] != goal[i].
Проходим по строке s:
Если символ по текущему индексу в s отличается от символа по текущему индексу в goal:
- добавляем индекс в diff.
Если кол-во различающихся индексов становится больше 2:
- False, так как одного обмена, затрагивающего две позиции, недостаточно для исправления различий.
Если не нашли 2 различающихся индекса (len(diff) == 1):
- False, так как обмен меняет две позиции и не может покрыть одну позицию без создания нового различия в другой позиции.
Если нашли ровно 2 различающихся индекса:
- проверяем, можем ли перекрёстно поменять символы местами, чтобы получить goal.
Сложность
O(1) - по памяти (diff хранит не более трёх индексов (на третьем - выход), set(s) хранит только уникальные символы, т.е. не более 26 эл-в)
Код
def buddyStrings(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
if s == goal:
return len(set(s)) < len(s)
diff = []
for i in range(len(s)):
if s[i] != goal[i]:
diff.append(i)
if len(diff) > 2:
return False
if len(diff) != 2:
return False
i, j = diff
return s[i] == goal[j] and s[j] == goal[i]
Подписаться: @algoses
🔥3
Ты поступишь в ШАД
Старт набора на наши ШАДовские курсы: без воды и лишней теории, 3 месяца семинаров, пробников и лекций! За результат отвечаем⭐️ пройдешь курсы, но не поступишь в ШАД - вернем деньги⭐️ Программы и подробности:
⏩ Алгоритмы
⏩ Анализ данных
⏩ Линейная алгебра
⏩ Теория вероятностей
⏩ Дискретная математика
⏩ Математический анализ
Можно взять один курс, или комбо по спеццене! Даже все 6 сразу — программа выстроена так, что ты все успеешь. Не веришь — чекай отзывы наших выпускников!
Курсы для тебя, если ты:
🔵 Только задумался о подготовке
🔵 Уже готовился, но не уверен в себе
🔵 Подзабыл математику, но хочешь в ШАД
🔵 Хочешь совмещать подготовку с работой
🔵 Готовишься к собесам в BigTech, АА и маги
Записи и материалы остаются навсегда, а сдать ДЗ, пробники, пройти мок-собес и получить фидбэк куратора можно после окончания курса!
Только у нас ты получишь:
Для вопросов и записи пиши менджеру: @menshe_treh▶️
Старт набора на наши ШАДовские курсы: без воды и лишней теории, 3 месяца семинаров, пробников и лекций! За результат отвечаем
Можно взять один курс, или комбо по спеццене! Даже все 6 сразу — программа выстроена так, что ты все успеешь. Не веришь — чекай отзывы наших выпускников!
Курсы для тебя, если ты:
Записи и материалы остаются навсегда, а сдать ДЗ, пробники, пройти мок-собес и получить фидбэк куратора можно после окончания курса!
Только у нас ты получишь:
🔵 Онлайн-семинары, лекции, ДЗ и пробники с проверкой🔵 Разбор отбора 2027, саппорт с анкетой и мотивацией🔵 Доступ к закрытой базе знаний и протоколам ШАД🔵 Пробное тестирование, экзамен и собеседование🔵 Сборник всех задач ШАДа для самоподготовки
Для вопросов и записи пиши менджеру: @menshe_treh
Please open Telegram to view this post
VIEW IN TELEGRAM
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥1
Собеседование по алгоритмам в ШАД 2026
На прикрепленном фото задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами.
Никаких изменений с форматом в этом году почти не было, все также одна задача на полчаса, нужно решение и код, могли быть доп вопросы и как бонус предлагался чужой код на оценку.
Но формат достаточно интенсивный и для подготовки мало просто прорешать 200 задач с литкода. Нужно научиться быстро распознать паттерны, сходу писать оптимальный код, параллельно поясняя решение. Именно к этому готовят наши курсы. Как раз на семинарах и мок собесах мы учимся рассказывать решения вслух, получаем развернутый фидбэк и учимся действовать в сложных ситуация: что делать если не понимаешь условие, не можешь придумать решение или получил неожиданный вопрос. На наших курсах индивидуальный и структурированный подход, а не тупая алго дрочка. Записывайся и поступай с гарантией!
➡ Записаться
Подписаться: @algoses
На прикрепленном фото задачи, которые спрашивали в этом году. Если хотите добавить задачу с вашего собеседования пишите @vice22821. Взамен могу провести консультацию по любым вопросам или поделиться своими материалами.
Никаких изменений с форматом в этом году почти не было, все также одна задача на полчаса, нужно решение и код, могли быть доп вопросы и как бонус предлагался чужой код на оценку.
Но формат достаточно интенсивный и для подготовки мало просто прорешать 200 задач с литкода. Нужно научиться быстро распознать паттерны, сходу писать оптимальный код, параллельно поясняя решение. Именно к этому готовят наши курсы. Как раз на семинарах и мок собесах мы учимся рассказывать решения вслух, получаем развернутый фидбэк и учимся действовать в сложных ситуация: что делать если не понимаешь условие, не можешь придумать решение или получил неожиданный вопрос. На наших курсах индивидуальный и структурированный подход, а не тупая алго дрочка. Записывайся и поступай с гарантией!
Подписаться: @algoses
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥2