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

в 10:44, , рубрики: ITренировка, microsoft, SpiceIT, Блог компании Spice IT Recruitment, занимательные задачи, Занимательные задачки, никто не читает теги, Программирование

Подоспел очередной выпуск ITренировки, и сегодня в номере — задачи от интервьюеров Microsoft.

КДПВ

В подборку вошли задачи с собеседований Microsoft. Сложность, традиционно, варьируется от простых до таких, над которыми нужно немного поразмыслить. Мы предпочитаем делать это в спокойной обстановке, нежели в цейтноте на собеседовании, и желаем, чтобы Ваши собеседования проходили так же спокойно, расслабленно и конструктивно :)

Вопросы

  1. Dominos on the chessboard

    There is an 8 by 8 chessboard in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?

    Перевод

    У обычной шахматной доски отрезаны две противоположных по диагонали клетки. Вам дана 31 косточка домино. Одна кость покрывает ровно 2 шахматных клетки. Сможете ли Вы покрыть все поле этими косточками?

  2. Gold for work

    You’ve got someone working for you for seven days and a gold bar to pay them. You must pay the worker for their work at the end of every day. If you are only allowed to make two breaks in the gold bar, how do you pay your worker? (Assuming equal amount of work is done during each day thus requiring equal amount of pay for each day)

    Перевод

    На Вас работает некто в течение семи дней с оплатой за работу в слиток золота. Вы должны расплачиваться с работником ежедневно в конце дня. Как вы будете рассчитываться с работником, если Вам разрешено разломить слиток лишь дважды? (Предполагается, что ежедневно выполняется одинаковый объём работы, требующий одинаковой оплаты)

Задачи

  1. Reverse a linked list

    Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing links between nodes.

    Examples:

    Input: Head of following linked list
    1->2->3->4->NULL
    Output: Linked list should be changed to,
    4->3->2->1->NULL

    Input: Head of following linked list
    1->2->3->4->5->NULL
    Output: Linked list should be changed to,
    5->4->3->2->1->NULL

    Input: NULL
    Output: NULL

    Input: 1->NULL
    Output: 1->NULL

    Перевод

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

    Примеры:
    Вход: Указатель на головную ноду, и сам список — 1->2->3->4->NULL
    Выход: 4->3->2->1->NULL

    Вход: 1->2->3->4->5->NULL
    Выход: 5->4->3->2->1->NULL

    Вход: NULL
    Выход: NULL

    Вход: 1->NULL
    Выход: 1->NULL

  2. Longest Bitonic Subsequence

    Given an array arr[0 … n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.
    A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.

    Examples:

    Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
    Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

    Input arr[] = {12, 11, 40, 5, 3, 1}
    Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

    Input arr[] = {80, 60, 30, 40, 20, 10}
    Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

    Перевод

    Дам массив arr[0… n-1] содержащий в себе n положительных целых чисел. Назовём подпоследовательность arr[] «Битонной», если элементы в ней сначала увеличиваются, затем уменьшаются. Напишите функцию, принимающую в качестве аргумента массив и возвращающую длину самой длинной битонной подпоследовательности.
    Последовательность, отсортированная по возрастанию, считается битонной с отсутствующей убывающей частью.
    Аналогично, последовательность, отсортированная по убыванию, считается битонной, с отсутствующей возрастающей частью.

    Пример:

    Вход: arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
    Выход: 6 (Длина наибольшей битонной подпоследовательности — 6 { 1, 2, 10, 4, 2, 1})

    Вход: arr[] = {12, 11, 40, 5, 3, 1}
    Выход: 5 (12, 11, 5, 3, 1)

    Вход: arr[] = {80, 60, 30, 40, 20, 10}
    Выход: 5 (80, 60, 30, 20, 10)

  3. Inplace transformation

    Given a string, move all even positioned elements to end of string. While moving elements, keep the relative order of all even positioned and odd positioned elements same with O(1) space and O(n) time.
    In other words given a string with alternating elements (numbers and letters) like this [a1b2c3d4] should be converted to [abcd1234].

    Перевод

    Дана строка, необходимо сместить все элементы, находящиеся на чётной позиции в конец строки. При перемещении элементов необходимо сохранять относительный порядок элементов, чётных и нечётных. Ограничения — O(1) памяти и O(n) времени выполнения.
    Другими словами, строка с чередующимися элементами (цифрами и буквами), например [a1b2c3d4] должна быть преобразована в [abcd1234].

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

Автор: reci

Источник

Поделиться

* - обязательные к заполнению поля