Информация об изменениях

Сообщение Re: Задачки с Amazon SDE Interview от 16.12.2020 17:50

Изменено 16.12.2020 19:05 Sergei MO

Re: Задачки с Amazon SDE Interview
Здравствуйте, Chriso, Вы писали:

C>2. Дан список последовательностей чисел
C>Найти самую часто встречающуюся непрерывную подпоследовательность и сколько раз она встречается.
C>Облегчённый вариант, с которым я также не справился: длина подпоследовательности задана, рассматривать только подпоследовательности этой длины.
C>Очевидное решение с Dictionary, где ключом является сама подпоследовательность не подходит по требуемой памяти, даже в "облегчённом" варианте. Предполагается, что список читается из файла и в память не влезет.

Во-первых, нужно дополнительное условие вроде "среди всех самых часто встречающихся последовательностей найти самую длинную". Иначе допустимым ответом будет последовательность длины 1 из самого часто встречающегося числа.
Во-вторых, было бы неплохо указать остальные ограничения по памяти — влезает ли в память один список, влезает ли в память Dictionary со всеми числами из всех последовательностей, влезает ли в память ответ, и т.д.

Я пока приведу решение для одной последовательности и случая, когда в память влезает всё.

Пусть у нас есть ответ — подпоследовательность, встречающаяся C раз. Тогда для неё выполняются следующие утверждения:
1) Любое число, входящее в эту подпоследовательность, встречается в ней ровно один раз. (Если оно встречается несколько раз, то последовательность длины 1, состоящая из этого числа, встретится k*C раз, т.е. чаще, чем ответ).
2) Любое число, входящее в эту подпоследовательность, встречается в исходной последовательности только во вхождениях ответа. (Если оно встречается где-то ещё, то последовательность длины 1 из этого числа, встретится C+k раз — чаще чем ответ).

Следствием этих утверждений является то, что все последовательности-кандидаты на ответ состоят из непересекающихся множеств чисел.

Решение следующее. На первом проходе считаем вхождения всех чисел, и составляем набор чисел, имеющих максимальное количество вхождений. Ответ будет состоять только из них.
На втором проходе жадным алгоритмом строим последовательности, удовлетворяющие приведенным выше условиям, и выбираем самую длинную из них.
Сложность решения — O(N*Log(N)), где N — длина входной последовательности.

  Код решения 
#include <iostream>
#include <vector>
#include <deque>
#include <map>

using namespace std;


class SequenceSolver
{
public:
    SequenceSolver(vector<int>& sequence);

    int getCount() { return maxCount_; }

    vector<int> getSequence();

private:
    // находит все числа-кандидаты для построения последовательностей
    void buildNumbers(vector<int>& sequence);

    // прекращает построение/проверку активной последовательности
    void terminateCurrentSequence();

    // удаляет из последовательности все элементы, находящиеся левее position
    void trimSequenceLeft(deque<int>& sequence, size_t position);

    // удаляет из последовательности все элементы, начиная с position
    void trimSequenceRight(deque<int>& sequence, size_t position);

    // начинает построение новой последовательности
    void beginSequence(size_t& index, int number);

    // начинает проверку существующей последовательности
    void beginSequenceCheck(size_t index, size_t position);

private:
    static const size_t NONE = (size_t)(-1);

    // числа-кандидаты для построения последовательностей
    // значение - (индекс последовательности, позиция в последовательности)
    map<int, pair<size_t, size_t>> numbers_;

    // последовательности-кандидаты
    vector<deque<int>> sequences_;

    // индекс и текущая позиция активной последовательности
    // (которая строится или проверяется в данный момент)
    size_t activeIndex_;
    size_t activePosition_;

    // true, если активная последовательность встретилась впервые
    bool activeNew_;

    // сколько раз встречается искомая последовательность
    int maxCount_;
};


SequenceSolver::SequenceSolver(vector<int>& sequence) : maxCount_(0), activeIndex_(NONE)
{
    buildNumbers(sequence);

    for (size_t i = 0; i < sequence.size(); i++)
    {
        auto it = numbers_.find(sequence[i]);
        if (it == numbers_.end())
        {
            terminateCurrentSequence();
        }
        else
        {
            if (activeIndex_ == NONE) // нет активной последовательности
            {
                if (it->second.first == NONE)
                {
                    beginSequence(it->second.first, it->first);
                }
                else
                {
                    beginSequenceCheck(it->second.first, it->second.second);
                }
            }
            else if (activeNew_) // есть новая активная последовательность
            {
                if (it->second.first == NONE)
                {
                    // продолжаем новую активную последовательность
                    it->second.first = activeIndex_;
                    it->second.second = activePosition_;
                    sequences_[activeIndex_].push_back(it->first);
                    activePosition_ += 1;
                }
                else
                {
                    // прерываем новую активную последовательность
                    // и начинаем проверку старой активной последовательности
                    terminateCurrentSequence();
                    beginSequenceCheck(it->second.first, it->second.second);
                }
            }
            else // есть старая активная последовательность
            {
                if (it->second.first == NONE)
                {
                    // прерываем старую активную последовательность
                    // и начинаем новую активную последовательность
                    terminateCurrentSequence();
                    beginSequence(it->second.first, it->first);
                }
                else if (it->second.first == activeIndex_ && it->second.second == activePosition_)
                {
                    // продолжаем проверку старой активной последовательности
                    activePosition_ += 1;
                    if (activePosition_ == sequences_[activeIndex_].size())
                    {
                        activeIndex_ = NONE;
                    }
                }
                else
                {
                    // прерываем старую активную последовательность
                    // и начинаем проверку другой старой активной последовательности
                    terminateCurrentSequence();

                    // обработка случая, когда число находится в этой же последовательности но на более
                    // далёкой позиции, например:  [ 1 2 3 4 5 ] и [ 1 2 5 ]
                    if (numbers_.find(sequence[i]) == numbers_.end())
                    {
                        activeIndex_ = NONE;
                    }
                    else
                    {
                        beginSequenceCheck(it->second.first, it->second.second);
                    }
                }
            }
        }
    }
}

vector<int> SequenceSolver::getSequence()
{
    size_t max = 0;
    for (size_t i = 1; i < sequences_.size(); i++)
    {
        if (sequences_[i].size() > sequences_[max].size())
        {
            max = i;
        }
    }

    return vector<int>(sequences_[max].begin(), sequences_[max].end());
}

void SequenceSolver::buildNumbers(vector<int>& sequence)
{
    map<int, int> counts;
    for (size_t i = 0; i < sequence.size(); i++)
    {
        counts[sequence[i]]++;
    }

    maxCount_ = 0;
    for (auto it = counts.begin(); it != counts.end(); ++it)
    {
        maxCount_ = it->second > maxCount_ ? it->second : maxCount_;
    }

    for (auto it = counts.begin(); it != counts.end(); ++it)
    {
        if (it->second == maxCount_)
        {
            numbers_[it->first] = make_pair(NONE, 0);
        }
    }
}

void SequenceSolver::terminateCurrentSequence()
{
    if (activeIndex_ != NONE && !activeNew_)
    {
        trimSequenceRight(sequences_[activeIndex_], activePosition_);
    }
    activeIndex_ = NONE;
}

void SequenceSolver::trimSequenceLeft(deque<int>& sequence, size_t position)
{
    for (size_t i = 0; i < position; i++)
    {
        numbers_.erase(sequence.front());
        sequence.pop_front();
    }

    for (size_t i = 0; i < sequence.size(); i++)
    {
        numbers_[sequence[i]].second -= position;
    }
}

void SequenceSolver::trimSequenceRight(deque<int>& sequence, size_t position)
{
    while (sequence.size() > position)
    {
        numbers_.erase(sequence.back());
        sequence.pop_back();
    }
}

void SequenceSolver::beginSequence(size_t& index, int number)
{
    index = sequences_.size();
    sequences_.push_back(deque<int>());
    sequences_.back().push_back(number);
    activeIndex_ = index;
    activePosition_ = 1;
    activeNew_ = true;
}

void SequenceSolver::beginSequenceCheck(size_t index, size_t position)
{
    trimSequenceLeft(sequences_[index], position);
    activeIndex_ = index;
    activePosition_ = 1;
    activeNew_ = false;
}

int main()
{
    int arr[] = { 1, 2, 3, 4, 0, 4, 2, 3, 2, 3 };
    
    SequenceSolver sol(vector<int>(arr, arr + sizeof(arr) / sizeof(int)));
    vector<int> ans = sol.getSequence();

    cout << "N = " << sol.getCount() << endl;
    cout << ans[0];
    for (size_t i = 1; i < ans.size(); i++)
    {
        cout << " " << ans[i];
    }
    cout << endl;
    return 0;
}
Re: Задачки с Amazon SDE Interview
Здравствуйте, Chriso, Вы писали:

C>2. Дан список последовательностей чисел
C>Найти самую часто встречающуюся непрерывную подпоследовательность и сколько раз она встречается.
C>Облегчённый вариант, с которым я также не справился: длина подпоследовательности задана, рассматривать только подпоследовательности этой длины.
C>Очевидное решение с Dictionary, где ключом является сама подпоследовательность не подходит по требуемой памяти, даже в "облегчённом" варианте. Предполагается, что список читается из файла и в память не влезет.

Во-первых, нужно дополнительное условие вроде "среди всех самых часто встречающихся последовательностей найти самую длинную". Иначе допустимым ответом будет последовательность длины 1 из самого часто встречающегося числа.
Во-вторых, было бы неплохо указать остальные ограничения по памяти — влезает ли в память один список, влезает ли в память Dictionary со всеми числами из всех последовательностей, влезает ли в память ответ, и т.д.

Я пока приведу решение для одной последовательности и случая, когда в память влезает всё.

Пусть у нас есть ответ — подпоследовательность, встречающаяся C раз. Тогда для неё выполняются следующие утверждения:
1) Любое число, входящее в эту подпоследовательность, встречается в ней ровно один раз. (Если оно встречается несколько раз, то последовательность длины 1, состоящая из этого числа, встретится k*C раз, т.е. чаще, чем ответ).
2) Любое число, входящее в эту подпоследовательность, встречается в исходной последовательности только во вхождениях ответа. (Если оно встречается где-то ещё, то последовательность длины 1 из этого числа, встретится C+k раз — чаще чем ответ).

Следствием этих утверждений является то, что все последовательности-кандидаты на ответ состоят из непересекающихся множеств чисел.

Решение следующее. На первом проходе считаем вхождения всех чисел, и составляем набор чисел, имеющих максимальное количество вхождений. Ответ будет состоять только из них.
На втором проходе жадным алгоритмом строим последовательности, удовлетворяющие приведенным выше условиям, и выбираем самую длинную из них.
Сложность решения — O(N*Log(N)), где N — длина входной последовательности. Хотя нет, нашёл ошибку и теперь там O(N*N) вылезает.

  Код решения 
#include <iostream>
#include <vector>
#include <deque>
#include <map>

using namespace std;


class SequenceSolver
{
public:
    SequenceSolver(vector<int>& sequence);

    int getCount() { return maxCount_; }

    vector<int> getSequence();

private:
    // находит все числа-кандидаты для построения последовательностей
    void buildNumbers(vector<int>& sequence);

    // прекращает построение/проверку активной последовательности
    void terminateCurrentSequence();

    // делит последовательность на две по элементу с индексом position
    size_t splitSequence(deque<int>& sequence, size_t position);

    // начинает построение новой последовательности
    void beginSequence(size_t& index, int number);

    // начинает проверку существующей последовательности
    void beginSequenceCheck(size_t index, size_t position);

private:
    static const size_t NONE = (size_t)(-1);

    // числа-кандидаты для построения последовательностей
    // значение - (индекс последовательности, позиция в последовательности)
    map<int, pair<size_t, size_t>> numbers_;

    // последовательности-кандидаты
    vector<deque<int>> sequences_;

    // индекс и текущая позиция активной последовательности
    // (которая строится или проверяется в данный момент)
    size_t activeIndex_;
    size_t activePosition_;

    // true, если активная последовательность встретилась впервые
    bool activeNew_;

    // сколько раз встречается искомая последовательность
    int maxCount_;
};


SequenceSolver::SequenceSolver(vector<int>& sequence) : maxCount_(0), activeIndex_(NONE)
{
    buildNumbers(sequence);

    for (size_t i = 0; i < sequence.size(); i++)
    {
        auto it = numbers_.find(sequence[i]);
        if (it == numbers_.end())
        {
            terminateCurrentSequence();
        }
        else
        {
            if (activeIndex_ == NONE) // нет активной последовательности
            {
                if (it->second.first == NONE)
                {
                    beginSequence(it->second.first, it->first);
                }
                else
                {
                    beginSequenceCheck(it->second.first, it->second.second);
                }
            }
            else if (activeNew_) // есть новая активная последовательность
            {
                if (it->second.first == NONE)
                {
                    // продолжаем новую активную последовательность
                    it->second.first = activeIndex_;
                    it->second.second = activePosition_;
                    sequences_[activeIndex_].push_back(it->first);
                    activePosition_ += 1;
                }
                else
                {
                    // прерываем новую активную последовательность
                    // и начинаем проверку старой активной последовательности
                    terminateCurrentSequence();
                    beginSequenceCheck(it->second.first, it->second.second);
                }
            }
            else // есть старая активная последовательность
            {
                if (it->second.first == NONE)
                {
                    // прерываем старую активную последовательность
                    // и начинаем новую активную последовательность
                    terminateCurrentSequence();
                    beginSequence(it->second.first, it->first);
                }
                else if (it->second.first == activeIndex_ && it->second.second == activePosition_)
                {
                    // продолжаем проверку старой активной последовательности
                    activePosition_ += 1;
                    if (activePosition_ == sequences_[activeIndex_].size())
                    {
                        activeIndex_ = NONE;
                    }
                }
                else
                {
                    // прерываем старую активную последовательность
                    // и начинаем проверку другой старой активной последовательности
                    terminateCurrentSequence();

                    // обработка случая, когда число находится в этой же последовательности но на более
                    // далёкой позиции, например:  [ 1 2 3 4 5 ] и [ 1 2 5 ]
                    if (numbers_.find(sequence[i]) == numbers_.end())
                    {
                        activeIndex_ = NONE;
                    }
                    else
                    {
                        beginSequenceCheck(it->second.first, it->second.second);
                    }
                }
            }
        }
    }
}

vector<int> SequenceSolver::getSequence()
{
    size_t max = 0;
    for (size_t i = 1; i < sequences_.size(); i++)
    {
        if (sequences_[i].size() > sequences_[max].size())
        {
            max = i;
        }
    }

    return vector<int>(sequences_[max].begin(), sequences_[max].end());
}

void SequenceSolver::buildNumbers(vector<int>& sequence)
{
    map<int, int> counts;
    for (size_t i = 0; i < sequence.size(); i++)
    {
        counts[sequence[i]]++;
    }

    maxCount_ = 0;
    for (auto it = counts.begin(); it != counts.end(); ++it)
    {
        maxCount_ = it->second > maxCount_ ? it->second : maxCount_;
    }

    for (auto it = counts.begin(); it != counts.end(); ++it)
    {
        if (it->second == maxCount_)
        {
            numbers_[it->first] = make_pair(NONE, 0);
        }
    }
}

void SequenceSolver::terminateCurrentSequence()
{
    if (activeIndex_ != NONE && !activeNew_)
    {
        splitSequence(sequences_[activeIndex_], activePosition_);
    }
    activeIndex_ = NONE;
}

size_t SequenceSolver::splitSequence(deque<int>& sequence, size_t position)
{
    deque<int> temp(sequence.begin() + position, sequence.end());
    sequence.erase(sequence.begin() + position, sequence.end());
    size_t index = NONE;
    if (temp.size() > 0)
    {
        index = sequences_.size();
        for (size_t i = 0; i < temp.size(); i++)
        {
            numbers_[temp[i]] = make_pair(index, i);
        }
        sequences_.push_back(temp);
    }
    return index;
}

void SequenceSolver::beginSequence(size_t& index, int number)
{
    index = sequences_.size();
    sequences_.push_back(deque<int>());
    sequences_.back().push_back(number);
    activeIndex_ = index;
    activePosition_ = 1;
    activeNew_ = true;
}

void SequenceSolver::beginSequenceCheck(size_t index, size_t position)
{
    activeIndex_ = splitSequence(sequences_[index], position);
    activePosition_ = 1;
    activeNew_ = false;
    if (activePosition_ == sequences_[activeIndex_].size())
    {
        activeIndex_ = NONE;
    }
}

int main()
{
    int arr[] = { 1, 2, 3, 4, 0, 4, 2, 3, 2, 3 };
    
    SequenceSolver sol(vector<int>(arr, arr + sizeof(arr) / sizeof(int)));
    vector<int> ans = sol.getSequence();

    cout << "N = " << sol.getCount() << endl;
    cout << ans[0];
    for (size_t i = 1; i < ans.size(); i++)
    {
        cout << " " << ans[i];
    }
    cout << endl;
    return 0;
}