Задача (из книжки Cracking the coding interview): есть два бинарных дерева (первое поменьше, второе побольше), и надо проверить является ли первое дерево поддеревом второго.
пятница, 13 апреля 2012 г.
суббота, 10 декабря 2011 г.
Пропущенные элементы в массиве
Есть очень старая задачка, которую часто задавали и задают на собеседованиях. Задавали её и мне, причем не один раз, задавал я и, тоже не один раз.
Формулировка: есть массив чисел длины 99 (ну или n - 1), в котором находятся числа от 1 до 100 (соответственно до n) в произвольном порядке, все по одному разу, кроме одного. Это одно отсутствующее число и надо найти.
Решается она не очень сложно, и довольно часто у кандидатов получается её решить (обычно с подсказками). Ну вы же знаете решение: считаем сумму элементов в массиве и вычитаем её из суммы элементов от 1 до n (которую можно посчитать по формуле n * (n + 1) / 2 или во время обхода массива). Ну или вместо сложения используем операцию исключающего или (xor) для элементов массива и чисел от 1 до n.
Есть расширенная версия этой задачи: теперь таких чисел два. В принципе, тоже не сложно. Раз чисел два, то нужна дополнительная информация, знания только о разности сумм недостаточно. Ну что же, можно считать произведение или сумму квадратов и решить квадратное уравнение.
Но что делать, если таких чисел m?
Формулировка: есть массив чисел длины 99 (ну или n - 1), в котором находятся числа от 1 до 100 (соответственно до n) в произвольном порядке, все по одному разу, кроме одного. Это одно отсутствующее число и надо найти.
Решается она не очень сложно, и довольно часто у кандидатов получается её решить (обычно с подсказками). Ну вы же знаете решение: считаем сумму элементов в массиве и вычитаем её из суммы элементов от 1 до n (которую можно посчитать по формуле n * (n + 1) / 2 или во время обхода массива). Ну или вместо сложения используем операцию исключающего или (xor) для элементов массива и чисел от 1 до n.
Есть расширенная версия этой задачи: теперь таких чисел два. В принципе, тоже не сложно. Раз чисел два, то нужна дополнительная информация, знания только о разности сумм недостаточно. Ну что же, можно считать произведение или сумму квадратов и решить квадратное уравнение.
Но что делать, если таких чисел m?
Подписаться на:
Сообщения (Atom)