Занимательные задачки и отрывок из книги «Карьера программиста»

Задача 2. Решение — создать длинный массив последовательных значений и сложение производить путем сдвига индекса сначала на одно число, а потом на другое. Для этого сначала обрезать массив от числа a и до конца, а затем выбрать в нем элемент с индексом b. В условии задачи нет ограничений на использование вспомогательных структур памяти.
Т.е. как то так (на питоне) sum = numbers[a:][b]

1. Отсортировать массив в порядке возрастания и вернуть первые К элементов

1. heap/heapsort Куча (структура данных)

первая задача делается легко и красиво с помощью Stream, буквально в одну строчку :)

// задача 1: поиск "K" наименьших в массиве
int K = 5;
List<Integer> src_1 = Arrays.asList(45, 36, 55, 12, 8, 9, 33, 24, 15);
List<Integer> res_1 = src_1.stream().sorted().limit(K).collect(toList());
res_1.stream().reduce(0, (acc,elem) -> { System.out.println("res[" + ++acc + "] = " + elem); return acc; });

по поводу задачи 2 не понял немного, что требуется. применить статическую функцию Integer::sum()?
или речь о чём-то другом?

третья задача удивительно лёгкая, но раз такие прения в комментах — не буду говорить принцип решения :))

могу предложить такой способ сложения двух чисел без сложения:

шутка, конечно :)
условиям не удовлетворяет из-за умножения и др. операций

Первую задачу задали на интервью в Гугле. «Найти k минимальных элементов в массиве размера N, для о-о-очень большого N.» — «Отсортировать и взять k первых?» — «А сложность какая?» — «Ну шо-то типа O(N log(N)).» — «А быстрее можно?» — «Можно взять бинарную кучу размера k и пройти по массиву, вставляя туда элементы.» — «А сложность какая?» — «Ну шо-то типа O(N log(k)).» — «А быстрее можно?» — «Думаю, для общего случая — нет, нельзя.» — «Ну ОК, я тоже так думаю.»

Через пару дней катался на велосипеде по берегу реки и вдруг подумал: «А что если сортировать квиксортом по-возрастанию, но не весь массив, а только левую, минимальную половину? До тех пор, пока её размер не станет равен k? Сложность будет, сложность будет, эээ, N + N/2 + N/4 + N/8 +… это больше или меньше, чем N log(k)?» Сходу не сообразил, чему равна сумма последовательности, забил.

Еще через пару дней вспомнил, нагуглил, что сумма вида N + N/2 + N/4 +… = 2N. Получается, сложность моего алгоритма будет O(2N), но константы из Big-O надо выкинуть, т. е. O(N). Т. е. лучше, чем то, что я до этого придумал с бинарной кучей. Ура, блин.

А ещё через пару дней нагуглил, что этот алгоритм называется quickselect и его в пятьдесят лохматом году изобрёл Хоар, вместе с quicksort. Какой удар со стороны классика…

без использования "+" или любых других арифметических операторов.

Знак равенства/неравенства, это арифметический оператор? Тоже запрещен?

1. Сортируем массив и откусываем сколько надо. Выше уже было.

2. Java8
http://stackoverflow.com/questions/17130521/java-method-to-sum-any-number-of-ints
int[] listOfNumbers = {5,4,13,7,7,8,9,10,5,92,11,3,4,2,1};
System.out.println(IntStream.of(listOfNumbers).sum());

3. Квадрат — штука симметричная. Прямая проходящая через центр квадрата(центр — точка пересечения диагоналей), разделит его на два равных четырехугольника. Прямая, заданная двумя центрами квадратов, разделит оба пополам.

Зачем предлагать приз, который не нужен тому, кто справиться с заданиями?
Может награждать тех, кто красиво не справиться?

(a & b) << 1

сдвиг это умножение на основание системы счисления, умножение арифметическая операция…

Вроде бы не писали этого решения 1 задачи.

Используем K-тую порядковую статистику (http://e-maxx.ru/algo/kth_order_statistics)
После чего делаем ещё 1 проход, и все что меньше копируем в ответ. Сложность O(N+K).
Если есть одинаковые элементы искусственно делаем их уникальными, добавив порядковый номер к элементу.

2 задача — классика

int sum(int a, int b)
return b==0?a:sum(a^b,(a&b) << 1);

2 слагаемое — биты переноса. Рано или поздно они закончаться (не позже чем двоичный логарифм от числа).

А с 3 задачей (квадратами) есть такая известная задача о бутерброде, это её частный случай. Для любых 2 хороших фигур, решение будет.

Если дан большой b(N) исходный массив и лучше не очень большое K…

1. Создать массив размера a(K), вначале заполнить a() первыми K элементами из b(), сортируем a(),
последний элемент a(K-1) есть max массива a().
Бежим 1 раз по оставшимся элементам массива b() и сравниваем с последним a(K-1),
если найден меньший элемент, заменяем последний элемент a(K-1) на найденый, сортируем a(), бежим дальше.

сортировку можно заменить одноразовым пробеганием по a() для поиска наибольшего элемента, тогда надо будет запоминать его положение в a() вместо использования последнего элемента.

В разделе 13.5 дважды упоминается LinkedListMap. Такого класса в Java (как минимум в SE) не существует. По смыслу там LinkedHashMap.
По словам автора публикации тоже самое в оригинале, скорее всего опечатка со стороны автора книги.

Забавно смотреть, как люди извращаются :)) У меня ещё вчера сформировалась такая мысль относительно оптимального алгоритма решения 1-й задачи:

Если K << N (число K много меньше количества элементов в массиве), то достаточно:

1) выполнить на исходном массиве «K» итераций таких алгоритмов сортировки, как сортировка выбором ( или даже сортировка пузырьком :) ); легко видеть, что алгоритмы выбора и пузырька работают следующим образом: найти минимальное значение, поставить на 1-е место; найти минимальное среди оставшихся значений и поставить на 2-е место; ...; найти минимальное среди оставшихся (N-(K-1)) значений и поставить на K-е место;…
2) взять первый «K» значений полученного массива и выдать в качестве массива.

Это будет довольно быстрый алгоритм — по сложности условно O(kN), а по правилам BigO-нотации — видимо, O(N)!
Конечно, если число «K» стремится по значению к «N», данный алгоритм будет стремиться к сложности используемой сортировки (а сортировки выбором и пузырьком, увы, не самые лучшие), то ситация меняется в худшую сторону

думаю, что такой ход мыслей будет понятен даже самым начинающим программистам :)