▍ Введение
Всем привет!
В данный момент времени я активно готовлюсь к алгоритмическим собеседованиям на позицию стажера в одну из около-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, посмотрим, обсудим.
▍ Итоги
Я мог бы делать подборки каждую неделю с еще более крутыми задачами, но это пока стоит под вопросом и сильно зависит от вашего желания видеть контент подобного рода на данном ресурсе. Для меня это лишний повод разобраться подробнее в материале, а для вас просто задачки, над которыми вы можете подумать на досуге!
Комментарии (21)
anonymous
00.00.0000 00:00
Juggernaut
01.11.2021 19:31+3Если лень самим заморачиваться, то собеседование вполне возможно стоит считать заранее проваленным.
charypopper
01.11.2021 18:02+1Во-второй задаче, вижу другое решение.
описание
К слову слева направо посчитать сколько уникальных символов поиндексно и записать в массив такого же размера:
"aacaba" -> [1,1,2,2,3,3]значение значит сколько уникальных в подстроке p если разбить по индексу i. После нужен такой же массив от обхода с конца:
[1,2,2,3,3,3]Дальше, я запишу один под другим массив со сдвигом, но второй инвертирую для наглядности:
[0,1,1,2,2,3,3] [3,3,3,2,2,1]Решением будет количество одинаковых элементов с одинаковым индексом (len([2,2]).
Второй массив не нужен в памяти, можно запомнить количество повторов и повторяющееся число
petropavel
01.11.2021 18:46Откуда в первой задаче взялось 100% непонятно. Задача — упрощённый вариант «быков и коров», решается так же.
По сути есть два подхода. "наивный" — спрашиваем про первое слово. После получения ответа выбрасываем все слова из списка, что не подходят. Спрашиваем первое из оставшихся. И так далее. Можно не первое, а случайное, один хрен.
И есть оптимальный подход — спрашиваем такое слово, которое позволит выбросит из списка как можно больше вариантов.
Интересный вопрос, на который я не знаю ответа — действительно ли оптимальный подход лучше? Есть ли случаи, когда наивный провалится, а оптимальный нет?
koldyr
01.11.2021 19:11Поскольку любой оптимальный должен выбрасывать уже проверенные слова, то получается - что не провалится.
Гораздо интереснее выглядит построение контпримера к 1 задаче и доказательство того, что его нельзя сделать с вероятностью 1 за 10 шагов.
petropavel
01.11.2021 19:20+4не, это-то как раз тривиально. первое слово 'aaaaaa', второе 'bbbbbb', ну и так далее до 'zzzzzz'. Для любых двух слов счетчик будет 0, хоть обвыбрасывайся весь, только случайно можно наткнуться.
Bitumok
02.11.2021 17:23Этот вариант, как мне кажется не пройдет по условию:
1 <= wordList.length <= 100
Уникальных строк такого вида, как у Вас - всего 26.
Остальные будут содержать различные уникальные комбинации символов.
Dim0v
02.11.2021 22:16+1Так 100 слов и не нужно. 26 уже будет более чем достаточно, чтобы вероятность угадать была сильно меньше 100%.
Вне зависимости от способа выбора слов для угадывания, вероятность угадать за 10 попыток будет равна
faiwer
01.11.2021 21:51+1Я поймал такой случай в одном из тестов на leetcode. 11 попыток, вместо 10. "Оптимальный" вариант сработал — 8 шагов вместо 11.
petropavel
01.11.2021 21:57Ссылку на пример можно? Или, если небольшой, прямо тут?
faiwer
01.11.2021 22:05+1testccoyyo ["wichbx","oahwep","tpulot","eqznzs","vvmplb","eywinm","dqefpt","kmjmxr","ihkovg","trbzyb","xqulhc","bcsbfw","rwzslk","abpjhw","mpubps","viyzbc","kodlta","ckfzjh","phuepp","rokoro","nxcwmo","awvqlr","uooeon","hhfuzz","sajxgr","oxgaix","fnugyu","lkxwru","mhtrvb","xxonmg","tqxlbr","euxtzg","tjwvad","uslult","rtjosi","hsygda","vyuica","mbnagm","uinqur","pikenp","szgupv","qpxmsw","vunxdn","jahhfn","kmbeok","biywow","yvgwho","hwzodo","loffxk","xavzqd","vwzpfe","uairjw","itufkt","kaklud","jjinfa","kqbttl","zocgux","ucwjig","meesxb","uysfyc","kdfvtw","vizxrv","rpbdjh","wynohw","lhqxvx","kaadty","dxxwut","vjtskm","yrdswc","byzjxm","jeomdc","saevda","himevi","ydltnu","wrrpoc","khuopg","ooxarg","vcvfry","thaawc","bssybb","ccoyyo","ajcwbj","arwfnl","nafmtm","xoaumd","vbejda","kaefne","swcrkh","reeyhj","vmcwaf","chxitv","qkwjna","vklpkp","xfnayl","ktgmfn","xrmzzm","fgtuki","zcffuv","srxuus","pydgmq"]Сразу уточню, я не запускал его на коде из статьи. Запускал на своём. Общий принцип тот же самый. Моя failed версия вывела:
outputWORD 1 wichbx 0 WORD 2 oahwep 0 WORD 3 tpulot 0 WORD 4 eqznzs 0 WORD 5 vvmplb 0 WORD 6 kmjmxr 0 WORD 7 ihkovg 0 WORD 8 bcsbfw 1 WORD 9 abpjhw 0 WORD 10 uysfyc 1 WORD 11 ccoyyo 6 FOUND
wataru
04.11.2021 15:23+1И есть оптимальный подход — спрашиваем такое слово, которое позволит выбросит из списка как можно больше вариантов.
Это очень спорный вопрос, а действительно ли жадный метод дает тут оптимальное решение? Если вы сейчас выкините побольше слов, то может вам потом придется сложнее гадать. Когда как сейчас можно выкинуть чуть меньше слов, но зато потом будет легче.
По идее, можно определить функцию Steps(set), которая бы выдвавла, сколько нужно запросов чтобы однозначно отгадать слово из заданного множества. Эта функция должна перебрать каждое слово среди всех секретных, разбить все слова из set на подмножества с равным distance до спрашиваемого (subset_i) и выдать 1 + max(Steps(subset_i)) — ведь мы же смотрим на худший ваниант. Но этот алгоритм работает за O(n*2^n), что для 100 слов это слишком медленно.
И кстати, есть вариант где 100% отгадать нельзя никогда — "aaaaa", "bbbbb", "ccccc", ..., "zzzzz" — тут все расстояния всегда или 0 или 5: вы можете выкидывать только одно слово за запрос.
faiwer
01.11.2021 21:47+1Что, если в начале взять некоторое рандомное слово str1 из списка, сравнить его с секретным, получить некоторое значение matchDistance(количество совпавших элементов), и после этого удалить из списка все те слова, у которых matchDistance со сторокой str1 отличается, так как если у этих слов это значение отличается, они не равны str1, значит не равны и секретному слову.
Я так и сделал. Failed. Благо leetcode даёт данные теста, на котором падает. Прогнал локально… эх, 11 попыток. Ровно на 1 больше лимита. Т.е. всё таки нужна стратегия выбора. Полагаю ваш код просто случайно прошёл тесты. Ну или мой сорвал "джекпот" вероятности.
Сильно всё усложнил. Теперь следующее слово выбирается по принципу: взять такое слово, чтобы в случае если guess вернёт точно такой же ответ, мы отрезали как можно больше слов. Для этого сделал квадратную матрицу пересечений всех со всеми, с которой потом сверялся. Success. Тот тест на котором всё упало теперь справляется за 8 попыток.
P.S. по русскому описанию 1-й задачи в статье ничего не понял. Залез на литкод — всё понятно. Ещё и с примерами.
faiwer
01.11.2021 22:31По второй задаче можно немного проще (для восприятия), и без hashmap:
- Пробегаем по всей строке и заполняем массив, где
arr[i]это количество уникальных символов от края до позицииi(для этого хранимsetзадействованных символов) - Ещё раз тоже самое, но с конца (т.е. один массив для "слева", другой для "справа")
- Пробегаем третий раз и сравниванием позиции
arr[i] == arr[length - i - 2]. Еслиtrue, то+1.
Коду немного больше, но, имхо, он сильно проще для понимания из-за прямолинейности.
codeconst calcUniq = (source: string): number[] => { const usedChars = new Set<string>(); let count = 0; return [...source].map(char => { if (!usedChars.has(char)) { usedChars.add(char); count = count + 1; } return count; }); }; function numSplits(source: string): number { const left = calcUniq(source); const right = calcUniq([...source].reverse().join('')); let count = 0; for (let idx = 0; idx < source.length - 1; ++ idx) { if (left[idx] !== right[source.length - idx - 2]) continue; ++ count; } return count; };petropavel
01.11.2021 23:05+1да и за два прохода можно. вначале считаем символы:
int chars['z'] = {0}, unique_chars = 0; for (i = 0; i < len_s; i++) { unique_chars += chars[s[i]] == 0; chars[s[i]]++; }А на втором проходе находим позиции:
int chars2['z']={0}, unique_chars2 = 0, answer = 0; for (i = 0; unique_chars2 <= unique_chars; i++) { unique_chars2 += chars2[s[i]] == 0; chars2[s[i]]++; chars[s[i]]--; unique_chars -= chars[s[i]] == 0; answer += unique_chars == unique_chars2; }это упрощённо, конечно. можно и массив меньше, и во втором цикле он вообще не нужен, можно bitmap взять. Но принцип будет тот же.
faiwer
01.11.2021 23:51Можно то можно, но единственное преимущество моего решения выше (простота и прямолинейность) полностью исчезло. А асимптотика у всех 3-х решений одна и та же :)
- Пробегаем по всей строке и заполняем массив, где
sdramare
02.11.2021 00:22Первая задача не корректна, так как вот такой кейс подходит под условия и при этом не имеет гарантированного решения
"aaaaaq"
["aaaaab","aaaaac","aaaaad","aaaaae","aaaaaf","aaaaag","aaaaah","aaaaai","aaaaaj","aaaaak","aaaaal","aaaaam","aaaaan","aaaaao","aaaaap","aaaaaq]
agmt
03.11.2021 19:55Видимо, в этом её прелесть для устного собеседования: код написать (со случайными перемешиваниями) — дело нехитрое, а вот пообсуждать тут есть что.
NightShad0w
Сложность кода по McCabe какая-то неадекватная использованному количеству строчек. Следствие олимпиадных и академических задач, сиюминутных требований к реализации и полного отсутствия поддержки и сопровождения, я полагаю.
А использование STL в С++ не является преимуществом или недостатком по сравнению с другими языками? Если решать задачу на С, то требуется реализовать структуры данных самостоятельно. А если использовать реактивное программирование, сложность кода снизится, но сложность времени выполнения может увеличиться.
Как бы ревью кода, с оглядкой на промышленные практики:
Навык алгоритмического мышления задачи проверяют успешно, пригодность кода для включения в проект, длиннее чем продать стартап FAANGу сомнительная, как по мне.
А учитывая, что построение алгоритмов и формальное доказательство — это отдельная область Computer Science, со своими исследованиями и развитием, умение сочинить алгоритм на коленке(или вспомнить готовый подходящий) — это всего лишь фильтр FAANG для отсеивания кандидатов, не имеющий под собой практической необходимости, кроме как пробиться в FAANG. Что само по себе на любителя.