Задание 1. Введение

1.1 Проверка скобок

Дана строка str, содержащая только символы (, ), {, }, [, ].

Определить, сбалансированы ли скобки в строке.

Скобки сбаланисрованы, если:

Открывающая скобка должна быть закрыта скобкой такого же типа.
Скобки должна быть закрыты в корректном порядке.
Для каждой закрывающей скобки есть соответсвующая открывающая.

Алгоритм должен работать за время $O(n)$ и память $O(n)$ .

Примеры

Input: str = "[]"
Outout: true

Input: str = "[](){}"
Outout: true

Input: str = "[({})]"
Outout: true

Input: str = "[({}()){}]"
Outout: true

Input: str = "{]"
Outout: false

Input: str = "({)}"
Outout: false

Ограничение

1 <= str.length <= 10000
str состоит только из символов ()[]{}.

Подсказка 1.

Используйте [стек](https://en.cppreference.com/w/cpp/container/stack) символов.

Подсказка 2.

Открывающуюуся скобку положите на вершину стека.

Подсказка 3.

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

1.2 Удалить на месте

Дан массив чисел arr и число val. Удалите из массива arr все вхождения числа val. Порядок элементов должен сохраниться.

Удаление должно происходить на месте без выделения дополнительного куска памяти для массива.

Функция должна вернуть размер нового массива. Размер массива arr не меняется.

Алгоритм должен работать за время $O(n)$ память $O(1)$ .

int removeElementInplace(vector<int>& arr, int val) {
    // TODO
}

Примеры

Input: arr = [4,5,5,4], val = 4
Output: 2, arr = [5,5,_,_]

Input: arr = [0,2,6,6,1,0,4,6], val = 6
Output: 5, arr = [0,2,1,0,4,_,_,_]

Ограничения

0 <= arr.length <= 100
0 <= arr[i] <= 50
0 <= val <= 100

1.3 Вопрос: Поиск дубликатов

Дана последовательность чисел $x_1, x_2, x_3, ..., x_n$ . Покажите, что за время $\Theta(n log(n))$ можно определить, есть ли в этой последовательности два одинаковых числа.

1.4 Вопрос: Как упорядочить таблицу по столбцам?

Дана таблица с тремя столбцами: A(ФИО студента), B(оценка), C(номер группы). Как упорядочить эту таблицу так, чтобы подряд шли студенты одной группы. В этих группах сначала были студенты с большей оценкой, а если совпадают оценки, то студенты были упорядочены по алфавиту их ФИО.

Вопрос на засыпку: а каким свойством должна обладать сортировка, чтобы всё получилось? Любой ли алгоритм сортировки можно использовать?