Задачи на собеседованиях #197

Наши старые друзья из IT-компании CUSTIS, когда-то одними из первых разместившие задачи в нашей тогда еще новорожденной рубрике, решили вновь порадовать нас хорошей порцией квестов. Ну а DZ Systems прислали нам решения задач, выложенных на суд читателей в апрельском номере, и мы их тоже с удовольствием опубликуем.

Свежая порция задач от компании CUSTIS

Задача для разработчиков Oracle

Разработчик баз данных в свой первый рабочий день в компании обнаружил, что в его проекте используется всего одна табличка с данными по отгруженным товарам (Т). В ней собираются данные по дате отгрузки (d), идентификационному номеру клиента (c) и количеству отгруженного товара (s). Разработчик проверил и убедился, что никаких ключей в таблице нет и по одному клиенту может быть сколько угодно фактов отгрузки в один день.

Почувствовав облегчение от того, что не придется возиться со страшными запросами, разработчик пошел на кухню выпить кофе и перекусить фруктами. После возвращения он с легким сердцем схватил первый же инцидент со Scrum-доски и прочитал следующее: «Нужен отчет по ежедневным отгрузкам товара по выбранному клиенту». Посоветовавшись с товарищами, он выяснил, что отчеты принято оформлять в виде view (представления), то есть для решения проблемы нужно сделать такой view, чтобы запрос

select * from V where c = ?

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

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

Как вы думаете, какой view в результате получился у нашего разработчика?

Задача для разработчиков C#

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

var atlasClient = new AtlasClient();
var allProducts = Session
     .Query<Product>()
     .Select(p => new
     {
         Product = p,
         Rests = atlasClient.GetRests(p.Id)
     });

var fewProducts = allProducts.Where(i => i.Rests > 0 && i.Rests < 10).Select(i => i.Product);
var someProducts = allProducts.Where(i => i.Rests >= 10 && i.Rests < 100).Select(i => i.Product);
var manyProducts = allProducts.Where(i => i.Rests >= 100).Select(i => i.Product);

PrintFewProducts(fewProducts);
PrintSomeProducts(someProducts);
PrintManyProducts(manyProducts);

метод atlasClient.GetRests занимает около 98% общего времени построения отчета.

Предложите вариант оптимизации построения отчета. Почему ваш вариант работает быстрее? Сколько времени занимает построение отчета после вашей оптимизации?

Задача для разработчиков Java

Разработчик C# решил попробовать себя на поприще Java и перешел в Java-проект. Одно из первых заданий, которое он получил, — сделать таблицу с информацией о проданных товарах. В постановке задачи было написано, что нужны следующие столбцы: имя клиента, код клиента, название товара и стоимость товара. Посмотрев на реализацию такого рода таблиц в проекте, он понял, что при настройке таблицы придется написать что-то вроде

table.add( "customer.name" );
table.add( "customer.code" );
table.add( "subject.name" );
table.add( "summ" );

Прямо скажем, по сравнению с тем, как он делал это на родном dotNet, это выглядело совсем ненадежно — никаких проверок уровня компиляции, очень легко допустить ошибку. Хочется написать

table.add( customer.name );

или хотя бы

table.add( {} -> customer.name );

а тут такое. Код получается небезопасный, IDE никак не подсказывает, что писать, и вообще... Решив не сдаваться и привнести свет истины в захолустное царство Java, он объяснил проблемы такой настройки таблиц другим Java-разработчикам. Ему отвечали, что проект ведется на Java 7, лямбд нет, а с анонимными классами для каждого поля настройка будет выглядеть жутко, поэтому пишем как можем. Но, найдя единомышленников в стане Java, он смог реализовать движок, который позволял настраивать столбцы вот так:

Payment root = root( Payment.class );
table.add($( root.getCustomer().getName() ));
...

Причем интерфейс настройки таблиц менять не пришлось, то есть на вход table.add приходит все та же строка customer.name. Не пришлось менять и модельные сущности («покупатель», «товар», «покупка» и другие) и даже не понадобилось никаких автогенерированных классов. Этот инструмент начали использовать везде, где нужно было сослаться на цепочку свойств.

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

Решение задач от DZ Systems

Задача 1

При использовании очевидного представления данных для сохранения даты требуется 8 байт (ДДММГГГГ), а имя человека занимает примерно 25 байт (14 на фамилию, 10 на имя и 1 на первую букву отчества). Насколько вы сможете уменьшить эти числа, если перед вами стоит задача экономии памяти?

Решение

• Первый способ уменьшения числа байтов для хранения даты:
  • день месяца — это число от 1 до 31, для записи его в бинарном представлении достаточно 5 бит;
  • месяц — это число от 1 до 12 — 4 бита;
  • год — число от 0 до 9999 — 14 бит.
  • Получаем 23 бита на хранение даты, или 3 байта (23/8 = 2,875).
• Второй способ уменьшения числа байтов для хранения даты: день можно отсчитывать от какого-то заранее заданного дня, и если предположить, что даты будут от 1 января 1 года до 31 декабря 9999 года, то это примерно 3 649 635 дней (365 * 9999), значение дня поместится в 22 бита.
• Первый способ хранения имени
  • Если предположить, что имя будет записано только русскими (33 буквы) и английскими буквами (26), это 59 различных букв и для хранения одного символа нам достаточно 6 бит. На 25 символов нам нужно 6 * 25 = 150 бит, или 19 байт (150/8 = 18,75).
• Второй способ хранения имени (улучшение первого)
  • Если фамилия может быть короче 14 символов, имя — короче 10, можно ввести символ окончания строки, например 0. Тогда если имя и фамилия короткие, то для хранения полного имени минимум может потребоваться 5 символов, это случай, когда фамилия, имя и отчество состоят из одного символа, и нам нужно сохранить одну букву фамилии, один символ окончания строки, одну букву имени, один символ окончания строки, одну букву отчества, то есть 5 * 6 = 30 бит, или 4 байта. Если фамилия и имя состоят из максимального числа символов, то разделитель не используем.

  Получаем, что для хранения имени потребуется от 30 до 150 бит, или от 4 до 19 байт.

Задача 2

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

Другие статьи в выпуске:

Xakep #197. Социальная инженерия

• Содержание выпуска
• Подписка на «Хакер»-60%

Решение

Приведем вариант на языке Java. Самый простой способ — это написать решение с использованием рекурсии:

public class MathUtils {
    public static long fibonacciNumber(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("");
        }
        if (n == 0 || n == 1) {
            return 1;
        } else {
            return fibonacciNumber(n - 1) + fibonacciNumber(n - 2);
        }
    }
} 

Однако вычислительная сложность этого способа оставляет желать лучшего, поэтому так лучше не делать. Реализация без рекурсии, с использованием цикла, будет работать намного быстрее, так как вычислительная сложность будет O(n):

public class MathUtils {
    public static long fibonacciNumber(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n should not be less 0");
        }
        long f1 = 1;
        long f2 = 1;
        long result = 1;
        for (int i = 2; i <= n; i++) {
            result = f1 + f2;
            f1 = f2;
            f2 = result;
        }
        return result;
    }
}

Это решение тоже имеет недостаток: с определенного момента (n = 92) будет переполнение разрядной сетки и метод вернет неверное значение. Для больших значений числа Фибоначчи можно использовать класс BigInteger, который предназначен для работы с большими числами. Получим следующий результат:

public class MathUtils {
    public static BigInteger fibonacciNumber(int n) {
        BigInteger f1 = BigInteger.valueOf(1);
        BigInteger f2 = BigInteger.valueOf(1);
        BigInteger result = BigInteger.valueOf(1);
        for (int i = 2; i <= n; i++) {
            result = f1.add(f2);
            f1 = f2;
            f2 = result;
        }
        return result;
    }
}

Задача 3

В массиве натуральных чисел [1..1001], содержащем все числа от 1 до 1000 включительно, есть элемент, повторяющийся дважды. Найти его. К каждому элементу можно обращаться только один раз. Язык программирования — любой.

Решение

Решение будет представлено на языке Java. Чтобы найти повторяющийся элемент, нужно сложить все числа из массива и вычесть из получившегося числа сумму чисел от 1 до 1000.

public class ArrayUtils {
    public final static int SUM_1_TO_1000 = (1 + 1000) * 1000 / 2;
    public int findRepeatedNumber(int[] input) {
        int sum = 0;
        for (int i : input) {
            sum += i;
        }
        return sum - SUM_1_TO_1000;
    }
}

Задача 4

Заданы два числа a, b. Поменять их значения местами без использования промежуточной переменной (то есть использовать можно только a, b и арифметические операции).

Решение

a = a + b;
b = a - b;
a = a - b;

Задача 5

Что такое полиморфизм? Приведите примеры.

Решение

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

Рассмотрим такой пример полиморфизма на Java.

interface SearchEngine {
    void search();
}
class GoogleEngine implements SearchEngine {
    @Override
    public void search() {
        System.out.println("search on google");
    }
}
class YandexEngine implements SearchEngine {
    @Override
    public void search() {
        System.out.println("search on yandex");
    }
}
public class Main {
    public static void main(String[] args) {
        GoogleEngine google = new GoogleEngine();
        YandexEngine yandex = new YandexEngine();
        searchOn(google);   // print "search on google"
        searchOn(yandex);   // print "search on yandex"
    }   
    private static void searchOn(SearchEngine engine) {
        engine.search();       
    }
}

В этом примере в метод searchOn мы передаем объекты двух разных типов, и внутри searchOn объекты разных типов обработались единообразно и выполнили разные действия. Это был пример динамического полиморфизма — какой метод будет вызван, определяется во время выполнения программы.

Рассмотрим еще пример полиморфизма.

public class Main {
    public static void main(String[] args) {
        int maxI = Math.abs(10);
        double maxD = Math.abs(10.0);
    }
}

Тут в функцию Math.abs мы передаем объекты разных типов (int и double), но при этом разные типы обрабатываются единообразно, и в результате получаем абсолютное значение числа. Это пример статического полиморфизма — какой метод будет вызван, определяется на этапе компиляции.

Задача 6

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

Перекидывать фонарик, идти навстречу, переплывать, останавливаться — нельзя. Задача решаема.

Решение

• Обозначим людей, которые переходят мост за 1, 2, 5 и 10 мин, как 1, 2, 5, 10 соответственно.
• Сначала переходят два человека 1 и 2, 1 возвращается назад.
• Теперь переходят 5 и 10, возвращается назад 2.
• Переходят 2 и 1.
• Получаем суммарное время на переход моста 2 + 1 + 10 + 2 + 2 = 17 минут.

Задача 7

Дана реляционная база данных, которая состоит из трех таблиц.

Написать на SQL программу, которая выведет все компании, где не работает Developer c ID = 3.

Решение

SELECT ID, NAME
FROM Company
WHERE ID NOT IN (
    SELECT ID_COMP
    FROM `Developers&Company`
    WHERE ID_DEV =3
)