В данной статье я разберу некоторые задани на позицию backend разработчика. Все задачи будут решены с использованием языка программирования python.
1. Нужно вернуть пересечение множеств, но с повторением элементов т.е. если есть два множетсва [1,2,3,4,2] и [2,7,2,4] то мы должны получить [2,2,4]
# импортируем пакет typing (актуально для python < 3.9) import typing as t def intersection_of_many(one: t.List[int], two: t.List[int]) -> t.List[int]: # Создаём копию множетсв (т.к. они мутируют) one = one.copy() two = two.copy() # Тут будем хранить результат res = [] # Проходим по всем элементам одного из множеств (O(n)) for element in one: # Если элемент есть во втором множестве if element in two: # Удаляем элемент из второго множества (первое вхождение) # Для этого и делали copy() чтобы не испортить данные вне функции two.pop(two.index(element)) # Добавляем элемент в результат res.append(element) return res
2. Напишите функцию, которая переставляет значения переменных без использования временных переменных и a,b = b,a.
def swap(a: t.List[int], b: t.List[int]) -> t.Union[t.List[int], t.List[int]]: a[0] = a[0] - b[0] b[0] = b[0] + a[0] a[0] = b[0] - a[0]
3. Реализуйте алгоритм, определяющий, все ли символы в строке встречаются только один раз. А если при этом запрещено использование дополнительных структур данных?
def is_all_symbols_are_unique(string: str) -> bool: for symbol in string: if string.count(symbol) > 1: return False return True
4. Напишите алгоритм, реализующий следующее условие: если элемент матрицы MxN равен 0, то весь столбец и вся строка обнуляются
def swap_lines_and_tables_to_zeros(table: t.List[t.List[int]]) -> None: indexes = [ set(), set() ] x, y = len(table[0]), len(table) for i, line in enumerate(table): if 0 in line: indexes[0].add(i) [indexes[1].add(x[0]) for x in enumerate(line) if not x[1]] if len(indexes[0]) == y or len(indexes[1]) == x: table.clear() table.append([[0 for _ in range(x)] for _ in range(y)]) return None for i, line in enumerate(table): if i in indexes[0]: table.pop(i) table.insert(i, [0 for _ in range(x)]) continue for j, element in enumerate(line): if j in indexes[1]: line.pop(j) line.insert(j, 0)
5. Реализуйте метод для выполнения простейшего сжатия строк с использованием счетчика повторяющихся символов. Например, строка ааbсссссааа превращается в а2b1с5а3. Если сжатая строка не становится короче исходной, то метод возвращает исходную строку. Предполагается, что строка состоит только из букв верхнего и нижнего регистра (a-z).
def zip_string(string: str) -> str: counter = 0 prev = "" res = "" for symbol in string: if symbol == prev: counter += 1 else: prev = symbol res += str(counter) if counter else "" res += symbol counter = 1 else: res += str(counter) if counter else "" return res
6. Напишите код для удаления дубликатов из несортированного списка.
def delete_repeated_data(data: t.List) -> None: for element in data: if data.count(element) > 1: for i in range(data.count(element) - 1): data.pop(data.index(data.index(element)+1, element))
7. Разработайте алгоритм, проверяющий результат игры в крестики-нолики (3х3). 1 - игрок 1, 2 - игрок 2
def x_o_check_result(data: t.List[t.List[int]]) -> int: zero_result = { "column": [0, 0, 0], "d_one": 0, "d_two": 0, } for player in [1, 2]: result = copy.deepcopy(zero_result) for i, line in enumerate(data): if line.count(player) == 3: return player if data[i][i] == player: result['d_one'] += 1 if data[2-i][2-i] == player: result['d_two'] += 1 for j, point in enumerate(line): if point == player: result['column'][j] += 1 if result['column'][j] == 3: return player if result['d_one'] == 3 or result['d_two'] == 3: return player return 0
8. Робот стоит в левом верхнем углу сетки, состоящей из r строк и k столбцов. Робот может перемещаться в двух направлениях: вправо и вниз, но некоторые ячейки сетки заблокированы, то есть робот через них проходить не может. Разработайте алгоритм построения маршрута от левого верхнего до правого нижнего угла.
input: [[0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0], [1, 0, 1, 0], [0, 1, 1, 0]]
где 0 - поле доступное для робота 1 - поле недоступное для робота
def robot_move(field: t.List[t.List[int]]) -> str: def is_free(x, y, field): return not bool(field[y][x]) def get_path( x: int, y: int, field: t.List[t.List[int]], path: t.List[t.List[int]] ) -> t.List[t.List[int]]: path.append([x, y]) if not x and not y: return True, path success = False if x >= 1 and is_free(x-1, y, field): success, path = get_path(x-1, y, field, path) if not success and y >= 1 and is_free(x, y-1, field): success, path = get_path(x, y-1, field, path) if not success: path.pop(-1) return success, path y = len(field) - 1 x = len(field[0]) - 1 return get_path(x, y, field, [])
9. Напишите программу, которая выводит на экран числа от 1 до 100. При этом вместо чисел, кратных трем, программа должна выводить слово «Fizz», а вместо чисел, кратных пяти — слово «Buzz». Если число кратно и 3, и 5, то программа должна выводить слово «FizzBuzz».
def fizz_bazz_print(length: int, rules: t.List[t.Dict]) -> None: rules = copy.deepcopy(rules) length += 1 if length else length for i in range(1, length): for rule in rules: if all(not i % index for index in rule['indexes']): print(rule['text']) break else: print(i)