Выпуск#21: ITренировка — актуальные вопросы и задачи от ведущих компаний

    Подоспел очередной выпуск ITренировки — задач, предлагаемых на собеседования в ведущие IT-компании.

    КДПВ

    В подборку вошли задачи и вопросы от Facebook, которые задают желающим устроиться на должность разработчика. Традиционно, отобраны как простые задачи, так и не очень. Рекомендуем попробовать решить задачи самостоятельно, ссылку на оригинальные решения мы обычно добавляем в секцию ответов.

    Вопросы


    1. Free place
      People are waiting in line to board a 100-seat airplane. Harry is the first person in the line. Harry gets on the plane but he forgets his seat number, so he picks a seat at random. After that, each person who gets on the plane sits in his assigned seat if it’s available otherwise chooses an open seat at random to sit in. The flight is full and you are last in line. What is the probability that you get to sit in your assigned seat?

      Перевод
      Пассажиры ожидают посадки в 100-местный воздушный лайнер. Гарри — первый в очереди. Когда он проходит в самолет, то обнаруживает, что забыл номер своего места, поэтому он усаживается на случайное место. Пассажиры, зашедшие после него, начинают занимать свои места согласно билетам, но если обнаруживают, что их место занято — то садятся на случайное место. Самолет заполнился и вы заходите последним. Какова вероятность, что вы попадёте на своё место?

    2. Two hourglasses
      Measure 9 minutes from a 4 minutes hourglass and a 7 minutes hourglass.

      Перевод
      Отмерьте 9 минут с помощью двух песочных часов на 4 и на 7 минут.


    Задачи


    1. Word boogle
      Given a dictionary, a method to do lookup in dictionary and a M x N board where every cell has one character. Find all possible words that can be formed by a sequence of adjacent characters. Note that we can move to any of 8 adjacent characters, but a word should not have multiple instances of same cell.

      Example:

      Input: dictionary[] = {«HABR», «FOR», «QUIZ», «GO»};

      boggle[][] = {{'H','I','Z'},
      {'U','A','R'},
      {'Q','N','B'}};

      isWord(str): returns true if str is present in dictionary
      else false.

      Output: Following words of dictionary are present
      HABR
      QUIZ




      Перевод
      Дано: словарь; метод для поиска по словарю и матрица MxN, где каждая ячека содержит один символ. Найдите все возможные слова из словаря, которые могут быть собраны последовательно из соседних символов матрицы. Мы можем двигаться на любую из 8 соседних ячеек, но слово не может включать одну и ту же ячейку дважды.

      Пример:

      Вход: dictionary[] = {«HABR», «FOR», «QUIZ», «GO»};

      boggle[][] = {{'H','I','Z'},
      {'U','A','R'},
      {'Q','N','B'}};

      isWord(str): возвращает true если слово str есть в словаре, иначе — false.

      Выход: Следующие слова наличествуют в словаре:
      HABR
      QUIZ



    2. FBI. Ways to decode
      A top secret message containing letters from A-Z is being encoded to numbers using the following mapping:

      'A' -> 1
      'B' -> 2

      'Z' -> 26

      You are an FBI agent. You have to determine the total number of ways that message can be decoded.
      Note: An empty digit sequence is considered to have one decoding. It may be assumed that the input contains valid digits from 0 to 9 and If there are leading 0’s, extra trailing 0’s and two or more consecutive 0’s then it is an invalid string.

      Example:
      Given encoded message «123», it could be decoded as «ABC» (1 2 3) or «LC» (12 3) or «AW»(1 23).
      So total ways are 3.


      Перевод
      Секретное сообщение, состоящее из букв A-Z закодировано числовой нотацией со следующим соответствием:

      'A' -> 1
      'B' -> 2

      'Z' -> 26

      Вы агент РКН ФБР. Вам необходимо определить количество вариантов расшифровки этого сообщения. Прим.: пустая числовая последовательность считается имеющей один вариант. Предполагается, что входная строка имеет корректную последовательность чисел 0-9. Если есть ведущие 0 или лишние замыкающие 0, а также два и более повторяющихся 0 — такая строка некорректна.

      Пример:
      Зашифрованное сообщение — «123», оно может быть расшифровано как «ABC» (1 2 3) или «LC» (12 3) или «AW»(1 23).
      Ответ: 3.


    3. Multiply strings
      Given two numbers as stings s1 and s2, your task is to multiply them. You are required to complete the function multiplyStrings which takes two strings s1 and s2 as its only argument and returns their product as strings.

      Constraints:
      1<=length of s1 and s2 <=100

      Input: s1 = 4154
      s2 = 51454
      Output: 213779916

      Input: s1 = 654154154151454545415415454
      s2 = 63516561563156316545145146514654
      Output: 41549622603955309777243716069997997007620439937711509062916

      Перевод
      Даны два числа в виде строк s1 и s2, Ваша задача — умножить эти числа. Вам требуется написать функцию multiplyStrings, которая принимает только 2 строковых агрумента (s1 и s2) и возвращает их произведение в качестве результата.

      Ограничения:
      1 <= длина s1 и s2 <= 100

      Пример:
      Вход: s1 = 4154
      s2 = 51454
      Выход: 213779916

      Вход: s1 = 654154154151454545415415454
      s2 = 63516561563156316545145146514654
      Выход: 41549622603955309777243716069997997007620439937711509062916

    Ответы будут даны в течение следующей недели — успейте решить. Удачи!

    Решения


    1. Вопрос 1
      Вероятность 50%. В комментариях это обстоятельно обсуждено, например, в этом.

    2. Вопрос 2
      Правильный ответ в первом же комментарии.

    3. Задача 1
      Исходный вариант решения:
      // C++ program for Boggle game
      #include<iostream>
      #include<cstring>
      using namespace std;
       
      #define M 3
      #define N 3
       
      // Let the given dictionary be following
      string dictionary[] = {"HABR", "FOR", "QUIZ", "GO"};
      int n = sizeof(dictionary)/sizeof(dictionary[0]);
       
      // A given function to check if a given string is present in
      // dictionary. The implementation is naive for simplicity. As
      // per the question dictionary is given to us.
      bool isWord(string &str)
      {
          // Linearly search all words
          for (int i=0; i<n; i++)
              if (str.compare(dictionary[i]) == 0)
                return true;
          return false;
      }
       
      // A recursive function to print all words present on boggle
      void findWordsUtil(char boggle[M][N], bool visited[M][N], int i,
                         int j, string &str)
      {
          // Mark current cell as visited and append current character
          // to str
          visited[i][j] = true;
          str = str + boggle[i][j];
       
          // If str is present in dictionary, then print it
          if (isWord(str))
              cout << str << endl;
       
          // Traverse 8 adjacent cells of boggle[i][j]
          for (int row=i-1; row<=i+1 && row<M; row++)
            for (int col=j-1; col<=j+1 && col<N; col++)
              if (row>=0 && col>=0 && !visited[row][col])
                findWordsUtil(boggle,visited, row, col, str);
       
          // Erase current character from string and mark visited
          // of current cell as false
          str.erase(str.length()-1);
          visited[i][j] = false;
      }
       
      // Prints all words present in dictionary.
      void findWords(char boggle[M][N])
      {
          // Mark all characters as not visited
          bool visited[M][N] = {{false}};
       
          // Initialize current string
          string str = "";
       
          // Consider every character and look for all words
          // starting with this character
          for (int i=0; i<M; i++)
             for (int j=0; j<N; j++)
                   findWordsUtil(boggle, visited, i, j, str);
      }
       
      // Driver program to test above function
      int main()
      {
          char boggle[M][N] = {{'H','I','Z'},
      {'U','A','R'},
      {'Q','N','B'}};
       
          cout << "Following words of dictionary are present\n";
          findWords(boggle);
          return 0;
      }
      


    4. Задача 2
      Предложены варианты решения на js, python и на go.

    5. Задача 3
      Можно решить с помощью «умножения в столбик», умножая цифры поразрядно и перенося на следующий разряд. Вариант решения

    Spice IT Recruitment
    82.38
    ИТ специализированное кадровое агентство
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 59

      +2
      2 задача:
      0 мин. Запускаем вместе 7 минутные и 4 минутные.
      4 мин. 4-минутные кончатся, снова их запускаем
      7 мин. 7 минутные кончатся снова их запускаем
      8 мин. 4 минутные кончаются, переворачиваем 7-минутные и как раз они кончатся через 1 минуту
        0
        Как вариант:
        0 мин. Запускаем 4-минутные и 7-минутные
        4 мин. 4-минутные кончаются, снова их запускаем, заодно переворачиваем 7-минутные, в них осталось 3 мин
        7 мин. 7-минутные кончаются, запускаем их заново, заодно переворачиваем 4-минутные, в которых осталась 1 мин
        8 мин. 4-минутные кончились, в 7-минутных накапало 1 мин. Достаточно их перевернуть и отсчитать эту минуту
        Я знаю, это более сложный вариант, просто захотелось найти альтернативное решение)
        0
        FBI Decode — решение на javascript

        function countVariants(codeString)
        {
          //Нули могут быть только вторым знаком кода, 
          // поэтому разобьем кодовую строку на части с разделителем 0,
          // посчитаем количество вариантов в каждой из них и перемножим
          var parts = codeString.split('0');
         
          var variants = 1;
          for(var i = 0; i < parts.length; i++){
            var part = parts[i];
            
            //Уберем последнюю цифру перед нулем 
            if(i + 1 < parts.length){
              //Если перед нулем ничего нет, или перед нулем цифра больше 2
              // возвращаем нуль вариантов, то есть ошибку
              if(!part.length){
                return 0;
              } else if (+part.substr(-1) > 2) {
                return 0;
              }
              
              part = part.substr(0, part.length - 1);
            }
            
            var partVariants = 1;  
            
            //Считаем количество вариантов в части
            if(part.length){
              partVariants = 0; 
              
              //Смотрим кол-во возможных вариантов в начале строки, 
              //если первые две цифры составляют число меньшее 27, то варианта два
              var startOptions = 1;
              if(part.length > 1 && +part.substr(0, 2) < 27) startOptions = 2;
              
              //Для каждого из вариантов рекурсивно вызываем функцию
              for(var j = 1; j <= startOptions; j++){
                partVariants += countVariants(part.substr(j));
              }
            }
        
            variants = variants * partVariants;  
          }
          
          return variants
        }
        
        document.write(countVariants('1231012'));
          0
          А данный метод за вменяемое время отработает? Можете оценить сложность? У меня вышло что-то в духе O(answer) в худшем случае. При этом на тесте 111....1111 (много раз) ответ будет не менее чем 2^(length). Итого имеем экспоненциальный рост от входных данных. Чёт как-то плохо.

          Правильно решение мне каежтся, должно содержать либо мемоизацию, либо лучше сразу использовать простое ДП и не думать. (кстати можно и не делить на блоки).
            0
            да, это бестолковый вариант, так лучше

            function getVariantsCount(codes)
            {
                //Определим все последовательности цифр в коде,
            
                //способные дать больше 2х вариантов,
                //назовем их "вариативным рядом"
                //вариативный ряд должен содержать в себе идущие подряд
                //цифры 1 или 2 и заканчиваться ненулевой цифрой,
                //которая не может составить двузначное число со следующей
                var variativeRows = [];
            
                //количество вариантов в вариативном ряде
                //возрастает по числам фибоначи с увеличением размера ряда
                var fibonachi = [1, 1, 2];
            
                //колво цифр в текущем вариативном ряде
                var row = 0;
            
                var num;
            
                //перебираем цифры кода
                for(var i = 0; i < codes.length; i++){
                    var prevNum = num;
            
                    //если цифра 1 или 2, то увеличиваем счетчик вариативного ряда
                    //и переходим к следующей цифре
                    if((num = +codes[i]) && num < 3 && ++row) continue;
            
                    if(!num){
                        //если перед 0 нет 1 или 2 возвращаем нуль
                        //так как шифр невалиден
                        if(!row)return 0;
            
                        //в противном случае уменьшаем счетчик, т.к.
                        //цифра перед нулем может относиться только к нулю
                        // и не может участвовать в вариативном ряде
                        else row--;
                    } else if(num < 7 || prevNum == 1) {
                        row++;
                    }
            
                    //увеличиваем ключ с размером ряда на 1
                    variativeRows[row] =
                        isNaN(variativeRows[row]) ? 1 :
                        ++variativeRows[row];
            
                    row = 0;
                }
            
                //увеличиваем ключ с размером последнего ряда на 1
                variativeRows[row] =
                    isNaN(variativeRows[row]) ? 1 :
                    ++variativeRows[row];
            
                var variantsCount = 1;
            
                //для каждого размера ряда определяем количество
                //возможных вариаций и возводим в степень числа рядов данного размера
                //полученные результаты перемножаем
                for(row in variativeRows){
                    for(var j = fibonachi.length - 1; j < row; j++){
                        fibonachi[j + 1] = fibonachi[j] + fibonachi[j - 1];
                    }
            
                    variantsCount *= Math.pow(fibonachi[row], variativeRows[row]);
                }
            
                return variantsCount;
            }
            alert("вариантов: " + getVariantsCount('12612'));
              0
              Решение на питоне динамикой за О(длина строки)
              Заголовок спойлера
              def fbi(s):
                  d = [1] * len(s)
                  if s[1] != '0' and int(s[:2]) <= 26:
                      d[1] = 2
                  for i in range(2, len(s)):
                      if s[i] == '0':
                          d[i] = d[i - 2]
                          continue
                      d[i] = d[i - 1]
                      if s[i - 1] != '0' and int(s[i - 1:i + 1]) <= 26:
                          if int(s[i - 2:i]) <= 26:
                              d[i] += d[i - 2]
                          else:
                              d[i] += d[i - 1]
                  return d[-1]
              
          +1
          Free place

          function freePlaceProbability()
          {
              var percent = 1;
              for(var i = 99; i > 1; i --){
                percent += percent/i;
              }
          
              return percent;
          }
          
          document.write('Probability: ' + freePlaceProbability() + '%');
            0
            Итого 50%
            0
            Free place:
            • вероятность что моё место останется свободным после того как сел Гарри 99/100
            • вероятность что моё место останется свободным после второго (1 — 1/100 (на моё сел Гарри, остальное не важно) — 1/100 (гарри сел на место второго)* 1/99(второй сел на моё
            • и так далее, пока последний передо мной не будет выбирать между двумя местами, то есть 1 — 1/100 — 1/(100*99) -… — 1(100*99*...*2)

            но думаю тут ошибка…
              0
              я бы пошел от обратного. предположим что после первого неправильно севшего пасажира оставшиеся 97 сели на свои места, тогда 99-й пассажир сядет на чужое место с вероятностью 50%. (он выбирал из 2-х кресел), если продолжить рассуждения то допустим 97-й пассажир выбирает из 3-х кресел и сядет на кресло первого пассажира с вероятностью 33,3% и так далее.
                0
                в чём загвоздка чтоб оценить суммарную вероятность что
                99-й пассажир сядет на чужое место с вероятностью 50%
                это 1/2 * вероятность (оставшиеся 97 сели на свои места) что не так просто отыскать
                  +1

                  Ответ: 50%, причем это верно для любого количества пассажиров.
                  Для 2 пассажиров это очевидно.
                  Для N пассажиров:
                  Для начала пусть i пассажир садится в i кресло. (Если это не так, то перенумеруем кресла)
                  Гарри может сесть на следующие кресла:


                    1. (Вероятность 1/N). Последний пассажир садится на свое место.

                  • N. (Вероятность 1/N). Последний пассажир садится НЕ на свое место.
                  • Любое другое (Вероятность (N — 2)/N). Пусть будет K. Тогда все пассажиры от 2 до K сядут на свои места. K пассажир по условию задачи получит роль Гарри и выберет из N-K+1 мест одно случайное. Задача свелась к меньшей. Последний пассажир садится на свое место с вероятностью 50%.
                    Общая вероятность = 1/N + (N-2)/2N = N/2N=1/2.
                    0
                    Немного занудства
                    Ответ: 50%, причем это верно для любого количества пассажиров.

                    А как же случай одного пассажира?

                    А вообще, существует чуть более короткое решение. Ясно, что последний пассажир займет либо свое место, либо место Гарри (ведь если он займет место любого другого пассажира, это бы означало, что тот пассажир не занял его, хотя оно было свободно). Кроме того ясно, что место, которое займет последний пассажир не зависит от того, что написано ни на его билете, ни на билете Гарри. Если взять эти два билета, перемешать и выдать по одному Гарри и последнему пассажиру, то с вероятностью 1/2 последний пассажир займет именно свое место (т.е. то, что отмечено в его билете)
                      0
                      А как же случай одного пассажира?

                      Исключен условиями, (я своё место знаю, а Гарри нет, так что я не Гарри)
                      Моё решение: рассмотрим пассажира, выбиравшего случайное место последним. Он должен был выбрать либо моё место либо место Гарри (иначе он не последний). Выбор из этих двух мест равновероятен, вот и 1/2.
                        0

                        В вашем варианте не учтен случай, когда Гарри садится на свое место.

                          0
                          Учтён. Смотрим случай, когда последний пассажир, выбиравший случайное место — Гарри: он сел либо на своё, либо на моё. Если Гарри сел еще куда-то, то он не последний и выбор просто откладывается.
                      0
                      Простите, вы не могли бы пояснить, как получили общую вероятность?
                        0

                        Общая вероятность равна вероятности того, что Гарри сел на свое место(1/N) или Гарри сел на промежуточное место((N — 2)/N) И последний пассажир сядет на свое место в меньшей задаче (1/2).

                  +1
                  multiply strings

                  function multiplyStrings(s1, s2){
                    
                    var numbers = [];
                    var multipleLength = s1.length + s2.length;
                    
                    for(var i = 0; i < multipleLength; i++) numbers[i] = 0;
                    
                    //Умножаем в столбик, но не по цифре, а сразу большими разрядами,
                    //насколько позволяет система, в js корректно работает при следующих
                    //step-ах, то есть при максимальном произведении двух чисел - 15 знаков после запятой
                    var steps = [10, 5];
                    
                    var digits = [[], []];
                    var stringCopies = [s1, s2]; 
                    
                    //Заполняем массивы для умножения по заданным разрядам
                    for(var ind in digits){
                      var copy = stringCopies[ind];
                      var step = steps[ind];
                      
                       while(copy){
                        if(copy.length <= step){
                          var part = copy;
                          copy = null;
                        } else {
                          var part = copy.substr(-step);
                          copy = copy.substr(0, copy.length - step);
                        }
                        digits[ind].push(+part);
                      }  
                    }
                    
                    //Умножаем в столбик
                    for(var i = 0; i < digits[1].length; i++){
                      for(var j = 0; j < digits[0].length; j++){
                        
                        //Задаем сдвиг в зависимости от текущих разрядов
                        var shift = i * steps[1] + j * steps[0];
                        
                        multipleLine = ('' + (digits[0][j] * digits[1][i])).split('').reverse();
                        
                        //Произведение добавляем в массив numbers
                        for(var k = 0; k < multipleLine.length; k++ ){
                          var ind = k + shift;
                          numbers[ind] += +multipleLine[k];
                        }
                      }
                    }
                    
                    //Подсчитываем каждую позицию в numbers, перенося десятки в следующий разряд
                    for(var i = 0; i < numbers.length - 1; i++){
                      var nextPos = Math.floor(numbers[i] / 10);
                      numbers[i] = numbers[i] % 10;
                      numbers[i + 1] += nextPos;
                    }
                    
                    //Удаляем возможные лишние нули в начале
                    while(numbers[numbers.length - 1] === 0) numbers.pop();
                    
                    return numbers.reverse().join('');
                      
                  }
                  
                  document.write('<br>' + multiplyStrings('654154154151454545415415454', '63516561563156316545145146514654'));
                  0

                  del

                    0

                    Free place:
                    197/9900
                    Вероятность что Гарри сел сразу на свое место: 0.01
                    Вероятность что никто не сядет на мое место и гарри не сел на свое место: 98/100 98/99 97/98… * 1/2
                    В сумме: 98/9900 + 0.01 = 197/9900

                      0
                      Как только отправил, понял что не прав)
                      Ответ 0.5
                      Я искал следующим образом:
                      p_n — вероятность что n-ый пассажир будет выбирать место случайно, при p_1 =1, т.к. гарри всегда все выбирает случайно.
                      p_n = сумма p_j / (101 -j ) по всем j от 1 до n -1
                      Дальше сумму можно выразить через предыдущий член последовательности и найти в явном виде.
                      +1
                      Free place:

                      После того, как Гарри вошёл в самолет, важнейший момент для нас — чьё место будет занято раньше: наше (в первом классе) или его (в багажном отсеке). Как только одно из них будет занято, путаница прекратится, и оставшиеся пассажиры займут свои законные места. Нам же достанется второе

                      Ответ: математически — 50%, но в реальной жизни лучше не вставать в конец очереди, когда летишь с Гарри
                        +1
                        В реальной жизни один пассажир может занимать 2 места.
                        0
                        Free place:
                        1/2
                          0
                          del
                            0
                            1 задача:
                            вероятность что 1 пассажир сядет не на место 100 пассажира 99/100
                            вероятность что 2 пассажир сядет не на место 100 пассажира 99/100 * 98/99
                            ***
                            вероятность что 99 пассажир сядет не на место 100 пассажира 99/100 * 98/99*… * 1/2
                            вероятность того что вы сядете на свое место 1- (99/100 * 98/99*… * 1/2)
                              0
                              Поправка:
                              вероятность того что вы сядете на свое место 99/100 * 98/99*… * 1/2
                              0
                              Free place:
                              Когда Гарри сел не на свое место, получаем цикл с пассажирами, где предыдущий занял место следующего. Этот цикл продолжается, пока последний в цикле не сядет на место Гарри. Например, цикл длины 0 — Гарри сразу на своем месте, цикл длины 100 — Гарри сел на место второго, второй — на место третьего и т.д. Тогда искомая вероятность — отношение числа циклов, не затрагивающих наше место к общему числу таких циклов. Цикл определяется просто набором пассажиров, входящих в него, кроме Гарри, а это все подмножества из 98 пассажиров, то есть 2^98. Аналогично, всего циклов 2^99. Отношение равно 1/2. Либо можно заметить, что к любому циклу без нашего места можно добавить наше место, то есть получим однозначное соответствие варианта где мы садимся на свое место варианту, где наше место будет занято, то есть снова половина вариантов.
                                0
                                2я задача:
                                0: запускаем 7м и 4м
                                4: Запускаем снова 4м
                                7: Кончается 7м С ЭТОГО МОМЕНТА начинаем отсчёт 9 минут.
                                8: переворачиваем 4м
                                12: переворачиваем 4м
                                16: 4м закончился c момента окончания 7м до текущего момента прошло 9м
                                ps: Я понимаю что мой вариант более длинный и запутанный чем у dimoff66, но именно он пришёл в голову.
                                  0
                                    0
                                    Я что-то не совсем понял — передается словарь, скажем Вход: dictionary[] = {«HABR», «FOR», «QUIZ», «GO»};

                                    или

                                    Вход: dictionary[] = {«HIZ», «RND»};

                                    и по нему нужно определиться, есть ли такое слово.
                                      0
                                      На входе матрица boggle (квадрат) и dictionary(набор слов, уже определены). Задача состоит в том чтобы определить есть ли эти слова в матрице или нет.

                                      PS. dictionary[] = {«HABR», «FOR», «QUIZ», «GO»};
                                        0
                                        Моя реализация на Go для Word boggle. Пробовал несколько варианты без рекурсии, но не все тесты проходят или алгоритм становится очень сложный.

                                        func isWord(w string) bool {
                                        
                                        	l := len(boggle)
                                        	c := len(boggle[0])
                                        
                                        	vs = make(map[uint8][]*position)
                                        
                                        	// O(n2)
                                        	for i := 0; i < l ; i++ {
                                        		for j := 0; j < c ; j++ {
                                        			vs[boggle[i][j]] = append(vs[boggle[i][j]], &position{i,j,false})
                                        		}
                                        	}
                                        
                                        	if ps, ok := vs[w[0]]; ok {
                                        		for _, p := range ps {
                                        			p.visited = true
                                        
                                        			if  isNextChar(p,w[1:]) {
                                        				return true
                                        			}
                                        
                                        			p.visited = false
                                        		}
                                        	}
                                        
                                        	return false
                                        }
                                        
                                        
                                        var vs map[uint8][]*position
                                        type position struct {
                                        	i int
                                        	j int
                                        	visited bool
                                        }
                                        
                                        func isNextChar(p *position, w string ) bool {
                                        
                                        	if ps, ok := vs[w[0]]; ok {
                                        		for _, pn := range ps {
                                        
                                        			if !pn.visited &&
                                        				((p.i-1 == pn.i && p.j-1 == pn.j) || (p.i-1 == pn.i && p.j == pn.j) || (p.i-1 == pn.i && p.j+1 == pn.j) ||
                                        				 (p.i == pn.i && p.j-1 == pn.j)   ||                                   (p.i == pn.i && p.j+1 == pn.j)   ||
                                        				 (p.i+1 == pn.i && p.j-1 == pn.j) || (p.i+1 == pn.i && p.j == pn.j) || (p.i+1 == pn.i && p.j+1 == pn.j)    ) {
                                        
                                        				pn.visited = true
                                        
                                        				if len(w) == 1 {
                                        					return true
                                        				}
                                        
                                        				if isNextChar(pn, w[1:]) {
                                        					return true
                                        				} else {
                                        					pn.visited = false
                                        				}
                                        				continue
                                        			}
                                        		}
                                        	}
                                        
                                        	return false
                                        }
                                        


                                        И тесты. Все проходит
                                        import "testing"
                                        
                                        func Test1(t *testing.T)  {
                                        
                                        	boggle = [][]uint8 {
                                        		{'H','I','Z'},
                                        		{'U','A','R'},
                                        		{'Q','N','B'},
                                        	}
                                        
                                        	testDatas := [] struct{
                                        		word string
                                        		isExist bool
                                        	}{
                                        		{ "HHH", false },
                                        		{ "HABR", true },
                                        		{ "HAABR", false },
                                        		{ "FOR", false },
                                        		{ "QUIZ", true },
                                        		{ "QUIZZ", false },
                                        		{ "GO", false },
                                        		{ "HUAIH", false },
                                        		{ "HUAIZ", true },
                                        
                                        	}
                                        
                                        	for _, w := range testDatas {
                                        		result := isWord(w.word)
                                        
                                        		if result != w.isExist {
                                        			t.Errorf("Failed: %s - expected:%v, actual:%v", w.word, w.isExist, result)
                                        		}
                                        	}
                                        }
                                        func Test2(t *testing.T)  {
                                        
                                        	boggle = [][]uint8 {
                                        		{'H','I','Z'},
                                        		{'U','A','A'},
                                        		{'H','N','B'},
                                        	}
                                        
                                        	testDatas := [] struct{
                                        		word string
                                        		isExist bool
                                        	}{
                                        		{ "HUH", true },
                                        		{ "HNB", true },
                                        		{ "HUAI", true },
                                        		{ "HIZAA", true },
                                        		{ "AA", true },
                                        		{ "IAAB", true },
                                        		{ "HUHAA", true },
                                        	}
                                        
                                        	for _, w := range testDatas {
                                        		result := isWord(w.word)
                                        
                                        		if result != w.isExist {
                                        			t.Errorf("Failed: %s - expected:%v, actual:%v", w.word, w.isExist, result)
                                        		}
                                        	}
                                        }
                                        func Test3(t *testing.T)  {
                                        
                                        	boggle = [][]uint8 {
                                        		{'H','A','C'},
                                        		{'A','X','K'},
                                        		{'C','X','E'},
                                        		{'K','E','R'},
                                        	}
                                        
                                        	testDatas := [] struct{
                                        		word string
                                        		isExist bool
                                        	}{
                                        		{ "HACKER", true },
                                        		{ "HACKERXX", true },
                                        		{ "XX", true },
                                        		{ "XXX", false },
                                        		{ "HXER", true },
                                        		{ "HACKERQ", false },
                                        	}
                                        
                                        	for _, w := range testDatas {
                                        		result := isWord(w.word)
                                        
                                        		if result != w.isExist {
                                        			t.Errorf("Failed: %s - expected:%v, actual:%v", w.word, w.isExist, result)
                                        		}
                                        	}
                                        }
                                        
                                          0
                                          Если все проходит, то это хорошо. Но всегда есть возможность для улучшения. Я думаю что для данной задачи будет более эффективно осуществлять поиск с помощью префиксного дерева
                                            0
                                            Как я понял условие задачи, внутрь словаря заглядывать нельзя. Можно пользоваться только ф-цией IsWord (данной нам как внешняя ф-ция). Т.е. можно проверять вхождение в словарь целого слова, но нельзя проверять, какие префиксы есть в словах, чтобы отсекать заведомо тупиковые маршруты.
                                              0
                                              Хмм, да, вчитался лучше… Но тогда нужно проверять слова на всю длину M*N (в данном случае как пример «HIZRAUQNB»), ограничения на длину слова нет.
                                              Во втором случае если есть доступ к словарю, то не зачем функция isWord. Тупик.
                                                0
                                                А может isWord дается как интерфейс функции, которую нужно реализовать?
                                                  0
                                                  Тогда бы это было отдельной, довольно простой, задачей.

                                                  Обычно в задачах «на подумать» не смешивают алгоритмы, чтобы не получилось «найдите кратчайший путь для такси, а заодно посчитайте сумму переплаты по кредиту»
                                                    0
                                                    Ну хорошо, к чему тогда пришли? Какие варианты у Вас трактования задачи? Перебирать слова на всю длину*ширину матрицы boogle то же не вариант. Это ж и так понятно. Вот есть матрица 100 на 100. Не будешь же слово длиной 10000 символов вставлять в isWord.
                                                      0
                                                      Это учебная задача и, видимо, требуется продемонстрировать решение, которое работает с данным API (IsWord), пусть даже неоптимально.
                                                        0
                                                        Учебная задача учит неправильным вещам .)
                                                        А вообще, она может быть просто плохо сформулирована, если у нас возникают вопросы в трактовке.
                                                0
                                                Мне кажется функция isWord дана что бы увести от правильного решения.
                                                *плюсую за префиксные деревья
                                              0
                                              Лучше вынести вот эту часть кода из функции isWord:

                                              l := len(boggle)
                                              c := len(boggle[0])
                                              vs = make(map[uint8][]*position)
                                              // O(n2)
                                              for i := 0; i < l ; i++ {
                                                  for j := 0; j < c ; j++ {
                                                      vs[boggle[i][j]] = append(vs[boggle[i][j]], &position{i,j,false})
                                                  }
                                              }
                                              


                                              Так как isWord запускается у Вас в цикле:

                                              for _, w := range testDatas {
                                                  result := isWord(w.word)
                                              
                                                0
                                                А также потому что isWord не должна быть ответcтвенна за формирование структуры vs.

                                                PS. Не знаю использует ли map префиксное дерево в Go, не работал с ним ранее.
                                                  0
                                                  Я думал это вынести отдельно в init, чтобы избежать повторного создания map.
                                                  Насчет префиксного дерева не знаю, надо копнуть. Скорее всего используется ассоциативный массив.
                                        +1
                                        2-я задача:
                                        1. Запускаем 7 и 4 одновременно, когда закончиться 7, в 4 минутах останется 1 минута.
                                        2. Запускаем оставщуюся 1 минута в 4 и 7 одновременно. После окончания 1 минуты, в 7 останется 6 минут.
                                        3. Запускаем сразу 4 и после окончания 6 минут в 7, в 4 останется 2 минуты
                                        4. Запускаем 7 и потом запускаем оставшиеся 2 минуты из 4 — в сумме получаем 9 минут.
                                          0
                                          Задача 2. FBI
                                          Деревом принятий решений, рекурсивно.
                                          PHP
                                          function fbi($a) {
                                          	if (strlen($a) == 0) {
                                          		return 1;
                                          	}
                                          	$i = fbi(substr($a, 1));
                                          	if ((strlen($a) > 1) and ((int)substr($a, 0, 2) <= 26)) {
                                          		$i = $i + fbi(substr($a, 2));
                                          	}
                                          	return $i;
                                          }

                                            +1
                                            Go
                                            package main
                                            
                                            import (
                                            	"fmt"
                                            	"strconv"
                                            )
                                            
                                            func main() {
                                            	u := fbi("121212")
                                            	fmt.Println(u)
                                            
                                            }
                                            
                                            func fbi(a string) int {
                                            	if len(a) == 0 {
                                            		return 1
                                            	}
                                            	i := fbi(a[1:])
                                            	if len(a) > 1 {
                                            		n, _ := strconv.Atoi(a[:2])
                                            		if n <= 26 {
                                            			i = i + fbi(a[2:])
                                            		}
                                            	}
                                            	return i
                                            }


                                            Запустить
                                            Go Playground
                                            PHP Playground
                                              +1
                                              Плохое решение. Например, вход из 200 единиц не имеет никаких шансов досчитаться за любое разумное время. Хорошее решение работает за линейное время от размера входа.
                                                +1
                                                Да, это дерево. Он должен найти все варианты-листья. Получается вроде O(N^2). Можно оптимизировать, добавить что то вроде динамичности, например так
                                                With simple cache
                                                получится O(N), это даст нам шанс дождаться ;) но не очень по памяти. И это можно оптимизировать, использовать указатели вместо строк – будет лучше, или ещё убрать стейт из стека, развернуть рекурсию в цикл и всё такое… Это оптимизации, но идея дерева так и останется в основе. :)
                                                  0
                                                  Получалось что-то около O(2^N), потому что O(N^2) при N=200 для программы на Go это совсем небольшая нагрузка, он не должен даже заметить.
                                                +1
                                                В решениях ошибка. Не учитываются варианты с ведущим 0.
                                                Исправлено php
                                                function fbi($a) {
                                                	if (strlen($a) == 0) {
                                                		return 1;
                                                	}
                                                	if ($a[0] == 0) {
                                                		return 0;
                                                	}
                                                	$i = fbi(substr($a, 1));
                                                	if ((strlen($a) > 1) and ((int)substr($a, 0, 2) <= 26)) {
                                                		$i = $i + fbi(substr($a, 2));
                                                	}
                                                	return $i;
                                                }
                                                </spoiler>
                                              0
                                              1. Запускаем 7 и 4 одновременно, когда закончиться 7, в 4 минутах останется 1 минута.
                                              2. Запускаем 1 минуту и потом два раза по 4 минуты — получим 9 минут.
                                                0

                                                Умножение строк? Легко!


                                                def multiplyStrings(s1, s2):
                                                    return str(int(s1)*int(s2))

                                                потому что целые числа в питоне — неограниченной разрядности.


                                                А если бы не было питона, пришлось бы реализовывать какой-нибудь алгоритм типа умножения Карацубы или Штрассена (если не жалко времени на программирование) или в столбик (если не жалко процессорного времени).

                                                  0

                                                  ФБР — если бы нам надо было расшифровывать по-честному, мы бы сделали декодер Витерби.
                                                  А раз только посчитать количество, то вырождаем Витерби до тупейшего автомата.


                                                  def fbi(digits):
                                                      valid_numbers = {str(n) for n in range(1, 27)}
                                                  
                                                      num_prev = 0  # сколько вариантов закончилось на предыдущем шаге
                                                                    # (нисколько, т.к. нет такого шага)
                                                      num_here = 1  # сколько вариантов закончилось прямо здесь
                                                                    # (единственный вариант из пустой строки)
                                                      here = '$'    # последняя цифра
                                                                    # (её нет, поэтому сделаем заглушку)
                                                  
                                                      for then in digits:
                                                          num_then = (  # сколько вариантов закончатся на следующем шаге
                                                              num_prev * ((here+then) in valid_numbers)  # предыдущие + 2-разрядное
                                                              +
                                                              num_here * (then in valid_numbers)         # текущие + 1-разрядное
                                                          )
                                                          # сдвигаем состояние
                                                          num_prev, num_here, here = num_here, num_then, then
                                                  
                                                          if not num_prev and not num_here:
                                                              break  # если никаких вариантов не осталось, не будем молотить дальше
                                                  
                                                      # итого, сколько вариантов закончилось здесь, когда проглочены все цифры?
                                                      return num_here
                                                    0
                                                    Не запустился у меня ваш код, выдает вот такую ошибку:

                                                    Traceback (most recent call last):
                                                    File «main.py», line 23, in fbi(121212)
                                                    File «main.py», line 10, in fbi
                                                    for then in digits:
                                                    TypeError: 'int' object is not iterable

                                                    И мне не совсем понятна логика.
                                                      0

                                                      потому что на вход нужно подавать строку с цифрами, а не число.


                                                      print(fbi("121212"))

                                                      А логика очень простая.
                                                      Рассмотрим рекурсивное определение


                                                      Пусть V(s) — предикат, отвечающий, является ли строка шифром одной буквы.
                                                      V("1")...V("9") = 1
                                                      V("10")...V("27") = 1
                                                      все остальные = 0


                                                      fbi("") = 1 — пустому шифру соответствует ровно одна пустая расшифровка
                                                      fbi(d) = V(d) — где d — одиночная цифра (если цифра "0", то ответ 0, иначе 1)
                                                      fbi(s+d1+d2) = fbi(s)V(d1+d2) + fbi(s+d1)V(d1) — количество расшифровок без двух цифр, при условии, что оставшиеся две цифры означают букву, плюс количество расшифровок без одной цифры, при условии, что цифра означает букву.


                                                      Это рекурсивное определение легко превратить в рекуррентное.


                                                      F(1) = fbi(s)
                                                      F(2) = fbi(s+d1)


                                                      F(n) = fbi(s+d1+d2) = F(n-2) V(d1+d2) + F(n-1) V(d1)


                                                      Затравочное состояние
                                                      (Fp,Fh,d1) := (0, 1, "$") — фиктивная цифра "которой просто нет". p=-1, h=0, если перевести на индексы.


                                                      Итерационное, при поступлении очередной цифры d2
                                                      (Fp,Fh,d1) := (Fh,Ft,d2) где Ft вычисляется по формуле выше. h=p+1, t=p+2.

                                                  Only users with full accounts can post comments. Log in, please.