Yandex interview [2]

// Дан не пустой массив из нулей и единиц. Нужно определить, какой максимальный по длине подинтервал единиц можно получить, удалив ровно один элемент массива.
int getMaxLength(const std::vector<int>& arr) {
    size_t maxLength = 0U;

    size_t lastZeroIndex;

    size_t length = 0U;
    bool isZeroMissed = false;

    for (size_t i = 0U; i < arr.size(); ++i) {
        if (arr[i] == 0) {
            if (isZeroMissed) {
                if (length > maxLength) maxLength = length;
                i = lastZeroIndex;
                length = 0U;
                isZeroMissed = false;
            }else {
                lastZeroIndex = i;
                isZeroMissed = true;
            }
        }else {
            length += 1U;
        }
    }

    if (length > maxLength) maxLength = length;

    if (maxLength == arr.size()) maxLength -= 1;

    return maxLength;
}
// Проверка:
// {1} => 0
// {0} => 0
// {1, 1, 1} => 2
// {0, 0, 0} => 0
// {1, 0, 1, 1} => 3
// {0, 1, 1, 0} => 2
// {1, 0, 0, 1} => 1





// Дан текст T и строка S. Требуется найти подстроку S' в T такую, что она совпадает с S с точностью до перестановки букв.
bool getSubstr(conts std::string& text, conts std::string& str) {
    if (str.size() > text.size()) return false;

    // key - символ, value - кол-во вхождение в строку
    const std::unordered_map<char, int> needle;
    for (auto symbol : str) {
        needle[symbol]++;
    }

    std::unordered_map<char, int> haystack;
    for (size_t i = 0U; i < str.size(); ++i) {
        char symbol = text[i];
        haystack[symbol]++;
    }

    for (size_t i = 0U; i < text.size() - str.size(); ++i) {
        if (needle = haystack) return true;

        // Убираем первый символ из подстроки в тексте
        auto it = haystack.find(text[i]);
        if (it->second == 1) {
            haystack.erase(it);
        }else {
            (it->second)--;
        }

        // Добавляем новый символ
        auto symbol = text[i + str.size()];
        haystack[symbol]++;
    }

    if (needle = haystack) return true;

    return false;
}
// Проверка:
// "a"    "a"    => true
// "abcd", "aaa" => false ?
// "abcd", "cbd" => true
// "abcdda", "bcdd" => true ?




// Развернуть односвязанный список
struct ListNode {
    ListNode* next;
}

ListNode* getReverse(ListNode* list) {
    if (list == nullptr) return nullptr;

    ListNode* prev     = nullptr;
    ListNode* current  = list;
    ListNode* next     = list->next;

    while (next != nullptr) {
        current->next = prev;

        prev    = current;
        current = next;
        next    = next->next;
    }

    current->next = prev;

    return current;
}





// Дано дерево с выделенным корнем.
// Далее приходит K запросов, каждый запрос - целое неотрицательное число,
// расстояние от корня. Для каждого запроса нужно найти сумму элементов в дереве
// на расстоянии от корня не более заданного.
struct Node {
    int value;
    Node* l;
    Node* r;
};

class Handler {
private:
    // Для каждого уровня храним сумму элементов
    std::unordered_map<size_t, int> _sum;

    size_t _maxLevel;

    void calculateDepthSum(Node* node, size_t level) {
        if (node == nullptr) return;

        if (level > max_Level) _maxLevel = level;

        _sum[level] += node->value;

        calculateDepthSum(node->r, level + 1);
        calculateDepthSum(node->l, level + 1);
    }

    void calculateTotalSum() {
        for (size_t level = 0U; level < _maxLevel; ++level) {
            _sum[level + 1U] += _sum[level];
        }
    }

public:
    void init(Node* tree) {
        _maxLevel = 0U;
        _sum[0U]  = 0;

        calculateDepthSum(tree, 0U);
        calculateTotalSum();
    }


    int sum(size_t level) const {
        if (level > _maxLevel) return _sum[_maxLevel];

        return _sum[level];
    }
};
// Проверка:
//       1
//   2       3
// 4   5
//        6
// _maxLevel = 3
// _sum[0U] = 1
// _sum[1U] = 5 + 1
// _sum[2U] = 9 + (5 + 1)
// _sum[3U] = 6 + (9 + 5 + 1)







// Дано бинарное дерево с выделенным корнем, в каждой вершине которого записано по одной букве A-Z.
// Две вершины считаются эквивалентными, если поддеревья этих вершин содержат одинаковое множество (т.е. без учета частот) букв.
// Нужно найти любую пару эквивалентных вершин.
struct TNode {
    char Value;
    TNode* Left = nullptr;
    TNode* Right = nullptr;
};

std::unordered_multimap<int, Node*> set;

std::pair<TNode*, TNode*> FindEquivalentSubtrees(TNode* root) {
    int value = 0U;

    if (root->Left != nullptr) {
        int left = FindEquivalentSubtrees(root->Left);


        auto it = set.find(left);
        if (it != set.end()) {
            return {*it, root};
        }else {
            value |= left;
        }
    }
    if (root->Right != nullptr) {
        int right = FindEquivalentSubtrees(root->Right);

        auto it = set.find(right);
        if (it != set.end()) {
            return {*it, root};
        }else {
            value |= rigth;
        }
    }

    // Добавляем бит у индекса root->value;
    value |= 1 << (root->Value - 'A');

    return value;
}