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

    Выкатили вам новую подборку задачек с собеседований. Проверить свои решения задач из предыдущей статьи — можно здесь.



    Тизер: в следующем выпуске попробуем новый формат. Запартнерились для этого с одной компанией — крупнейшим ритейлером, известным своим ИТ-департаментом (догадки принимаются в комментах). Stay tuned, как говорится. Рубрика выходит при поддержке рекрутингового агентства Spice IT.

    Напоминаю, схема нашей статьи такая — мы публикуем 2 вопроса, которые не требуют написания кода, для разминки. Далее мы публикуем 3 задачи, которые подразумевают написание программного кода на одном из удобных для вас языке, если в конкретной задаче не указано иное.
    Также все вопросы и задачи идут в порядке возрастания сложности.
    Итак, приступим.

    Вопросы


    1. Find missing Row in Excel
    We are given an excel sheet which contains integers from 1 to 50, including both. However, the numbers are in a jumbled form and there is 1 integer missing. You have to write a code to identify the missing integer. Only the logic is required.

    Перевод
    Нам дается лист excel, который содержит целые числа от 1 до 50 включительно. Однако, числа находятся в беспорядочной форме, и отсутствует одно целое число. Вам нужно придумать такой алгоритм, который поможет определить недостающее целое число.

    2. Tic Tac Toe Puzzle
    The game of Tic-Tac-Toe is being played between two players and it is in below state after six moves.

    Can you answer following questions?
    • Who will win the game, O or X?
    • Which was the sixth mark and at which position?

    Assume that both the players are intelligent enough.

    Перевод
    Игра в крестики-нолики ведется между двумя игроками, и она находится в таком состоянии (на рисунке) после шести ходов.
    Можете ли вы ответить на следующие вопросы?
    • Кто победит в этой игре, О или Х?
    • Каким был 6-ой ход и в каком квадрате?

    Предположим, что оба игрока достаточно умны.

    Задачи


    1. Find winner of the Game of Nim
    In Game of Nim, two players take turns removing objects from heaps or the pile of stones.
    Suppose two players A and B are playing the game. Each is allowed to take only one stone from the pile. The player who picks the last stone of the pile will win the game. Given N the number of stones in the pile, the task is to find the winner, if player A starts the game.

    Input:
    The input line contains T, denoting the number of test cases. Then T test case follows, a single line of the input containing a positive integer N.

    Output:
    Print the winner i.e. Player A or Player B for each testcase in a separate line.

    Constraints:
    1 <= T <= 100
    1 <= N <= 1000


    Example:
    Input:

    2
    3
    15


    Output:
    Player A
    Player A


    Explanation:
    Testcase 1: Player A remove stone 1 which is at the top, then Player B remove stone 2
    and finally player A removes the last stone.

    Перевод
    В игре Nim два игрока по очереди убирают предметы из кучи или груды камней.
    Предположим, что в эту игру играют два игрока А и В. Каждому из них разрешается взять только один камень из кучи. Игрок, который забирает последний камень из кучи, выиграет игру. Дано N количество камней в куче, задача состоит в том, чтобы найти победителя, если игрок А начнет игру.

    Ввод:
    Входная строка содержит T, обозначающее количество тестов. Далее вводится натуральное число N для каждого теста в отдельной строке.

    Вывод:
    Выведите победителя, то есть игрока А или игрока B, для каждого тестового набора в отдельной строке.

    Ограничения:
    1 < = T < = 100
    1 < = N < = 1000


    Пример:
    Ввод:

    2
    3
    15


    Вывод:
    Игрок А
    Игрок А


    Объяснение:
    Тест 1: игрок А удаляет камень 1, который находится вверху, затем игрок В удаляет камень 2,
    и, наконец, игрок А убирает последний камень — игрок А победил.

    2. Queue Reversal
    Given a Queue Q containing N elements. The task is to reverse the Queue. Your task is to complete the function rev(), that reverses the N elements of the queue.

    Input:
    The first line of input contains an integer T denoting the Test cases. Then T test cases follow. The first line contains N which is the number of elements which will be reversed. Second line contains N space seperated elements.

    Output:
    For each testcase, in a new line, print the reversed queue.

    Your Task:
    This is a function problem. You only need to complete the function rev that takes a queue as parameter and returns the reversed queue. The printing is done automatically by the driver code.

    Constraints:
    1 ≤ T ≤ 100
    1 ≤ N ≤ 105
    1 ≤ elements of Queue ≤ 105


    Example:
    Input :

    2
    6
    4 3 1 10 2 6
    4
    4 3 2 1
    Output :

    6 2 10 1 3 4
    1 2 3 4


    Explanation :
    Testcase 1: After reversing the given elements of the queue, the resultant queue will be 6 2 10 1 3 4.
    Testcase 2: After reversing the given elements of the queue, the resultant queue will be 1 2 3 4.

    Перевод
    Дана очередь Q, содержащая N элементов. Задача состоит в том, чтобы перевернуть очередь. Ваша задача — написать функцию rev(), которая переворачивает N элементов очереди.

    Ввод:
    Первая строка входных данных содержит целое число T, обозначающее тесты. Затем следуют T тестов. Первая строка содержит N — это число элементов, которые будут перевернуты. Вторая строка содержит N разделенных элементов.

    Вывод:
    Для каждого тестового набора в новой строке выведите перевернутую очередь.

    Ваша задача:
    Это функциональная задача. Вам нужно написать функцию rev, которая принимает очередь в качестве параметра и возвращает перевернутую очередь. Печать выполняется автоматически с помощью кода драйвера.

    Ограничения:
    1 ≤ T ≤ 100
    1 ≤ N ≤ 105
    1 ≤ элементы очереди ≤ 105


    Пример:
    Ввод:

    2
    6
    4 3 1 10 2 6
    4
    4 3 2 1

    Вывод:
    6 2 10 1 3 4
    1 2 3 4


    Объяснение:
    Тест 1: после реверсирования заданных элементов очереди результирующая очередь будет равна 6 2 10 1 3 4.
    Тест 2: После реверсирования заданных элементов очереди результирующая очередь будет равна 1 2 3 4.

    3. Operations on PriorityQueue
    Given N integers, your task is to add these elements to the PriorityQueue. Also, given M integers, the task is to check if element is present in PriorityQueue. If present, print 1 and return the max element of priority queue, and then delete the max element. If not present, print -1.

    Input Format:
    First line of testcas contains number of testcases T. For each testcase, there will be 4 lines. First line contains N, number of elements to be inserted into the Priority Queue. Second line contains N positive integers separated by space. Third line contains M, fourth line contains M positive integers.

    Output Format:
    For each testcase, print «1» and max element in newlines if element to be found is present in the PriorityQueue, else print "-1".

    Your Task:
    Your task is to complete the functions insert(), find(), and delete(), such that it adds, find and delete the elements from the queue respectively.

    Constraints:
    1 <= T <= 100
    1 <= N <= 103
    1 <= M <= 103


    Example:
    Input:

    1
    8
    1 2 3 4 5 2 3 1
    5
    1 3 2 9 10


    Output:
    1
    5
    1
    4
    1
    3
    -1
    -1


    Explanation:
    Testcase 1: After inserting given elements, when we find 1, which is present, so we print 1, and then we print the top element of the PriorityQueue which is 5, and delete it. Similarly, when element is not present, just print "-1".

    Перевод
    Даны N целых чисел, ваша задача состоит в том, чтобы добавить эти элементы в PriorityQueue. Кроме того, дано M целых чисел, задача состоит в том, чтобы проверить, присутствует ли элемент в PriorityQueue. Если он присутствует, выведите 1 и верните максимальный элемент приоритетной очереди, а затем удалите максимальный элемент. Если его нет, выведите значение -1.

    Входной формат:
    Первая линия содержит количество тестов Т. Каждый тест имеет 4 строки. Первая строка содержит N — количество элементов, которые будут вставлены в приоритетную очередь. Вторая строка содержит N положительных целых чисел, разделенных пробелом. Третья строка содержит M — количество чисел для проверки присутствия этого числа в PriorityQueue, четвертая строка содержит M положительных целых чисел.

    Выходной формат:
    Для каждого тестового набора выведите «1» и максимальный элемент в отдельной строке, если найденный элемент присутствует в PriorityQueue, в противном случае выведите "-1".

    Ваша задача:
    Ваша задача состоит в том, чтобы написать функции insert(), find() и delete() таким образом, чтобы они добавляли, находили и удаляли элементы из очереди соответственно.

    Ограничения:
    1 < = T < = 100
    1 < = N < = 103
    1 <= M < = 103


    Пример:
    Ввод:

    1
    8
    1 2 3 4 5 2 3 1
    5
    1 3 2 9 10


    Выход:
    1
    5
    1
    4
    1
    3
    -1
    -1


    Объяснение:
    Тест 1: после вставки заданных элементов, PriorityQueue = 1 2 3 4 5 2 3 1. Далее нужно проверить существование заданных элементов 1 3 2 9 10. Элемент «1» существует в PriorityQueue, поэтому мы выводим «1» и максимальный элемент PriorityQueue «5» и удаляем его. Аналогично, когда элемент отсутствует, просто выводим "-1".

    Ответы


    Вопрос 1
    Мы знаем, что сумма всех чисел от 1 до n равна (n*(n+1)/2)
    Поэтому сумма всех чисел от 1 до 50 равна
    50*(50+1)/2 (здесь, n = 50)
    = 50*(51)/2
    = 25*51
    = 1275.

    Поэтому все, что нам нужно сделать, это суммировать все целые числа, присутствующие в файле, и вычесть получившуюся сумму из 1275. Разница между 1275 и этой суммой даст нам недостающее целое число.

    Вопрос 2
    O выиграет эту игру. Шестым ходом был Х в квадрате 9.
    Объяснение:
    7-я метка должна быть помещена в квадрат 5, который является выигрышной ситуацией как для X, так и для O. Следовательно, 6-я метка должна быть помещена в линию, уже содержащую две метки противников. Есть две такие возможности – 6-я отметка была бы либо О в квадрате 7, либо Х в квадрате 9.

    Поскольку мы знаем, что оба игрока достаточно умны, 6-я отметка не может быть О в квадрате 7. Вместо этого он поместил бы О в квадрат 5 и выиграл бы.

    Следовательно, шестая метка должна быть X, помещенная в квадрат 9. И седьмым ходом будет О. Таким образом, О выиграет игру.

    Задача 1
    printf("%s\n",(n % 2) ? "Player A" : "Player B");

    Задача 2
    {
        // add code here.
        stack<long long int> st;
        while(!q.empty())
        {
            int a=q.front();
            st.push(a);
            q.pop();
        }
        while(!st.empty())
        {
            q.push(st.top());
            st.pop();
        }
        return q;
    }
    

    Задача 3
    static void insert(PriorityQueue<integer> q, int k){
    q.add(k);
    }
    
    static boolean find(PriorityQueue<integer> q, int k){
    return q.contains(k);
    }
    
    static int delete(PriorityQueue<integer> q){
    int removed = q.remove();
    return removed;
    }
    Spice IT Recruitment
    ИТ-специализированное кадровое агентство
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 16

      0
      Tic Tac Toe Puzzle

      Так как удалить неправильные рассуждения не могу, то просто поправлю. Видимо крестик оказался в безвыходном положении, и последним поставил свой крестик на 9, потомучто что на 9 что на 5 он проигрывает.
      p.s. такое чувство что с русского на англ транслейтом перевели.
        0

        Задача с крестиками-ноликами довольно странная. Первый ход всегда делается крестиком. Отсюда видно, что крестики победили. Только вот это немного противоречит уточнению про то, что оба игрока умны т.к. крестики-нолики игра по умолчанию ничейная и сводится к победе только ошибкой ноликов. А тут явная ошибка ноликов, что противоречит вышеуказанному уточнению. И в таком случае, игра могла идти как угодно.

          0

          Победит Х т.к. его ход сейчас.
          Прошлый ход — ход 0, который очевидно не 7, т.к. иначе он мог просто выиграть, заняв центр, а значит остаются ходы 2 и 8, оба из которых бездарные, т.к. подарили кресту выигрыш.

            0
            Да нет, как заметил IsUnavailable тут ошибка в условии. если ходил нолик, то почему он не занял центр, чтобы предотвратить победу крестиков? Если ход очевидно не 7, то очевидно пойдя на 5 вместо 2 или 8, 0 сделал бы «вилку» кретику. Я не вижу логичного развития событий которое приведет к данной ситуации.
              0

              Единственная ошибка в условии — это предположение, что оба игрока достаточно умны.

          0
          Я вот понять не могу, в чем интерес этих задач? Они очень простые (ну разве что крестики-нолики интересное). В том что это реальные задачи с собеседований «от ведущих компаний»?
          Например задача «Find winner of the Game of Nim» вообще решается в одну строку: число нечетное — выводим «Player A», иначе «Player B».
          Может стоит добавить какие-нибудь ограничения на решения?
          Я просто предполагаю, что допустим та же «Find missing Row in Excel» на реальном собеседовании:
          — Я придумал алгоритм: «вычеркивание» чисел
          — А теперь решите не используя «массив»
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              Это если вы уточните задачу, добавив условие недопустимости повторов чисел.
              • НЛО прилетело и опубликовало эту надпись здесь
              0
              Статьи нужны для тренировки мозговой деятельности)
              Кому-то задачи могут показаться простыми, кому-то сложными — поэтому задачки имеют три «уровня» сложности.

              А то, что у вас есть несколько вариантов решения — это же хорошо. Всегда есть смысл придумать более эффективный алгоритм решения задачи.
              0
              Вопрос 2:
              Предположим, что оба игрока достаточно умны.

              Если предположить, что оба игрока достаточно умны, то я не могу представить ситуации, при которой поле могло оказаться в такой конфигурации…
                0

                Очевидно, что в начале игры оба игрока были законченными идиотами (что хорошо согласуется с тем, что первыми в нарушение правил ходили нолики), но в процессе игры они резко поумнели, и сейчас они достаточо умны.

                • НЛО прилетело и опубликовало эту надпись здесь
                0
                1. Find missing Row in Excel
                (1..50).reduce(:+)

                Ответ: 1275-SUM(A1:A49)
                сумма чисел минус сумма чисел с пропущенным числом
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Объяснение:
                    7-я метка должна быть помещена в квадрат 5, который является выигрышной ситуацией как для X, так и для O. Следовательно, 6-я метка должна быть помещена в линию, уже содержащую две метки противников. Есть две такие возможности – 6-я отметка была бы либо О в квадрате 7, либо Х в квадрате 9.

                    Поскольку мы знаем, что оба игрока достаточно умны, 6-я отметка не может быть О в квадрате 7. Вместо этого он поместил бы О в квадрат 5 и выиграл бы.

                    Следовательно, шестая метка должна быть X, помещенная в квадрат 9. И седьмым ходом будет О. Таким образом, О выиграет игру.


                    Все так, но если уходить дальше в прошлое, то ни один из вариантов развития не является логичным с точки зрения одного из игроков. Поэтому либо они поумнели на последних шагах, либо, как я и говорил, такая расстановка никак не могла получится, и в любом случае задача не имеет однозначного решения.

                    Соглашусь с решением только если приведете полную партию по шагам (естественно с точки зрения достаточно умных игроков)

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое