▍ Введение
Всем привет!
В данный момент времени я активно готовлюсь к алгоритмическим собеседованиям на позицию стажера в одну из около-FAANG компаний. В данной статье пройдемся по двум задачам из списка часто встречаемых задач с leetcode.com.
▍ 1. Guess the Word
Условие задачи:
Имеется некоторое непустое множество уникальных строк и некоторое секретное слово, которое находится в этом множестве, представленное в виде непустой строки. Так же на входе предоставлен некоторый сторонний интерфейс Master, метод которого будет возвращать количество совпавших символов по соответствующим индексам между переданной строкой и секретным словом. Если этого слова нет в списке, метод guess() интерфейса Master вернет -1. Необходимо не больше чем за 10 вызовов метода Master.guess(const std::string& strToCompare) найти секретное слово из списка. Секретное слово считается найденным, если вы смогли вызвать метод guess() от вашего секретного слова.
Говоря формальным языком, необходимо реализовать функцию, которая не более чем за 10 попыток вызовет метод guess() у Master секретным словом в качестве аргумента. То есть, наша задача больше заключается в построении стратегии угадывания секретного слова.
/**
* // This is the Master's API interface.
* // You should not implement it, or speculate about its implementation
* class Master {
* public:
* int guess(string word);
* };
*/
class Solution {
public:
void findSecretWord(std::vector<std::string>& wordlist, Master& master) {
}
};
Ограничения:
wordlist[i].length == 6wordlist[i]из множества ['a', 'b'...'z']все строки в wordList уникальныгарантие на то, что секретное слово находится в wordListколичество обращений к Master.guess() <= 101 <= wordList.length <= 100
Претесты:
Input
: wordList = ["acckzz","ccbazz","eiowzz","abcczz"], secretWord = "acckzz"Output
:В данном случае, при вызове методаMaster.guess(),
передав каждое слово из wordList, мы гарантированно
меньше, чем за 11 попыток, найдем наше секретное слово.Input:
wordList = ["acckzz","ccbazz","eiowzz","abcczz", "abcctt", "abccyy", "abccpz", "abccjz", "abcczn", "abccer", "abcclk"],
secretWord = "abcclk"Output
:В данном тесте уже не получится гарантированно уложиться в
10 вызовов методаMaster.guess(),если действовать так же,
как и для предыдущего теста.
Прежде, чем приступить к разбору, я настоятельно рекомендую вам решить эту задачу самим и прогнать ваш код по заготовленным тестам на leetcode.com.
Разбор
В этой задаче важна сама стратегия, по которой нужно оптимизировать количество вызовов метода 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, посмотрим, обсудим.
▍ 2. Number of Good Ways to Split a String
Условие задачи:
Имеется строка s на входе. Так вот, разделение этой строки на 2 непустые подстроки p и q называется хорошим тогда и только тогда, когда конкатенация этих строк дает строку s и количество различных элементов в подстроке p равно количеству различных в q.
На выходе нужно вернуть количество "хороших" разделений строки s.
Ограничения:
sсодержит элементы из множества ['a', 'b'...'z'].1 <= s.length <= 10^5
Претесты:
Input
: s = "aacaba"
Output: 2.Explanation: Исходную строку можно разбить 5ью разными способами
в соответствии с условиями задачи:
p = "a", q = "acaba" - не является "хорошей"
p = "aa", q = "caba" - не является "хорошей"
p = "aac", q = "aba" - является "хорошей"
p = "aaca", q = "ba" - является "хорошей"
p = "aacab", q = "a" - не является "хорошей"Input
: s = "abcd"Output
: 1.Explanation
: p = "ab", q = "cd" - разбиение является "хорошим"
Разбор:
Суть задачи в том, чтобы аккуратно поработать с префиксами и суффиксами данной строки. Допустим, произошло некоторое разбиение по индексу 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, посмотрим, обсудим.
▍ Итоги
Я мог бы делать подборки каждую неделю с еще более крутыми задачами, но это пока стоит под вопросом и сильно зависит от вашего желания видеть контент подобного рода на данном ресурсе. Для меня это лишний повод разобраться подробнее в материале, а для вас просто задачки, над которыми вы можете подумать на досуге!
