Pull to refresh
0
Spice IT Recruitment
ИТ-специализированное кадровое агентство

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

Reading time 5 min
Views 10K
Подоспел очередной выпуск 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
    Можно решить с помощью «умножения в столбик», умножая цифры поразрядно и перенося на следующий разряд. Вариант решения

Tags:
Hubs:
+10
Comments 59
Comments Comments 59

Articles

Information

Website
www.spiceit.ru
Registered
Founded
2009
Employees
31–50 employees
Location
Россия