osxmagic.com | блог об OS X Вопрос 1

Код C++ 
1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24

class Foo
{
public:
    Foo(int j) { i=new int[j]; }
    ~Foo() { delete i; }
private:
    int* i;
};
class Bar: Foo
{
public:
    Bar(int j) { i=new char[j]; }
    ~Bar() { delete i; }
private:
    char* i;
};
void main()
{
    Foo* f=new Foo(100);
    Foo* b=new Bar(200);
    *f=*b;
    delete f;
    delete b;
}                      
Перечислите все проблемы, которые вы видите в данном коде:
пример ответа

• У Foo нет конструктора по умолчанию. А в конструкторе Bar базовый класс Foo никак не инициализируется существующим конструктором Foo::Foo(int j)
• В строчке Foo* b = new Bar(200) будет ошибка из-за того, что наследование по умолчанию "private". Нужно поставить ключевое слово public перед Foo в строчке class Bar: Foo.
• Массивы нужно удалять оператором delete[].
• Деструктор в Foo нужно сделать виртуальным, иначе в данном случае не вызывается Bar::~Bar()
• char* i; поле i определено в классе Foo.С точки зрения компилятора всё правильно, т. к. char* i и int* i находятся в разных пространствах имен. Но это может запутать программиста
• В конструкторах, желательно, сделать отдельную инициализацию, если j не положительное или нулевое.
• Строка *f=*b; - утечка памяти.


Вопрос 2
Какие из следующих стандартных контейнеров позволяют найти в них элемент (по его значению) за O(ln(n))?
std::set
std::multiset
std::hash_set
std::vector
std::list
std::deque
сортированный std::vector
сортированный std::list
сортированный std::deque
сортированный std::set
сортированный std::multiset
сортированный std::hash_set

Аргументируйте ответ, прокомментируйте правильность постановки вопроса:
пример ответа
сложность O(ln(n)) — будем использовать более привычное — логарифм, без упоминания основания, т.е. O(log n).
1. std::vector — невозможно использовать бинарный алгоритм поиска, сложность O(n)
2. std::list — невозможно использовать бинарный алгоритм поиска, сложность O(n)
3. std::deque — невозможно использовать бинарный алгоритм поиска, сложность O(n)
4. std::set — имеет "встроенный" find, сложность O(log n)
5. std::multiset — имеет "встроенный" find, сложность O(log n)
6. hash_set — (скорее всего, пока не включен в состав STL, отсутствует сайте http://cplusplus.com/reference/stl/ и в справочнике по STL от 2010 года ) — постоянное время поиска O(С)
7. сортированный std::vector — используем бинарный алгоритм поиска, сложность O(log n)
8. сортированный std::list — нет итератора произвольного доступа, сложность O(n)
9. сортированный std::deque — используем бинарный алгоритм поиска, сложность O(log n)
10. сортированный std::set — имеет "встроенный" find, сложность O(log n)
11. сортированный std::multiset — имеет "встроенный" find, сложность O(log n)
12. сортированный hash_set — (скорее всего, пока не включен в состав STL, отсутствует сайте http://cplusplus.com/reference/stl/ и в справочнике по STL от 2010 года ) — постоянное время поиска, сложность O(С)
Замечания:
• Некоторые функции поиска требуют сортировки.
• Часто наилучший результат для сортированных данных достигается при использовании бинарных алгоритмов, например, таких как, binary_search. Эффективность алгоритма O(log n) может быть ограничена способом доступа к элементам контейнера O(n) итератором.
• Сортированный std::multiset и сортированный std::set - это условность, т.к. ассоциативный контейнер всегда отсортирован по критерию. Хотя в составе STL с 2011 года появились std::unordered_set, std::unordered_multiset (по имеющимся тестам на форумах равнозначны по скорости поиска аналогам из Boost).



Вопрос 3
Есть приложение, написанное на C++ под Linux, производительность которого необходимо серьезно улучшить. Расскажите, как можно найти его «узкие места», и какие инструменты вы станете для этого использовать.
пример
Найти «узкие места» приложения можно найти профилировкой, т.е. измерением производительности как всей программы в целом, так и отдельных ее фрагментов, с целью нахождения тех участков программы, на выполнение которых расходуется наибольшее количество времени.
Согласно правилу "10/90", десять процентов кода "съедают" девяносто процентов производительности системы.
Основой прирост оптимизации дает алгоритмическая оптимизация. Никакая оптимизация не позволит существенно увеличить эффективность пузырьковой сортировки или процедуры линейного поиска. Переход к быстрой сортировке (quick sort) и двоичному поиску сократят время обработки данных(в убедился, решая задачи по спортивному программированию с существенным ограничением по времени выполнения программы). Поэтому, если программа выполняется слишком медленно, лучше поискать более эффективные математические алгоритмы(в случае получения информации из БД необходимо переработать запросы, например, один «тяжелый» запрос разбить на несколько простых «легких»).
Обнаружив профайлером узкие места в программе, следует избавиться от затратных арифметических операций, свести к минимуму ветвления, развернуть циклы с малым количеством итераций, отказаться, когда это возможно, от рекурсивных вызовов, в крайнем случае, попробовать сменить компилятор.
Наиболее распространенные профайлеры для Linux:
gprof - невозможность отлаживать многопоточные программы. Для использования необходимо собирать программу с ключем -pg.
Valgrind - помимо профилирования умеет отслеживать утечки ресурсов, ошибки при работе с памятью и ошибки в многопоточных программах.


Вопрос 3

В чем разница между public и private наследованием?
• private наследования не существует
• нет никакой разницы
• при private наследовании все методы базового класса становятся приватными, при public— публичными
• public наследует интерфейс, private— реализацию

пример
Наиболее правильный ответ из предложенных вариантов: public наследует интерфейс, private— реализацию.
Публичное наследование – это наследование интерфейса (наследование типа).
При публичном наследовании открытые (публичные) поля и методы родительского класса остаются открытыми Производный класс является подтипом родительского Производный класс служит примером отношения «является» (is a) Производный класс является объектом родительского.
Примеры: «Собака является животным», «Прямоугольник является замкнутой фигурой» .
Приватное наследование – это наследование реализации.
При приватном наследовании открытые и защищенные поля и методы родительского класса становятся закрытыми полями и методами производного. Производный класс напрямую не поддерживает открытый интерфейс базового, но пользуется его реализацией, предоставляя собственный открытый интерфейс. Производный класс служит примером отношения «реализован на основе» (implemented as) Производный класс реализован на основе родительского.
Примеры: «Класс Stack реализован на основе класса Array»


Вопрос 3

Базы данных/SQL.
Вам нужно создать в MySQL таблицу со следующей структурой:
Код MySQL
1
2
3
4
5

CREATE TABLE `URL_IDS` (
`ID` INTEGER(11) NOT NULL AUTO_INCREMENT,
`PICTURE_ID` INTEGER(11) NOT NULL UNIQUE,
`URL` VARCHAR(255) NOT NULL,
PRIMARY KEY (`ID`, `URL`))TYPE=MyISAM ;
и быстро вставить в нее 100M записей из файла.


пример ответа
Использовал графический(GTK+) центр управления MySQL (GMySQLcc)
С версии MySQL 5.0 вместо TYPE используется — ENGINE.
Вводил следующие команды:
//1.Создаем БД
Код MySQL 
1

CREATE DATABASE forum;
//2.Создаем требуемую таблицу
Код MySQL 
1

CREATE TABLE `URL_IDS` (`ID` INTEGER(11) NOT NULL AUTO_INCREMENT,`PICTURE_ID` INTEGER(11) NOT NULL UNIQUE,`URL` VARCHAR(255) NOT NULL,PRIMARY KEY (`ID`, `URL`))ENGINE=MyISAM ;
//3.Отключаем индексы
Код MySQL 
1

ALTER TABLE `URL_IDS` DISABLE KEYS;
//4.Загружаем быстро данные из файла
//В документации сказано, что данный способ быстрее в 20 раз, чем использование команды INSERT.
Код MySQL 
1

LOAD DATA INFILE 'test.txt' IGNORE INTO TABLE `URL_IDS` FIELDS TERMINATED BY ',' ENCLOSED BY '' ESCAPED BY '\\' LINES TERMINATED BY '\n' STARTING BY '';
//5.Включаем индексы
Код MySQL 
1

ALTER TABLE `URL_IDS` ENABLE KEYS;


Вопрос 4
Код C++
1
2
3

class A {
      void f();
};
чему равен sizeof(A):
Объясните свой ответ:

пример
Код C++ 
1

sizeof(A) == 1;
sizeof(A) - имеет фактически нулевой размер(размер пустой структуры), но потому, что язык требует, чтобы разные экземпляры одного и того же класса имеют разные указатели, они не могут иметь размер нуля - так что компилятор делает их, как он может, например, 1 байт.
Не виртуальные функции не дают вклада в размер. Функции не имеют ничего общего с ним. Ничего не нужно хранить в объекте, чтобы иметь возможность вызвать его не виртуальные функции-члены.


Вопрос 4
Есть класс CodeGenerator, который умеет генерировать Код на разных языках.

Код C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class CodeGenerator
{
public:
    enum Lang {JAVA, C_PLUS_PLUS, PHP};
    CodeGenerator(Lang language) { _language=language; }
    std::string generateCode()
    {
        switch(_language) {
        case JAVA:        //return generated java code
        case C_PLUS_PLUS: //return generated C++ code
        case PHP:         //return generated PHP code
        }
        throw new std::logic_error("Bad language");
    }
    std::string someCodeRelatedThing() // used in generateCode()
    {
        switch(_language) {
        case JAVA:        //return generated java-related stuff
        case C_PLUS_PLUS: //return generated C++-related stuff
        case PHP:         //return generated PHP-related stuff
        }
        throw new std::logic_error("Bad language");
    }
 
private:
    Lang _language;
}
Исходя из предположения, что количество языков будет увеличиваться, предложите refactoring Кода. Аргументируйте преимущество вашего Кода над существующим.
пример

Предполагая, что количество языков будет увеличиваться, необходимо спроектировать класс, который дает возможность записывать требуемые(желаемые пользователем) для генерации языки, генерировать Код согласно имеющихся для данного языка правил генерации. Т.е. необходимо записывать в БД языки, правила генерации для них и, в последствии , при наличии правил, производить генерацию.
Преимущества предложенного Кода:
• гибкость и возможности редактированием правил генерации изменять параметры генерации, добавления новых языков не меняя существующий Код класса
•запись и возможное получение статистики по требуемым пользователем языков для генерации
Код C++ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

class CodeGenerator
{
public:
    CodeGenerator()  {}
    ~CodeGenerator()
    {
    //закрытие соединений с БД
    }
    enum TypeGenering {RELATED_STUFF,NORMAL};
    // Получение из БД правила для генерации языка
    std::string GetRules(std::string language , TypeGenering TypeOfGenereted)
    {
    }
    // Запись в БД правила для генерации языка
    // так же, осуществляется запись пометки,
    //что для языка есть возможность генерации
    void SetRules(std::string& language , TypeGenering TypeOfGenereted)
    {
    }
    //Добавление возможного языка в БД
    void AddLang(std::string& language)
    {
    }
    // Получение из БД списка языков, доступных к генерации
    // т.е. для которых в БД существуют действующие правила генерации
    std::vector<std::string> listLangReadyForUse()
    {
    }
//генерирование Кода
    std::string generateCode(std::string& language ,TypeGenering TypeOfGenereted )
    {
        //1. Проверка на наличие language в std::vector listLangReadyForUse()
        //2. В случае присутствия в списке, генерация
        //в зависимости от TypeGenering TypeOfGenereted,
        //с использованием метода  GetRules()
        // возврат требуемого сгенерированного значения
        //3. В случае отсутствия запись в БД с помощью AddLang()
        // для ведения статистики по требуемым для пользователя языкам
        // возврат значения предупреждающего пользователя, что генерация введенного им языка еще находится в разработке,
    }
};


Вопрос 5
Допустим, в MySQL есть две таблицы:
В таблице users хранятся имена пользователей
CREATE TABLE users (
user_id int unsigned not null,name varchar(100) not null);
В таблице messages хранятся сообщения, отправленные пользователями
CREATE TABLE messages (user_id int unsigned not null, msg_text text not null);
Напишите запрос, выводящий полный список пользователей и для каждого пользователя количество сообщений.
Например:
+------+-----+
| name | cnt |
+------+-----+
| Вася | 4 |
| Петя | 0 |
+------+-----+
Какие индексы нужно построить?
пример
1:
Код MySQL 
1
2

ALTER table 'users' ADD CONSTRAINT PRIMARY KEY (user_id);
ALTER table users ADD KEY (name);
При необходимости, которая могла бы возникнуть в процессе использования таблицы 'users', возможно, создали бы еще составной индекс из user_id + name, но, в данном случае, он не нужен.
Код MySQL 
1

ALTER table messages ADD KEY (user_id);
Создаем временную таблицу, создаем у нее индекс по `user_id`, используем ее в левом соединении, затем удаляем.
2.Запрос:
Код MySQL 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

CREATE TEMPORARY TABLE temp
SELECT
`user_id`,
COUNT(*) AS cnt
FROM `messages`
GROUP BY `user_id`;
ALTER table temp ADD KEY (user_id);
SELECT
name AS name,
IFNULL(tempTable.cnt,0) AS cnt  
FROM users
LEFT JOIN temp AS tempTable ON users.user_id = tempTable.user_id
ORDER BY name;
DROP TABLE temp;