Comments 21
Сложность кода по McCabe какая-то неадекватная использованному количеству строчек. Следствие олимпиадных и академических задач, сиюминутных требований к реализации и полного отсутствия поддержки и сопровождения, я полагаю.
А использование STL в С++ не является преимуществом или недостатком по сравнению с другими языками? Если решать задачу на С, то требуется реализовать структуры данных самостоятельно. А если использовать реактивное программирование, сложность кода снизится, но сложность времени выполнения может увеличиться.
Как бы ревью кода, с оглядкой на промышленные практики:
- А почему в первом решении счетчики 8-битные, а не size_t, или специального типа, выражающего семантику инкрементирования.
- А почему во втором решении целочисленная переменная имеет тип char, а не более подходящий тип, для выражения целочисленной константы времени компиляции.
- В обоих решениях используется несогласованное именование переменных и аргументов, и однобуквенные именования не выражают семантику сущности.
Навык алгоритмического мышления задачи проверяют успешно, пригодность кода для включения в проект, длиннее чем продать стартап FAANGу сомнительная, как по мне.
А учитывая, что построение алгоритмов и формальное доказательство — это отдельная область Computer Science, со своими исследованиями и развитием, умение сочинить алгоритм на коленке(или вспомнить готовый подходящий) — это всего лишь фильтр FAANG для отсеивания кандидатов, не имеющий под собой практической необходимости, кроме как пробиться в FAANG. Что само по себе на любителя.
Во-второй задаче, вижу другое решение.
описание
К слову слева направо посчитать сколько уникальных символов поиндексно и записать в массив такого же размера:
"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]).
Второй массив не нужен в памяти, можно запомнить количество повторов и повторяющееся число
Откуда в первой задаче взялось 100% непонятно. Задача — упрощённый вариант «быков и коров», решается так же.
По сути есть два подхода. "наивный" — спрашиваем про первое слово. После получения ответа выбрасываем все слова из списка, что не подходят. Спрашиваем первое из оставшихся. И так далее. Можно не первое, а случайное, один хрен.
И есть оптимальный подход — спрашиваем такое слово, которое позволит выбросит из списка как можно больше вариантов.
Интересный вопрос, на который я не знаю ответа — действительно ли оптимальный подход лучше? Есть ли случаи, когда наивный провалится, а оптимальный нет?
Поскольку любой оптимальный должен выбрасывать уже проверенные слова, то получается - что не провалится.
Гораздо интереснее выглядит построение контпримера к 1 задаче и доказательство того, что его нельзя сделать с вероятностью 1 за 10 шагов.
не, это-то как раз тривиально. первое слово 'aaaaaa', второе 'bbbbbb', ну и так далее до 'zzzzzz'. Для любых двух слов счетчик будет 0, хоть обвыбрасывайся весь, только случайно можно наткнуться.
Я поймал такой случай в одном из тестов на leetcode. 11 попыток, вместо 10. "Оптимальный" вариант сработал — 8 шагов вместо 11.
Ссылку на пример можно? Или, если небольшой, прямо тут?
ccoyyo
["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 версия вывела:
WORD 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
И есть оптимальный подход — спрашиваем такое слово, которое позволит выбросит из списка как можно больше вариантов.
Это очень спорный вопрос, а действительно ли жадный метод дает тут оптимальное решение? Если вы сейчас выкините побольше слов, то может вам потом придется сложнее гадать. Когда как сейчас можно выкинуть чуть меньше слов, но зато потом будет легче.
По идее, можно определить функцию Steps(set), которая бы выдвавла, сколько нужно запросов чтобы однозначно отгадать слово из заданного множества. Эта функция должна перебрать каждое слово среди всех секретных, разбить все слова из set на подмножества с равным distance до спрашиваемого (subset_i) и выдать 1 + max(Steps(subset_i)) — ведь мы же смотрим на худший ваниант. Но этот алгоритм работает за O(n*2^n), что для 100 слов это слишком медленно.
И кстати, есть вариант где 100% отгадать нельзя никогда — "aaaaa", "bbbbb", "ccccc", ..., "zzzzz" — тут все расстояния всегда или 0 или 5: вы можете выкидывать только одно слово за запрос.
Что, если в начале взять некоторое рандомное слово str1 из списка, сравнить его с секретным, получить некоторое значение matchDistance(количество совпавших элементов), и после этого удалить из списка все те слова, у которых matchDistance со сторокой str1 отличается, так как если у этих слов это значение отличается, они не равны str1, значит не равны и секретному слову.
Я так и сделал. Failed. Благо leetcode даёт данные теста, на котором падает. Прогнал локально… эх, 11 попыток. Ровно на 1 больше лимита. Т.е. всё таки нужна стратегия выбора. Полагаю ваш код просто случайно прошёл тесты. Ну или мой сорвал "джекпот" вероятности.
Сильно всё усложнил. Теперь следующее слово выбирается по принципу: взять такое слово, чтобы в случае если guess вернёт точно такой же ответ, мы отрезали как можно больше слов. Для этого сделал квадратную матрицу пересечений всех со всеми, с которой потом сверялся. Success. Тот тест на котором всё упало теперь справляется за 8 попыток.
P.S. по русскому описанию 1-й задачи в статье ничего не понял. Залез на литкод — всё понятно. Ещё и с примерами.
По второй задаче можно немного проще (для восприятия), и без hashmap:
- Пробегаем по всей строке и заполняем массив, где
arr[i]это количество уникальных символов от края до позицииi(для этого хранимsetзадействованных символов) - Ещё раз тоже самое, но с конца (т.е. один массив для "слева", другой для "справа")
- Пробегаем третий раз и сравниванием позиции
arr[i] == arr[length - i - 2]. Еслиtrue, то+1.
Коду немного больше, но, имхо, он сильно проще для понимания из-за прямолинейности.
const 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;
};да и за два прохода можно. вначале считаем символы:
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 взять. Но принцип будет тот же.
Первая задача не корректна, так как вот такой кейс подходит под условия и при этом не имеет гарантированного решения
"aaaaaq"
["aaaaab","aaaaac","aaaaad","aaaaae","aaaaaf","aaaaag","aaaaah","aaaaai","aaaaaj","aaaaak","aaaaal","aaaaam","aaaaan","aaaaao","aaaaap","aaaaaq]
Разбор алгоритмических задач с собеседований в Google, Facebook, Amazon