Этап: Техническое собеседование (Алгоритмы)
Максимальная сумма ладьи
У вас есть виртуальная шахматная доска. Требуется выбрать такую ячейку, из которой получится максимальная сумма значений по вертикали и горизонтали, включая само число.
Пример:
print(maxRookSum([
[1, 2, 3],
[3, 4, 1],
[3, 5, 2]
])) # => 16
print(maxRookSum([[1,2,3,4]])) # => 10def maxRookSum(board):
if not board or not board[0]:
return 0
m, n = len(board), len(board[0])
row_sums = [sum(row) for row in board]
col_sums = [sum(board[i][j] for i in range(m)) for j in range(n)]
max_sum = float('-inf')
for i in range(m):
for j in range(n):
current_sum = row_sums[i] + col_sums[j] - board[i][j]
max_sum = max(max_sum, current_sum)
return max_sum
print(maxRookSum([
[1, 2, 3],
[3, 4, 1],
[3, 5, 2]
])) # => 16
print(maxRookSum([[1,2,3,4]])) # => 10Максимизация счастья друзей
У нас есть список друзей [w_i, h_i], где w_i — уровень достатка друга, а h_i — уровень счастья от его присутствия. Никакой друг не должен иметь уровень достатка в 2 или более раз меньше, чем у кого-либо другого на вечеринке. Необходимо максимизировать сумму счастья h_i.
def maxHappiness(friends):
if not friends:
return 0
friends.sort(key=lambda x: x[0])
n = len(friends)
left = 0
current_happiness = 0
max_happiness = 0
for right in range(n):
current_happiness += friends[right][1]
while left < right and friends[right][0] >= 2 * friends[left][0]:
current_happiness -= friends[left][1]
left += 1
max_happiness = max(max_happiness, current_happiness)
return max_happinessВертикальная ось симметрии
Имеется звездная карта (матрица из значений, где каждая ячейка соответствует координатам OX и OY). Требуется найти вертикальную ось симметрии, параллельную оси OY, для множества точек.
Дополнительно
Собеседование проходит на внутренней платформе Т-Банка, похожей на Leetcode. Планируется решить от 2 до 3 задач уровня easy/medium за 1 час. Процесс включает чтение задачи вслух, обсуждение решения, оценку сложности и памяти, а также предложение оптимизаций.