И снова про собеседования. Некоторые простые задачи порой вызывают затруднение. В этом посте я хочу рассмотреть три задачки с собеседований, которые мне понравились, потому что к их решению можно прийти самим, но чуток подумать все равно придется.

Задача 1. Проверьте, насколько вы избалованный программист

Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.

С толку сбивает только одна фраза «упорядоченная последовательность», она-то и может натолкнуть на использование сортировки для решения данной задачи. Программисты довольно часто пользуются готовыми библиотеками и фреймворками, поэтому при решении задач автоматом обдумываешь, что будешь использовать из библиотеки. Для многих программистов единственным очевидным решением является сортировка полученной последовательности и далее поэлементное сравнение исходной и отсортированной последовательностей до первого несовпадения. Можно подсчитать сложность такого решения: логарифмическая сложность сортировки плюс линейная сложность поиска. Хм, может подойти к решению как-то иначе?

Задача 2. Жонглирование числами

У вас есть пятилитровый и трехлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить половину кувшина не получится.

Это моя любимая задачка из разряда «головоломок». С одной стороны нужно немного подумать, а с другой – она действительно проста и адекватна.

Задача 3. Без посредников

Имеется два числа. Можно ли поменять их местами без использования дополнительной переменной?

Как потом оказалось, это довольно популярная задачка. Но я решила со значительным недочетом.

Решить задачу можно, используя арифметические или побитовые операции. Поскольку арифметические показались проще, то я решила использовать их.


Осталось только пожелать всем успешных собеседований!
А в комментариях можете написать, какие задачи встречались вам.

https://habrahabr.ru/post/332088/