Популярные вопросы на собеседовании по C++ и ответы на них
Те, кто занимается программированием рано или поздно сталкивается с необходимостью прохождения технического собеседования у потенциального работодателя.
О том, что спрашивают на собеседовании у C++ программистов, а также об ответах на эти вопросы и пойдет речь в данном посте.
Зачем нужен виртуальный деструктор?
Ответ: Чтобы избежать возможной утечки ресурсов или другого неконтролируемого поведения объекта, в логику работы которого включен вызов деструктора.
Пример:
class Base
{
public:
virtual ~Base()
{
std::cout << "Hello from ~Base()" << std::endl;
}
};
class Derived : public Base
{
public:
virtual ~Derived()
{
// Здесь могла бы быть очистка ресурсов
std::cout << "Hello from ~Derived()" << std::endl;
}
};
Base *obj = new Derived();
delete obj;
Output:
Hello from ~Derived()
Hello from ~Base()
Без ключевого слова virtual у родительского класса Base деструктор порожденного класса не был бы вызван. Т.е. вызвался бы только ~Base():
Output:
Hello from ~Base()
Что стоит помнить при использовании исключений в конструкторе объекта?
Ответ: Если исключение не обработано, то c логической точки зрения разрушается объект, который еще не создан, а с технической, так как он еще не создан, то и деструктор этого объекта не будет вызван.
Пример:
class Base
{
private:
HANDLE m_hFile;
public:
Base()
{
std::cout << "Hello from Base()" << std::endl;
m_hFile = ::CreateFileA(...);
// Вызываем код, который в ходе своего выполнения бросает исключение
SomeLib.SomeFunc(...);
}
virtual ~Base()
{
std::cout << "Hello from ~Base()" << std::endl;
// Здесь мы планировали закрыть хэндл
::CloseHandle(m_hFile);
}
};
try
{
Base b;
}
catch(const std::exception &e)
{
std::cout << "Exception message: " << e.what() << std::endl;
}
Output:
Hello from Base()
Exception message: Something failed
Я немного модифицировал предыдущий пример, чтобы проблема была наглядней. Здесь объект m_hFile (если был открыт) утечет т.к. до CloseHandle() выполнение не дойдет. Т.е. имеем такие же проблемы как в первом примере: возможная утечка ресурсов или другие проблемы из-за нарушения логики работы класса.
Здесь могут спросить: «Как бы вы поступили при подобной ситуации». Правильный ответ: «Воспользовался бы умными указателями». Простой пример умного указателя:
class Base
{
private:
class CHandle
{
public:
~CHandle()
{
::CloseHandle(m_handle);
}
private:
HANDLE m_handle;
public:
// Для полноценного smart pointer'а перегрузки одной операции
// не достаточно, но для нашего примера и понимания вполне хватит
void operator = (const HANDLE &handle)
{
m_handle = handle;
}
};
CHandle m_hFile;
public:
Base()
{
std::cout << "Hello from Base()" << std::endl;
m_hFile = ::CreateFileA(...);
// Вызываем код, который в ходе своего выполнения бросает исключение
SomeLib.SomeFunc(...);
}
virtual ~Base()
{
std::cout << "Hello from ~Base()" << std::endl;
}
...
Теперь и без вызова деструктора Base хэндл будет закрыт, т.к. при уничтожении класса Base будет уничтожен объект m_hFile класса CHandle, в деструкторе которого и будет закрыт хэндл.
Изобретать велосипед, конечно, не надо, все уже написано до нас, это пример который можно написать на бумажке при соответствующем вопросе. А так есть boost, Loki, ATL и т.п., где это уже реализовано.
Для каких целей применяется ключевое слово const?
Ответ:
- Позволяет задать константность объекта
- Позволяет задать константность указателя
- Позволяет указать, что данный метод не модифицирует члены класса, т.е. сохраняет состояние объекта
Пример 1. Не можем изменить значение объекта:
const int i = 1;
i = 2; // error C3892: 'i' : you cannot assign to a variable that is const
Пример 2. Не можем изменить указатель на объект:
int i = 1;
int* const j(&i);
int k = 2;
*j = k; // Ok
j = &k; // error C3892: 'j' : you cannot assign to a variable that is const
Пример 3. Не можем изменить члены класса:
class Foo
{
private:
int i;
public:
void func() const
{
i = 1; // error C3490: 'i' cannot be modified because it is being accessed through a const object
}
};
Дополнение: константный метод может изменять члены класса, если они объявлены как mutable.
Можете ли вы написать пример какого-нибудь алгоритма сортировки?
Ответ: Пузырьковая сортировка, для контейнеров, без временных переменных:
void sort(vector <int> & arr){
for(size_t i = 0; i < arr.size() - 1; ++i){
for(size_t j = i; j + 1 > 0; j--){
if(arr[j] > arr[j + 1])
std::swap(arr[j], arr[j + 1]);
}
}
}
vector <int> arr = {5,8,3,0,7,15,42};
sort(arr);
for(auto & item : arr)
cout << " ^^^^^^ " << item << endl;
или
void sort(vector <int> & arr){
for(size_t i = 0; i < (arr.size() - 1); ++i){
for(size_t j = i; j + 1 > 0; j--){
if(arr[j] > arr[j + 1])
arr[j] = arr[j] + arr[j + 1] - (arr[j + 1] = arr[j]);
}
}
}
vector <int> arr = {5,8,3,0,7,15,42};
sort(arr);
for(auto & item : arr)
cout << " ^^^^^^ " << item << endl;
Можете ли вы написать код для переворота строки?
Ответ: Код переворота строки для контейнеров, без временных переменных, не осуществляющий прохода по всей строке:
void invert(string & str){
for(size_t i = 0; i < (str.length() / 2); ++i){
std::swap(str[i], str[str.length() - i - 1]);
}
}
string str = "abcdefg";
invert(str);
cout << " ^^^^^^^^^^^^^ " << str << endl;
или
void invert(string & str){
for(size_t i = 0; i < (str.length() / 2); ++i)
str[i] = str[i] + str[str.length() - i - 1] - (str[str.length() - i - 1] = str[i]);
}
string str = "abcdefg";
invert(str);
cout << " ^^^^^^^^^^^^^ " << str << endl;
Как защитить объект от копирования?
Ответ: Сделать private конструктор копирования и оператор =.
Пример:
class NonCopyable
{
public:
NonCopyable(){}
private:
NonCopyable(NonCopyable&){}
private:
void operator=(const NonCopyable&){}
};
NonCopyable a;
NonCopyable b = a; // error C2248: 'NonCopyable::NonCopyable' : cannot access private member
a = b; // error C2248: 'NonCopyable::operator =' : cannot access private member
В чем разница между struct и class?
Ответ: Практически ни в чем. В struct модификаторы доступа по умолчанию public, в class private. Также отличается и наследование по умолчанию, у struct — public, у class — private.
Пример:
struct Foo
{
int i;
};
class Bar
{
int i;
};
Foo a;
a.i = 1; // Ok
Bar b;
b.i = 1; // error C2248: 'Bar::i' : cannot access private member declared in class 'Bar'
Каким свойством должен обладать объект, чтобы его можно было добавить в ассоциативные контейнеры в качестве ключа?
Ответ: Т.к. значения в ассоциативных контейнерах хранятся отсортированными, то объект должен реализовывать оператор сравнения <, а остальные операторы сравнения могут быть выражены через него.
Пример:
struct Foo
{
int i;
};
inline bool operator < (const Foo & lhs, const Foo & rhs)
{
return lhs.i < rhs.i;
}
std::set<Foo> data;
Foo a, b, c;
a.i = 7;
b.i = 1;
c.i = 6;
data.insert( a );
data.insert( b );
data.insert( c );
// Теперь в data элементы находятся в последовательности 1 6 7
Без реализации operator < объект класса Foo нельзя было бы добавить в set, т.к. был бы не определен их порядок внутри set’а.
Для нахождения элемента в контейнеры STL сам определяет недостающие операторы из оператора меньше. Так например, чтобы вычислить нужный элемент STL проверяет меньше ли он текущего, далее больше ли, и если оба условия ложны значит элемент эквивалентен искомому.
Помимо этого, для контейнеров может быть определен класс сравнения (Comparison class), в котором будет определена логика сравнения объектов, реализованная через тот же оператор меньше.
Сколько в памяти занимает произвольная структура?
Ответ: sizeof всех членов + остаток для выравнивания (по умолчанию выравнивание 4 байта) + sizeof указателя на vtable (если есть виртуальные функции) + указатели на классы предков, от которых было сделано виртуальное наследование (размер указателя * количество классов)
Пример:
struct Foo
{
int i;
char a;
};
int size = sizeof(Foo); // 8 байт, хотя int + char = 5. Все дело в дефолтном выравнивании равном 4, т.е. размер должен быть кратен блоку в 4 байта.
// Установим выравнивание в 1 байт
#pragma pack(push, 1)
struct Foo
{
int i;
char a;
};
#pragma pack(pop)
int size = sizeof(Foo); // 5 байт
Как сгенерировать pure virtual function call исключение?
Ответ: Нужно вызвать чисто виртуальный метод в конструкторе родительского класса т.е. до создания дочернего, в котором этот метод реализован. Т.к. современный компилятор не даст это сделать напрямую, то нужно будет использовать промежуточный метод.
Пример:
class Base
{
public:
Base()
{
base_func();
}
void base_func()
{
func(); // pure virtual function call exception
}
virtual void func() = 0;
};
class Derived : public Base
{
public:
virtual void func()
{
}
};
В чем отличие vector от deque?
Ответ: Здесь вспоминают о наличии у deque методов push_front и pop_front. Но основное отличие в организации памяти, у vector она как у обычного Си-массива, т.е. последовательный и непрерывный набор байт, а у deque это фрагменты с разрывами. За счет этого отличия vector всегда можно привести к обычному массиву или скопировать целиком участок памяти, но зато у deque операции вставки/удаления в начало быстрее (O(1) против O(n)), ввиду того, что не нужно перемещать остальные значения.
Что дают разные модификаторы при наследовании?
Ответ: Изменяют зону видимости членов базового класса.
Пример:
class Base
{
public:
int i;
};
class Derived : private Base
{
// i теперь имеет модификатор доступа private
};
class Derived2 : private Derived
{
public:
Derived2()
{
i = 2; // error C2247: 'Base::i' not accessible because 'Derived' uses 'private' to inherit from 'Base'
}
};
Derived d;
d.i; // error C2247
При private наследовании protected и public члены становятся private. При protected наследовании public становится protected. А при public ничего не изменяется.
Что такое инкапсуляция?
Ответ (Wiki): Инкапсуляция — свойство языка программирования, позволяющее объединить и защитить данные и код в объектe и скрыть реализацию объекта от пользователя (прикладного программиста). При этом пользователю предоставляется только спецификация (интерфейс) объекта.
Пользователь может взаимодействовать с объектом только через этот интерфейс. Реализуется с помощью ключевого слова: public.
Пользователь не может использовать закрытые данные и методы. Реализуется с помощью ключевых слов: private, protected.
Что такое полиморфизм?
Ответ (Wiki): Возможность объектов с одинаковой спецификацией иметь различную реализацию.
Пример:
class Figure
{
...
void Draw() const;
...
};
class Square : public Figure
{
...
void Draw() const;
...
};
class Circle : public Figure
{
...
void Draw() const;
...
};
Т.е. есть базовый класс фигура, и от него унаследованы два класса квадрат и круг, имеющие собственную реализацию метода Draw().
В чем отличие malloc от new?
Ответ: malloc — выделение блока памяти в стиле Си, опасное с точки зрения приведения типов (non-typesafe), т.к. возвращает void * и требует обязательного приведения. new — выделение блока памяти и последующий вызов конструктора, безопасное с точки зрения приведения типов (typesafe), т.к. тип возвращаемого значения определен заранее.
Что такое чисто виртуальный метод и абстрактный класс?
Ответ: Чисто виртуальный метод — это метод, у которого отсутствует реализация. Абстрактный класс — это класс имеющий хотя бы один чисто виртуальный метод. Как следствие, экземпляр подобного класса не может быть создан т.к. отсутствует реализация виртуального метода.
Пример:
// Абстрактный класс
class Foo
{
public:
// Чисто виртуальный метод
virtual void func() = 0;
};
class Bar : public Foo
{
public:
virtual void func()
{
}
};
Foo f; // error C2259: 'Foo' : cannot instantiate abstract class
Bar b; // Ok
Для чего используется вызов throw без аргументов?
Ответ: Для повторного возбуждения предыдущего исключения и направления его следующему обработчику.
Пример:
try
{
//....
try
{
// Call something
}
catch(const std::exception& )
{
// Make/Check something..
throw; // Пересылаем исключение следующему обработчику
}
//...
}
catch(const std::exception& e)
{
std::cout << e.what() << std::endl;
}
В чем различия между delete и delete [] ?##
Ответ: delete предназначен для уничтожения объектов, память под которые выделена при помощи new(). delete [] для объектов выделенных при помощи оператора new [] ().
Пример:
class Foo
{
};
Foo *pFoo = new Foo();
delete pFoo;
Foo *pFooArray = new Foo[10]();
delete[] pFoo;
При неправильном использовании оператора delete (например, delete вместо delete []) результат будет: undefined behavior.
Что стоит учитывать при использовании auto_ptr?
Ответ: Так как данный умный указатель реализует подход разрушающего копирования, то при присвоении его другому умному указателю оригинальный потеряет свое значение. А так же его нельзя использовать в стандартных STL контейнерах.
Пример:
std::auto_ptr<Foo> a(new Foo);
std::auto_ptr<Foo> b;
b = a; // a больше не ссылается на Foo
std::vector<std::auto_ptr<Foo>> v;
v.push_back(b); // error C2558: class 'std::auto_ptr<_Ty>' : no copy constructor available or copy constructor is declared 'explicit'
Также ввиду того, что в деструкторе auto_ptr вызывается оператор delete, нельзя хранить объекты созданные при помощи new [] (). Именно из-за этого нюанса boost предоставляет умные указатели в двух вариантах, для просто объекта и их коллекции, например, shared_ptr и shared_array.
Для чего используется ключевое слово volatile?
Ответ: Для указания компилятору, что доступ к переменной может осуществляться из мест, неподконтрольных ему. А как следствие, что работу с данной переменной не нужно подвергать разного рода оптимизациям.
Пример:
volatile int i = 1; // Независимо от прочего кода, данная переменная не будет оптимизирована.
Т.е. если volatile присутствует в каком-то условии, которое не меняется со временем, то компилятор может оптимизировать его, чтобы избежать ненужных проверок, при использовании volatile компилятор скорее всего не будет этого делать.
Пример:
while (1)
{
if(i == 1)
{
// Какой-то код не изменяющий i
}
}
// Если бы volatile отсутствовало, то компилятор мог бы переделать код на что-то аля:
if(i == 1) // Нет необходимости проверять i все время, если и так известно, что оно не изменяется
{
while (1)
{
// Какой-то код не изменяющий i
}
}
В чем различия между dynamic_cast и reinterpret_cast?
Пример:
xxx_cast <type_to> (expression_from)
Динамическое приведение - это безопасное приведение по иерархии наследования, в том числе и для виртуального наследования. Проводит преобразование типа, предварительно убедившись (с помощью RTTI), что объект expression_from в действительности является объектом типа type_to. Если нет: для указателей возвращает nullptr.
При reinterpret_cast результат не гарантирован, проверки не осуществляются. Ограничения на expression_from: порядковый тип (логический, символьный, целый, перечисляемый), указатель, ссылка. Ограничения на type_to: для порядкового типа или указателя — порядковый тип или указатель. Для ссылки — ссылка.
Для чего нужен аллокатор и как создать свой собственный аллокатор?
Аллокатор это шаблонный класс, который отвечает за выделение памяти и создание объектов. По умолчанию все контейнера используют std::allocator . В языке C++ имеется так же возможность написать свой аллокатор. У своего алокатора должно быть такое объявление:
template <class T>
class my_allocator {
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef T value_type;
pointer allocate(size_type st, const void* hint = 0);
void deallocate (pointer p, size_type st);
void construct (pointer p, const_reference val);
void destroy (pointer p);
template <class U>
struct rebind { typedef allocator<U> other; };
};
В чём суть множественного наследования? Какие проблемы могут возникнуть при его использовании? Как их преодолеть?
Множественное наследование – мощный способ связи классов в C++. С помощью множественного наследования класс может иметь сразу несколько базовых классов, объединяя в себе их свойства. Однако данный метод порождает определенные неудобства, из-за которых множественно наследование отсутствует в таком языке, как Java, к примеру, уберегая программиста от возможных проблем, и вынуждая его строить механизм множественного наследования без порождения выше упомянутых проблем.
Проблемы, собственно говоря, возникают, когда имеет место такая ситуация: Пусть класс A – базовый, далее классы B и С наследуют A, к классу D применено множественное наследование - для него базовыми являются одновременно B и C. Программа видит эту структуры таким образом:
A(1) A(2)
| |
B C
\ /
D
Теперь, вызывая из D метод, расположенный в A программа сталкивается с неоднозначностью: а из «какого» A вызывать? A(1) или A(2)? Избежать данной проблемы поможет использование ключевого слова virtual, которое превращает класс A в виртуальный класс, так сказать «класс – шаблон». Теперь никакой неоднозначности нет, и ситуация выглядит вот так:
A
/ \
B C
\ /
D
Какая разница между указателями?
int * i = new int[0];
int * j = (int *) malloc(0);
Ответ:
int * i = new int[0];
возвращает ненулевой указатель, а
int * j = (int *) malloc(0);
возвращает нулевой указатель.
int * i = new int[0];
выделит память в GlobalHeap, а
int * j = (int *) malloc(0);
выделит в LocalHeap.
Отсюда в оператора new преимущества в памяти.
В чем основное различие между деструктором и оператором delete?
Оператор delete освобождает область памяти зарезервированную ранее с помощью оператора new. При этом для объектов автоматически будет вызван деструктор. Деструктор содержит код, который необходимо выполнить до освобождения памяти, например, освобождение системных ресурсов и т.д. Вызов деструктора вручную не приводит к освобождению памяти, занимаемой объектом.
Что можно сказать о delete this?
Это выражение считается выражением плохого тона и нужно стараться избегать его использования, так как оно ведет к ошибкам. Данная конструкция имеет две ловушки.
Во-первых, если оно выполняется в методе extern, static или automatic объекта, программа скорее всего завершится досрочно вскоре после выполнения оператора delete. Не существует переносимого способа сообщить, что объект создан на куче, таким образом класс не может проверить корректно ли объект создался.
Во-вторых, при таком самоуничтожении, программа может и не узнать об этом. Для нее объект по-прежнему продолжает существовать, несмотря на то, что это не так. Любое обращение к this или к любым данным объекта приведет к катастрофическим последствиям. При этом методы, которые не содержат обращения к полям-данным объекта, выполняются нормально.
В чем разница между массивом и списком?
Массив – это набор однородных элементов, а список – разнородных. Распределение памяти массива всегда статическое и непрерывное, а в списке все это динамическое и рандомное.
В случае с массивами пользователю не нужно управлять выделением памяти, а при использовании списков придется, из-за ее динамичности.
Обмен значениями двух переменных без использования третьей
Пример1:
int a = 3;
int b = 5;
a = a + b;
b = a - b;
a = a - b;
a = 5
b = 3
Пример 2:
int a = 3;
int b = 5;
a = a * b;
b = a / b; // деление НЕ целочисленное
a = a / b;
Пример 3:
int a = 3;
int b = 5;
a = a + b - (b = a);
Пример 4:
int a = 3;
int b = 5;
a += b - (b = a);
Пример 5:
int a = 3;
int b = 5;
a = a * b / (b = a);
Пример 6:
int a = 3;
int b = 5;
a = a - b;
b = a + b;
a = -a + b;
Пример 7:
int a = 3;
int b = 5;
// XOR
a = a ^ b;
b = b ^ a;
a = a ^ b;
Пример 8:
int a = 3;
int b = 5;
a ^= b;
b ^= a;
a ^= b;
Пример 9:
int a = 3;
int b = 5;
a ^= b ^= a ^= b;
Алгоритмы поиска
- Алгоритм поиска A* — особый случай поиска по первому наилучшему совпадению; используется эвристика, увеличивающая скорость работы алгоритма
- Алгоритм выбора — модификация алгоритма линейного поиска; находит k-й по величине элемент в списке
- Двоичное дерево поиска O(log n), O(n) в худшем случае - использует бинарное дерево для хранения элементов
- Красно-чёрное дерево O(log n) — использует дополнительный атрибут узла дерева — «цвет»
- АВЛ-дерево O(log n) — в каждом узле хранит разницу высот (целое число от −1 до +1)
- Расширяющееся дерево O(log n) — вместо дополнительных полей в узлах дерева «расширяющие операции» выполняются при каждом обращении к дереву
- Двоичный поиск O(log n) — находит элемент в отсортированном списке
- Интерполяционный поиск - предсказывающий поиск, поиск по словарю
- Линейный поиск O(n) — находит элемент в неотсортированном списке
- Локальный поиск - оптимизация
Метод штрафов
- Поиск в глубину — проходит граф ветка за веткой
- Поиск в ширину — проходит граф уровень за уровнем
- Поиск по первому наилучшему совпадению (англ. Best-first search) — проходит граф в порядке важности, используя очередь приоритетов
- Троичный поиск — находит максимум или минимум функции
Поиск в хеш-таблице
- Алгоритм Ли (волновой алгоритм) — поиск пути на карте
Алгоритмы сортировки: algolist
время:
O(n), O(n^2), O(n^2)
память:
O(1), O(1), O(1)
Пузырьковая сортировка - Сортировка пузырьком — это самый простой алгоритм сортировки. Он проходит по массиву несколько раз, на каждом этапе перемещая самое большое значение из неотсортированных в конец массива.
время:
O(n), O(n^2), O(n^2)
память:
O(1), O(1), O(1)
Сортировка вставками - Сортировка вставками работает, проходя по массиву и перемещая нужное значение в начало массива. После того, как обработана очередная позиция, мы знаем, что все позиции до нее отсортированы, а после нее — нет.
время:
O(n), O(n^2), O(n^2)
память:
O(1), O(1), O(1)
Сортировка выбором - Сортировка выбором — это некий гибрид между пузырьковой и сортировкой вставками. Как и сортировка пузырьком, этот алгоритм проходит по массиву раз за разом, перемещая одно значение на правильную позицию. Однако, в отличие от пузырьковой сортировки, он выбирает наименьшее неотсортированное значение вместо наибольшего. Как и при сортировке вставками, упорядоченная часть массива расположена в начале, в то время как в пузырьковой сортировке она находится в конце.
время:
O(n·log n), O(n·log n), O(n·log n)
память:
O(n), O(n), O(n)
Сортировка слиянием - При сортировке слиянием мы разделяем массив пополам до тех пор, пока каждый участок не станет длиной в один элемент. Затем эти участки возвращаются на место (сливаются) в правильном порядке. (Телефонный справочник) Сортировка слиянием также построена на принципе “разделяй-и-властвуй”, однако реализует его несколько по-другому, нежели быстрая сортировка. А именно, вместо разделения по опорному элементу массив просто делится пополам.
время:
O(n·log n), O(n·log n), O(n^2)
память:
O(1), O(1), O(1)
Быстрая сортировка - Быстрая сортировка — это еще один алгоритм типа «разделяй и властвуй». Он работает, рекурсивно повторяя следующие шаги:
- Выбрать ключевой индекс и разделить по нему массив на две части. Это можно делать разными способами, но мы используем случайное число.
- Переместить все элементы больше ключевого в правую часть массива, а все элементы меньше ключевого — в левую. Теперь ключевой элемент находится в правильной позиции — он больше любого элемента слева и меньше любого элемента справа.
- Повторяем первые два шага, пока массив не будет полностью отсортирован.
время:
O(n), O(n × k)
память:
O(n × k)
Поразрядная сортировка 1. алгоритм совсем не использует сравнений сортируемых элементов. 2. Ключ, по которому происходит сортировка, необходимо разделить на части, разряды ключа. Например, слово можно разделить по буквам, число - по цифрам… 3. До сортировки необходимо знать два параметра: k и m, где
k - количество разрядов в самом длинном ключе m - разрядность данных: количество возможных значений разряда ключа
При сортировке русских слов m = 33, так как буква может принимать не более 33 значений. Если в самом длинном слове 10 букв, k = 10. Аналогично, для для шестнадцатиричных чисел m = 16, если в качестве разряда брать цифру, и m = 256, если использовать побайтовое деление. Эти параметры нельзя изменять в процессе работы алгоритма.
время:
O(n^7/6), O(n^4/3).
Сортировка Шелла Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками. Единственной характеристикой сортировки Шелла является приращение - расстояние между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице - метод завершается обычной сортировкой вставками, но именно последовательность приращений определяет рост эффективности.
Структуры данных
Абстрактные структуры данных:
Абстрактные структуры данных предназначены для удобного хранения и доступа к информации. Они предоставляют удобный интерфейс для типичных операций с хранимыми объектами, скрывая детали реализации от пользователя. Конечно, это весьма удобно и позволяет добиться большей модульности программы. Абстрактные структуры данных иногда делят на две части: интерфейс, набор операций над объектами, который называют АТД(абстрактный тип данных) и реализацию. Ниже, где возможно, собственно АТД будут отделены от их реализации. Каждый уже имел дело с простыми абстрактными структурами данных - например, когда оперировал с числами. Языки программирования высокого уровня(Паскаль, Си..) предоставляют удобный интерфейс для чисел: операции +, *, = .. и т.п, но при этом скрывают саму реализацию этих операций, машинные команды.
Список:
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения.
Стек:
Стек - такой последовательный список с переменной длиной, включение и исключение элементов из которого выполняются только с одной стороны списка, называемого вершиной стека. Применяются и другие названия стека - магазин и очередь, функционирующая по принципу LIFO (Last - In - First- Out - “последним пришел - первым исключается”). Примеры стека: винтовочный патронный магазин, тупиковый железнодорожный разъезд для сортировки вагонов.
Очередь FIFO:
Очередью FIFO (First - In - First- Out - “первым пришел - первым исключается”). называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO.
Дек:
Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
Красно-черное дерево:
Красно-черные деревья - один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O(log n).
Красно-черное дерево - это бинарное дерево с следующими свойствами: Каждый узел покрашен либо в черный, либо в красный цвет. Листьями объявляются NIL-узлы (т.е. “виртуальные” узлы, наследники узлов, которые обычно называют листьями; на них “указывают” NULL указатели). Листья покрашены в черный цвет. Если узел красный, то оба его потомка черны. На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.
Слоёные списки:
Слоёные списки - это связные списки, которые позволяют вам пропустить (skip) ненужные элементы, прыгнув сразу к нужному. Это позволяет преодолеть ограничения последовательного поиска, являющегося основным источником неэффективного поиска в списках. В то же время вставка и удаление остаются сравнительно эффективными. Оценка среднего времени поиска в таких списках есть O(lg n). Для наихудшего случая оценкой является O(n), но худший случай крайне маловероятен.
Хеш таблица:
Один из наиболее эффективных способов реализации словаря - хеш-таблица. Среднее время поиска элемента в ней есть O(1), время для наихудшего случая - O(n). Прекрасное изложение
Структуры данных продолжение:
- Стек (Stack) - Последний пришел = Первый ушел
- Очередь (Queue) - Первый пришел = Первый ушел
- Двусторонняя очередь (Deque) - Можно добавлять элементы как с начала так и с конца очереди.
- Массив - структура данных в виде набора компонентов (элементов массива), расположенных в памяти непосредственно друг за другом, что позволяет обращаться к элементам по числовому индексу.
- Список - это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза. Экземпляр списка является компьютерной реализацией математического понятия конечной последовательности.
- Куча - это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ (A) ≥ ключ (B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами). Не существует никаких ограничений относительно того, сколько узлов-потомков имеет каждый узел кучи, хотя на практике их число обычно не более двух.
- Дерево - одна из наиболее широко распространённых структур данных в информатике, эмулирующая древовидную структуру в виде набора связанных узлов. Является связным графом, не содержащим циклы.
- Бинарное дерево - Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.
- Бинарное дерево поиска — это бинарное дерево, обладающее дополнительными свойствами: значение левого потомка меньше значения родителя, а значение правого потомка больше значения родителя для каждого узла дерева.
Чем массив лучше или хуже связанного списка?
- Отвечаешь что в связанном списке удаление элемента занимает O(1), а поиска O(n). Когда в массиве тебе так же надо найти за O(n), а потом еще сдвинуть значения что бы пустого места не было так же за O(n).
Сложность алгоритмов
- O(n) — линейная сложность Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
- O(log n) — логарифмическая сложность Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
- O(n^2) — квадратичная сложность Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n2.
Бывают и другие оценки по сложности, но все они основаны на том же принципе.
- O(1) - контстантная сложность Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1). Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.
Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.
- O(n·log n) - Линеарифметический Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n·log n). Некоторые алгоритмы типа «разделяй и властвуй» попадают в эту категорию.
Отличие указателей от ссылок
- Нельзя объявить массив ссылок.
- У ссылки нет адреса.
- Существует арифметика указателей, но нет арифметики ссылок.
- Указатель может иметь «невалидное» значение с которым его можно сравнить перед использованием. Если вызывающая сторона не может не передать ссылку, то указатель может иметь специальное значение nullptr
- Ссылка не обладает квалификатором const
- Ссылка, в отличии от указателя, не может быть неинициализированной;
- Ссылка не может быть изменена после инициализации.
Отсюда и получаем плюсы и минусы использования того и другого:
- ссылки лучше использовать когда нежелательно или не планируется изменение связи ссылка → объект
- указатель лучше использовать, когда возможны следующие моменты в течении жизни ссылки
- ссылка не указывает ни на какой объект
- ссылка указаывает на разные объекты в течении своего времени жизни
Размерности которые нужно знать
| Power | Exact Value | Approx Value | Bytes |
|---|---|---|---|
| 7 | 128 | ||
| 8 | 256 | ||
| 10 | 1024 | 1 thousand | 1 KB |
| 16 | 65,536 | 64 KB | |
| 20 | 1,048,576 | 1 million | 1 MB |
| 30 | 1,073,741,824 | 1 billion | 1 GB |
| 32 | 4,294,967,296 | 4 GB | |
| 40 | 1,099,511,627,776 | 1 trillion | 1 TB |
Latency Comparison Numbers
| L1 cache reference | 0.5 | ns | |||
| Branch mispredict | 5 | ns | |||
| L2 cache reference | 7 | ns | 14x L1 cache | ||
| Mutex lock/unlock | 25 | ns | |||
| Main memory reference | 100 | ns | 20x L2 cache, 200x L1 cache | ||
| Compress 1K bytes with Zippy | 10,000 | ns | 10 us | ||
| Send 1 KB bytes over 1 Gbps network | 10,000 | ns | 10 us | ||
| Read 4 KB randomly from SSD* | 150,000 | ns | 150 us | ~1GB/sec SSD | |
| Read 1 MB sequentially from memory | 250,000 | ns | 250 us | ||
| Round trip within same datacenter | 500,000 | ns | 500 us | ||
| Read 1 MB sequentially from SSD* | 1,000,000 | ns | 1,000 us | 1 ms | ~1GB/sec SSD, 4X memory |
| HDD seek | 10,000,000 | ns | 10,000 us | 10 ms | 20x datacenter roundtrip |
| Read 1 MB sequentially from 1 Gbps | 10,000,000 | ns | 10,000 us | 10 ms | 40x memory, 10X SSD |
| Read 1 MB sequentially from HDD | 30,000,000 | ns | 30,000 us | 30 ms | 120x memory, 30X SSD |
| Send packet CA->Netherlands->CA | 150,000,000 | ns | 150,000 us | 150 ms |
Notes
1 ns = 10^-9 seconds 1 us = 10^-6 seconds = 1,000 ns 1 ms = 10^-3 seconds = 1,000 us = 1,000,000 ns
Типы данных
| name | value | size |
|---|---|---|
| bool | true и false | 1 |
| signed char | -128 … 127 | 1 |
| unsigned char | 0 … 255 | 1 |
| signed short int | -32 768 … 32 767 | 2 |
| unsigned short int | 0 … 65 535 | 2 |
| signed long int | -2 147 483 648 … 2 147 483 647 | 4 |
| unsigned long int | 0 … 4 294 967 295 | 4 |
| float | 3.4e-38 … 3.4e+38 | 4 |
| double | 1.7e-308 … 1.7C+308 | 8 |
| long double | 3.4e-4932 … 3.4e+4932 | 10 |
Подсчет суммы числа без преобразования в строку
#include <iostream>
using namespace std;
int main(){
int n;
int sum = 0;
cout << "please, enter n = ";
cin >> n;
while (n != 0){
sum += n % 10;
n /= 10;
}
cout << "sum = " << sum << endl;
return 0;
}
Перевод Римских чисел в арабские
#include <string>
class Solution {
public:
int romanToInt(std::string s){
int result = 0;
if(!s.empty()){
char c, o;
u_int i = 0, v = 0, n = 0;
// Преобразовываем цифру M
if(s[0] == 'M'){
for(n = 0; s[i] == 'M'; n++) i++;
if(n > 4) return 0;
v += n * 1000;
}
o = s[i];
// Преобразовываем букву D и C
if((o == 'D') || (o == 'C')){
if((c = o) == 'D'){
i++;
v += 500;
}
o = s[i + 1];
if((c == 'C') && (o == 'M')){
i += 2;
v += 900;
} else if((c == 'C') && (o == 'D')) {
i += 2;
v += 400;
} else {
for(n = 0; s[i] == 'C'; n++) i++;
if(n > 4) return 0;
v += n * 100;
}
}
o = s[i];
// Преобразовываем букву L и X
if((o == 'L') || (o == 'X')){
if((c = o) == 'L'){
i++;
v += 50;
}
o = s[i + 1];
if((c == 'X') && (o == 'C')){
i += 2;
v += 90;
} else if((c == 'X') && (o == 'L')) {
i += 2;
v += 40;
} else {
for(n = 0; s[i] == 'X'; n++) i++;
if(n > 4) return 0;
v += n * 10;
}
}
o = s[i];
// Преобразовываем букву V и I
if((o == 'V') || (o == 'I')){
if((c = o) == 'V'){
i++;
v += 5;
}
o = s[i + 1];
if((c == 'I') && (o == 'X')){
i += 2;
v += 9;
} else if((c == 'I') && (o == 'V')){
i += 2;
v += 4;
} else {
for(n = 0; s[i] == 'I'; n++) i++;
if(n > 4) return 0;
v += n;
}
}
result = (((s.length() == i) && (v >= 1) && (v <= 4999)) ? v : 0);
}
return result;
}
};
Тестовое задание
В данной задаче будут рассматриваться 13-ти значные числа в тринадцатиричной системе исчисления (цифры 0,1,2,3,4,5,6,7,8,9,A,B,C) с ведущими нулями. Например: ABA98859978C0, 6789110551234, 0000007000000 Назовем число красивым, если сумма его первых шести цифр равна сумме шести последних цифр.
Пример:
- Число 0055237050A00 - красивое, так как 0+0+5+5+2+3 = 0+5+0+A+0+0
- Число 1234AB988BABA - некрасивое, так как 1+2+3+4+A+B != 8+8+B+A+B+A
Задача:
написать программу на С/С++ печатающую в стандартный вывод количество 13-ти значных красивых чисел с ведущими нулями в тринадцатиричной системе исчисления.
В качестве решения должен быть предоставлено:
- ответ - количество таких чисел. Ответ должен быть представлен в десятичной системе исчисления.
- исходный код программы.
Пож-та, кроме кода, напишите ответ числом в теле письма.
#include <vector>
#include <iostream>
using namespace std;
typedef class BeautifulNumbers {
private:
vector <uint8_t> _nums;
private:
int64_t way(uint8_t n, uint8_t depth){
if(n < 0) return 0;
if(depth == 0)
return (n == 0 ? 1 : 0);
uint64_t result = 0;
for(auto & num : this->_nums)
result += way(n - num, depth - 1);
return result;
}
public:
int64_t calc(){
uint64_t result = 0, count = 0;
for(uint8_t i = 0; i < 73; i++){
count = this->way(i, 6);
printf("%u = %zu\n", i, count);
result += (count * count);
}
return (result * 13);
}
public:
BeautifulNumbers() : _nums({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}) {}
} bf_t;
int main(){
bf_t bf;
int64_t result = bf.calc();
cout << "RESULT: " << result << endl;
return 0;
}
Отличие static_cast от dynamic_cast
static_cast - выполняет проверку на этапе компиляции. Если типы несовместимые, компиляция завершается с ошибкой.
dynamic_cast - выполняет проверку на этапе выполнения и зависит от механизма динамической информации о типах (RTTI), поэтому его использование влечет за собой некоторые накладные расходы. Если типы несовместимые, dynamic_cast бросает исключение std::bad_cast (для ссылок) или возвращает NULL (для указателей).
dynamic_cast работает только для указателей и ссылок и только для полиморфных классов, связанных открытым наследованием; при попытке использовать его с чем-нибудь другим произойдет ошибка компиляции. Хотя это тоже можно считать одним из проявлений контроля типов.
Основное назначение dynamic_cast - защита от нисходящего приведения типов в тех случаях, когда это лишено смысла. Например, если у вас есть ссылка или указатель на базовый класс, но вы точно знаете, что на самом деле она указывает на экземпляр производного типа, вы можете выполнить приведение и работать с производным типом. Это называется нисходящее приведение. Но если там будет объект базового типа, лишенный своей производной части, такое приведение лишено смысла и приведет к неопределенному поведению.
Ни static_cast, ни тем более приведение в стиле C такую ситуацию не ловят. А dynamic_cast с ней справляется. Помедитируйте над следующим кодом:
#include <iostream>
class abc {
public:
virtual ~abc() {}
};
class def : public abc {
public:
~def() {}
};
template <typename T_TypeTo, typename T_TypeFrom>
void test_casting(T_TypeFrom * p){
std::cout << std::boolalpha << (nullptr != dynamic_cast <T_TypeTo> (p)) << std::endl;
}
int main(){
abc * pAbc = new abc();
def * pDef = new def();
abc * pAbcDef = new def();
test_casting <abc *> (pAbc);
test_casting <abc *> (pDef);
test_casting <abc *> (pAbcDef);
test_casting <def *> (pAbc);
test_casting <def *> (pDef);
test_casting <def *> (pAbcDef);
delete pAbcDef;
delete pDef;
delete pAbc;
return 0;
}