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

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

А использование STL в С++ не является преимуществом или недостатком по сравнению с другими языками? Если решать задачу на С, то требуется реализовать структуры данных самостоятельно. А если использовать реактивное программирование, сложность кода снизится, но сложность времени выполнения может увеличиться.

Как бы ревью кода, с оглядкой на промышленные практики:

• А почему в первом решении счетчики 8-битные, а не size_t, или специального типа, выражающего семантику инкрементирования.
• А почему во втором решении целочисленная переменная имеет тип char, а не более подходящий тип, для выражения целочисленной константы времени компиляции.
• В обоих решениях используется несогласованное именование переменных и аргументов, и однобуквенные именования не выражают семантику сущности.

Навык алгоритмического мышления задачи проверяют успешно, пригодность кода для включения в проект, длиннее чем продать стартап FAANGу сомнительная, как по мне.
А учитывая, что построение алгоритмов и формальное доказательство — это отдельная область Computer Science, со своими исследованиями и развитием, умение сочинить алгоритм на коленке(или вспомнить готовый подходящий) — это всего лишь фильтр FAANG для отсеивания кандидатов, не имеющий под собой практической необходимости, кроме как пробиться в FAANG. Что само по себе на любителя.

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

Я так и сделал. Failed. Благо leetcode даёт данные теста, на котором падает. Прогнал локально… эх, 11 попыток. Ровно на 1 больше лимита. Т.е. всё таки нужна стратегия выбора. Полагаю ваш код просто случайно прошёл тесты. Ну или мой сорвал "джекпот" вероятности.

Сильно всё усложнил. Теперь следующее слово выбирается по принципу: взять такое слово, чтобы в случае если guess вернёт точно такой же ответ, мы отрезали как можно больше слов. Для этого сделал квадратную матрицу пересечений всех со всеми, с которой потом сверялся. Success. Тот тест на котором всё упало теперь справляется за 8 попыток.

P.S. по русскому описанию 1-й задачи в статье ничего не понял. Залез на литкод — всё понятно. Ещё и с примерами.

По второй задаче можно немного проще (для восприятия), и без hashmap:

1. Пробегаем по всей строке и заполняем массив, где arr[i] это количество уникальных символов от края до позиции i (для этого храним set задействованных символов)
2. Ещё раз тоже самое, но с конца (т.е. один массив для "слева", другой для "справа")
3. Пробегаем третий раз и сравниванием позиции 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;
};