3 логічні завдання з програмування

1. Завдання про Комбінації:

Припустимо, у вас є масив цілих чисел і число K. Потрібно знайти всі унікальні комбінації чисел із масиву, сума яких дорівнює K. Кожне число можна використовувати лише один раз у комбінації.

Приклад:

Вхід: масив [2, 3, 5, 7], K = 8
Вихід: [[2, 3, 3], [5, 3], [2, 2, 2, 2]]

Це завдання перевіряє навички роботи з масивами, рекурсивні функції та вміння ефективно керувати потоком виконання програми.

2. Завдання про Матриці:

Дано квадратну матрицю. Напишіть програму, яка повертає матрицю на 90 градусів за годинниковою стрілкою.

Приклад:

Вхід:
1 2 3
4 5 6
7 8 9

Вихід:
7 4 1
8 5 2
9 6 3

Це завдання перевіряє вміння маніпулювати матрицями та використовувати індекси масивів для доступу до елементів.

3. Завдання про Дерева:

Реалізуйте функцію для перевірки збалансованості двійкового пошуку. Збалансоване дерево - це дерево, в якому висота піддерев різниться не більше ніж на одиницю.

Приклад:

Вхід:
   1
  / \
 2   3
    / \
   4   5

Вихід: True (збалансоване дерево)

Вхід:
   1
  / 
 2   
  \
   3

Вихід: False (незбалансоване дерево)

Це завдання перевіряє знання структур даних, таких як дерева, та вміння рекурсивно обминати їх.

Вирішення цих завдань вимагає не тільки знання мови програмування, а й уміння розробляти ефективні та логічні алгоритми. Ці завдання часто зустрічаються на співбесідах та можуть допомогти виявити кандидатів із сильними навичками програмування.

Відповіді до завдань

1. Завдання про Комбінації:

def find_combinations(nums, K):
	result = []

	def backtrack(start, target, path):
		if target == 0:
			result.append(path)
			return
		for i in range(start, len(nums)):
			if i > start and nums[i] == nums[i - 1]:
				continue
			if nums[i] > target:
				break
			backtrack(i + 1, target - nums[i], path + [nums[i]])

	nums.sort()
	backtrack(0, K, [])
	return result

# Приклад використання:
arr = [2, 3, 5, 7]
K = 8
print(find_combinations(arr, K))

2. Завдання про Матриці:

def rotate_matrix(matrix):
	n = len(matrix)

	# Транспонування матриці
	for i in range(n):
		for j in range(i, n):
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

	# Реверс рядків матриці
	for i in range(n):
		matrix[i].reverse()

# Приклад використання:
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_matrix(matrix)
print(matrix)

3. Завдання про Дерева:

class TreeNode:
	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

def is_balanced(root):
	def height(node):
		if not node:
			return 0
		left_height = height(node.left)
		right_height = height(node.right)

		if left_height == -1 or right_height == -1 or abs(left_height - right_height) > 1:
			return -1

		return 1 + max(left_height, right_height)

	return height(root) != -1

# Приклад використання:
root_balanced = TreeNode(1)
root_balanced.left = TreeNode(2)
root_balanced.right = TreeNode(3)
root_balanced.right.left = TreeNode(4)
root_balanced.right.right = TreeNode(5)

print(is_balanced(root_balanced)) # True

root_unbalanced = TreeNode(1)
root_unbalanced.left = TreeNode(2)
root_unbalanced.left.left = TreeNode(3)

print(is_balanced(root_unbalanced)) # False

Ці відповіді надають робочі рішення для кожного із запропонованих завдань.