Задачка: Перестановки в массиве

Дан массив
[ a₁, a₂, ... a_n, b₁, b₂, ... b_n ]

Необходимо переставить элементы в массиве, так, чтобы получился

[ a₁, b₁, a₂, b₂, ... a_n, b_n ]

замечание: дополнительная память O(1), сложность < O(n²)

Задачка: зеркально отразить битовое представление

Как можно зеркально отобразить битовое представление 8 битного числа ? 16 битного числа ?

Например,
M(123₁₀) = M(01111011₂) = 11011110₂ = 222₁₀.

внимание! комментарии содержат ответ.

Задачка: развернуть односвязанный список

Задан односвязанный список, например:

A -> B -> C -> ... -> X -> Y -> Z

Необходимо развернуть список, т.е, чтобы его крайний элемент стал первым, предпоследний вторым, и т.д, и в конце концов, первый элемент стал бы крайним элементом.

Z -> Y -> X -> ... -> C -> B -> A

Сложность: O(N), доступная память: O(1).

замечание: можно модифицировать исходный список.

внимание! комментарии содержат ответ.

Задача №377

Задача №377:

Белка массой 0.5 кг сидит на абсолютно гладкой, обледенелой, горизонтальной, плоской крыше. Человек бросает белке камень массой 0.1 кг. Камень летит горизонтально со скоростью 6 м/с. Белка хватает камень и удерживает его.

Вычислите скорость белки, поймавшей камень.

внимание! комментарии содержат ответ.

Задачка: Объём луж

На рельеф некоторой местности падает дождь, попадая в низменности он образует лужи и озерца.

Найти объём образовавшихся луж за время O(N).

замечание №1: силами поверхностного натяжения пренебречь.

замечание №2: рельеф задан целыми числами

например:
V([0, 0, 3, 6, 6, 10, 5, 5, 5, 7, 7, 4, 9, 9, 13, 12, 14, 4, 3, 0]) = 30.

Задачки: Количество сообщений в минуту

Есть некоторый поток сообщений, идущий не равномерно.

Например, с 0 - 10 секунду может прийти 1 сообщение, в следующие 10 ещё 5, потом 10, потом 100 и т.д и опять наступит затишье.

В целях мониторинга хочется иметь представление о точном количестве полученных сообщений (скользящим окном) за крайнюю минуту.

Пояснение: если мы запрашиваем кол-во сообщений в 13:12:05, то должны получить кол-во сообщений с 13:11:05 по 13:12:05. Запрос в 13:12:57 отображает число сообщений с 13:11:57 по 13:12:57.

При этом не интересует сколько было получено две минуты назад, только реальные актуальные цифры. Допускается огрубление с точностью до секунды.

Ограничения: память O(1), сложность O(1), одна нитка выполнения.

p.s. я не знаю, существует ли какое-то классическое и/или единственно верное решение или нет, уже засыпая я смог придумать вполне приемлемое для меня решение, но которое расходует больше, чем 3-5 переменных.

Задачка: <L| и |R>

Заданы два оператора:
L : L(a,b) => ( 2 * a - b , b )
R : (a,b)R => ( a, 2 * b - a )
и начальная точка (a, b) = (0, 1).

Существует последовательность операторов L и R, такая, что в результате либо a = N, либо b = N.

Например:
Число 21 может быть получено кратчайшей последовательностью L L R L R:

  (a, b):   L(a, b) | (a, b)R
  (0, 1):   (-1, 1) | (0, 2)
 (-1, 1):   (-3, 1) | (-1, 3)
 (-3, 1):   (-7, 1) | (-3, 5)
 (-3, 5):  (-11, 5) | (-3, 13)
(-11, 5):  (-27, 5) | (-11, 21)


Какова минимальная длина последовательности с помощью которой можно получить N ?

Замечание №1: число N может лежать в диапозоне -2³¹ .. 2³¹-1.
Замечание №2: сложность O(log(N)).
Замечание №3: досупная память O(1).

внимание! комментарии содержат ответ.

задачка: синие и красные в мешках

Есть 50 синих бумажек и 50 таких же, но красных.

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

внимание! комментарии содержат ответ.

Задачка: лестница

Есть лестница с 10 ступеньками.

За один шаг можно подняться либо на одну ступеньку, либо на две, либо на три ступеньки.



Сколько существует разных способов подняться на последнюю ступеньку ?

замечание #1 Считать, что варианты 3 + 3 + 3 + 1 и 1 + 3 + 3 + 3 независимыми.

замечание #2 Последний шаг должен приводить ровно на последнюю ступеньку, н-р, недопустим вариант 3 + 3 + 3 + 2.

внимание! комментарии содержат ответ.

Задачка: Сортировка по частоте

Дан (очень) большой массив целых чисел, необходимо отсортировать по частоте появления элемента в массиве.
Ограничения: постоянная память, сложность O(N log(N)).

Пример:
[ 1 3 1 ] -> [ 3 1 1 ] т.к. частота(3) = 1; частота(1) = 2
[ 7 1 1 0 ] -> [ 7 0 1 1 ]
[ 9 1 0 1 3 1 3 3 ] -> [ 9 0 1 1 3 3 3 ]

Два презерватива на необитаемом острове

Волею судьбы на необитаемом острове оказалось четверо: двое мужчин и еще две прелестные дамы.

Через какое-то время природа взяла свое и было решено «заняться любовью», однако выяснилось, что все четверо болеют венерическими заболеваниями, причем все - разными.

Поскольку никто не желал добавлять себе еще одно, то после некоторых поисков было найдено два презерватива.

Как провести все четыре возможные встречи между разнополыми партнерами?

внимание! комментарии содержат ответ.

Задачка: 12 монет и 3 взвешивания

Есть 12 монет и аптекарские весы с двумя чашами, которые могут показывать больше, меньше и равно.

Известно, что одна из монет фальшивая - отличается только по весу, причём не известно - тяжелее ли она настоящей или легче.

Как при помощи только трёх взвешиваний определить какая монета фальшивая и тяжелее ли она или легче настоящей ?

Задачка: Честный стражник и лжец

Перед вами две двери:
одна из них ведет на волю, другая - прямая дорога к смерти.

Перед каждой из дверей сидит стражник, причем один из них - лжец, а второй говорит правду и только правду; однако вы не знаете, кто из них кто.

Задав только один вопрос только одному из стражников, определить дорогу на свободу.

Каков вопрос стоит задать ?

внимание! комментарии содержат ответ.

log2(1M)

Многие задачки, которые задают на собеседованиях появляются рано или поздно на ресурсах типа braingames.ru, что в общем-то и не удивительно.

Так например, fp-сообществу понравилась эта задачка, придуманная в нашем отделе.

По мотивам Top 25 Oddball Interview Questions Of 2010 и особенно вопроса, задаваемого в UBS

sqrt(2000) = ?

вспомнилась классическая задача, задаваемая у нас:

log₂(1000000) = ?

Не предполагается, что ответ будет с точностью до какого знака после запятой (точки) - достаточно оценить с точностью до единицы.

Задача Льва Толстого

Продавец продаёт шапку. Стоит 10 р.

Подходит покупатель, меряет и согласен взять, но у него есть только банкнота 25 р. Продавец отсылает мальчика с этими 25 р. к соседке разменять.

Мальчик прибегает и отдаёт 10 + 10 + 5.

Продавец отдаёт шапку и сдачу 15 руб.

Через какое-то время приходит соседка и говорит, что 25 р. фальшивые, требует отдать ей деньги. Ну что делать. Продавец лезет в кассу и возвращает ей деньги.

На сколько обманули продавца ?

внимание! комментарии содержат ответ.

Задачка: Круглый стол

За круглым столом сидят два игрока.

Первый играет белыми круглыми фишками, второй - такими же, но чёрными.

Игрок должен положить на стол только одну фишку, после чего ход переходит к другому игроку.

Игрок проигрывает, если нет свободного места, чтобы положить фишку.

Как следует действовать игроку, начинающему игру, чтобы всегда выигрывать ?

Задачка: Мальчики

В семье два ребенка, причём один из них мальчик.

Какая вероятность что и другой тоже мальчик ?

Задачка: Сколько лет детям

Встречаются 2 друга
- Привет
- Привет
- Как дела?
- Растут два сына дошкольника.
- Сколько им лет?
- Произведение их возрастов равно количеству голубей около скамейки.
- Этой информации мне не достаточно.
- Старший похож на мать.
- Вот теперь я знаю сколько лет твоим детям.

Сколько лет детям?

внимание! комментарии содержат ответ.

Задачка: Таблетки

В джунглях тебя укусила ядовитая змея.

В аптечке есть 4 таблетки - две типа А две типа Б, причём выглядят абсолютно одинаково.

Противоядие - одна таблетка типа А и одна таблетка типа Б.
Во всех других случаях умираешь от змеиного яда (т.е если выпить две таблетки А, или две Б или выпить сразу 2 А и 2 Б)

Как стоит действовать?

Задачка: Груши

В ящике 4 x 4 лежат груши (16 шт.)

Какие 6 груш необходимо убрать, так, чтобы в каждой строке и каждом столбце было чётное число груш.

внимание! комментарии содержат ответ.