Разбор алгоритмических задач с собеседований в Google, Facebook, Amazon

В этой задаче важна сама стратегия, по которой нужно оптимизировать количество вызовов метода guess()у нашего стороннего API.

Следует подумать вот о чем. Вначале представим самых худший тест-кейс, который у нас может быть в соответствии с данными ограничениями. Пусть wordList.length = 100 и загадано какое-то секретное слово Q. Теперь, если случайным образом брать слова из wordList и вызывать метод guess(wordList[i]) нашего API, то вероятность попадания в слово, которое является секретным при 10 попытках равняется примерно 0.1, но если мы при этом будем удалять то слово, которое мы проверили, вероятность попадания немного возрастает, но все еще незначительно.

Давайте подумаем в сторону тразитивности отношений. Что, если в начале взять некоторое рандомное слово str1 из списка, сравнить его с секретным, получить некоторое значение matchDistance(количество совпавших элементов), и после этого удалить из списка все те слова, у которых matchDistance со сторокой str1 отличается, так как если у этих слов это значение отличается, они не равны str1, значит не равны и секретному слову.
В силу своей рандомности, алгоритм недетерминирован, и работает корректно в 99,(9)% случаев.

class Solution {
public:
    
    void findSecretWord(std::vector<std::string>& wordlist, Master& master) {
        srand(10); 
        random_shuffle(wordlist.begin(), wordlist.end()); 
        
        for (uint8_t i = 0; i < 10; ++i) 
            
            if (wordlist.size() != 0) {
                std::string strCompareToMaster = wordlist.back(); 
                wordlist.pop_back(); 
                uint8_t matchDistanceWithSecret = master.guess(strCompareToMaster); 
                std::vector<std::string> tempWordListWithTheSameMatchDistance; 
                
                for (auto& currWord : wordlist) {
                    uint8_t mathDistanceWithCurrWord = 0; 
                    
                    for (uint8_t k = 0; k < strCompareToMaster.size(); ++k) {
                        if (strCompareToMaster[k] == currWord[k]) 
                            mathDistanceWithCurrWord++; 
                    }
                        
                    if (mathDistanceWithCurrWord == matchDistanceWithSecret) 
                        tempWordListWithTheSameMatchDistance.push_back(currWord); 
                }
                wordlist = tempWordListWithTheSameMatchDistance; 
            }
        
    }
};

Заранее прошу прощения за код...
Если вы решили задачу как-то иначе, отправляйте PR ко мне на github.com/Rassska/Leetcode, посмотрим, обсудим.

Суть задачи в том, чтобы аккуратно поработать с префиксами и суффиксами данной строки. Допустим, произошло некоторое разбиение по индексу k. Все, что нам остается сделать, это сравнить количество уникальных элементов на отрезке
[0; k] с количеством уникальных символов на отрезке [k + 1, s.size() - 1]. Давайте заведем структуру данных set для хранения уникальных элементов префикса строки до некоторого индекса, а вот для суффикса заведем хеш-мап, в которой будет содержаться информация по количеству элементов от некоторого индекса k + 1 до s.size() - 1.

В случае, когда суффикс строки совпадает с самой строкой, хеш-мап будет содержать всю предпосчитанную информацию по количеству символов строки. Как только мы рассматриваем следующее k + 1 разбиение мы должны исключить из нашего хеш-мапа тот символ, который уже из суффикса перешел в префикс при разбиении.

class Solution {
public:
    Solution() {
        ios::sync_with_stdio(0);
        cin.tie(0);
    }
    int numSplits(string s) {
        
        std::set<char> leftPref;
        std::unordered_map<char, int> hashMap;
        int ans = 0;
        for (std::size_t i = 0; i < s.size(); i++) {
            hashMap[s[i]]++;
        }
        
        for (std::size_t i = 0; i < s.size(); i++) {
            leftPref.insert(s[i]);
            
            if (hashMap[s[i]] == 1) {
                hashMap.erase(s[i]);
            } else {
                hashMap[s[i]]--;
            }
            
            if (leftPref.size() == hashMap.size()) {
                ans++;
            }
            
        }
        return ans;
        
        
        
    }
private:
    const char maxen = 26;
};

Заранее прошу прощения за код...
Если вы решили задачу как-то иначе, отправляйте PR ко мне на github.com/Rassska/Leetcode, посмотрим, обсудим.