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

Подоспел очередной выпуск 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

Источник