Python вопросы с собеседований

📌 Задача



У вас есть девять цифр: 1, 2, …, 9. Именно в таком порядке. Вы можете вставлять между ними знаки «+», «-» или ничего. У вас будут получаться выражения вида 123+45-6+7+89. Найдите все из них, которые равны 100.



def all_combinations(a):

if len(a) <= 1:

yield a

else:

head = ''

tail = list(a)

while len(tail) > 0:

head += tail.pop(0)

for s in all_combinations(tail):

yield [head] + s



def all_signs(n):

if n == 0:

yield ()

else:

for tail in all_signs(n-1):

for s in '+-':

yield (s,) + tail



def perform_operations(nums, signs):

nums = list(map(int, nums))

result = nums.pop(0)

n = 1

for s in signs:

if s == '+':

result += nums.pop(0)

if s == '-':

result -= nums.pop(0)

n += 1

return result



for numbers in all_combinations(tuple(map(str, range(1, 10)))):

#print(numbers)

for signs in all_signs(len(numbers) - 1):

#print(signs)

summ = perform_operations(numbers, signs)

if summ == 100:

print(

''.join(map(

lambda x: ''.join(x),

zip(numbers, signs)))

+ numbers[-1])



Три функции:



- all_combinations — итератор, который выдает все числа для операций (в терминах задачи: вставляет пустые места);

- all_signs — выдаёт все возможные сочетания знаков + и - заданной длинны (для единообразия, это тоже итератор с рекурсией);

- perform_operations — выполняет операции.



Здесь просится решение, избавленное от if-ов и кодирования операций с помощью символов.



👉 Это не оптимальное решение. Пишите свое решение в комментариях👇





@python_job_interview