Выпуск №17: It-Обучение – Актуальные Вопросы И Задачи От Ведущих Компаний

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

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

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

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

Вопросы

Домино на шахматной доске
Имеется шахматная доска размером 8 на 8, у которой срезаны два диагонально противоположных угла.
Вам дана 31 костяшка домино, причем одна костяшка может покрыть ровно две клетки.
Сможете ли вы использовать 31 домино, чтобы покрыть всю доску?
Перевод На обычной шахматной доске отрезаны два диагонально противоположных поля.
Вам дана 31 домино.
Одна игральная кость покрывает ровно 2 шахматных поля.
Сможете ли вы покрыть этими семенами все поле?
Золото за работу
У вас есть кто-то, кто работает на вас семь дней, и у вас есть золотой слиток, чтобы заплатить ему.
Вы должны платить работнику за его работу в конце каждого дня.
Если вам разрешено сделать только два перерыва в золотом слитке, как вы будете платить своему работнику? (Предполагая, что в течение каждого дня выполняется одинаковый объем работы, следовательно, требуется одинаковая оплата за каждый день)
Перевод Кто-то работает на вас семь дней с оплатой за работу золотым слитком.
Вы должны платить работнику в конце дня каждый день.
Как вы будете платить сотруднику, если вам разрешено разбить слиток только дважды? (Предполагая, что каждый день выполняется один и тот же объем работы и требуется одинаковая оплата)

Задания

Реверс связанного списка
Учитывая указатель на головной узел связанного списка, задача состоит в том, чтобы перевернуть связанный список.
Нам нужно перевернуть список, изменив связи между узлами.
Примеры: Входные данные: глава следующего связанного списка.
1-> 2-> 3-> 4-> НОЛЬ Вывод: Связанный список следует изменить на, 4-> 3-> 2-> 1-> НОЛЬ Входные данные: глава следующего связанного списка.
1-> 2-> 3-> 4-> 5-> НОЛЬ Вывод: Связанный список следует изменить на, 5-> 4-> 3-> 2-> 1-> НОЛЬ Ввод: НОЛЬ Выход: НУЛЬ Ввод: 1-> NULL Вывод: 1-> NULL
Перевод Учитывая указатель на головной узел связанного списка, задача состоит в том, чтобы преобразовать список в обратный.
Вам нужно изменить указатели между узлами.
Примеры: Входные данные: указатель на головной узел и сам список — 1-> 2-> 3-> 4-> NULL. Вывод: 4-> 3-> 2-> 1-> NULL Ввод: 1-> 2-> 3-> 4-> 5-> NULL Вывод: 5-> 4-> 3-> 2-> 1-> NULL Ввод: НОЛЬ Выход: НУЛЬ Ввод: 1-> NULL Вывод: 1-> NULL
Самая длинная битоническая подпоследовательность
Учитывая массив 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 (Самая длинная битоническая подпоследовательность длиной 5 равна 12, 11, 5, 3, 1) Введите arr[] = {80, 60, 30, 40, 20, 10} Выход: 5 (Самая длинная битоническая подпоследовательность длиной 5 равна 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)
Преобразование на месте
Учитывая строку, переместите все четные элементы в конец строки.
При перемещении элементов сохраняйте относительный порядок всех четных и нечетных элементов одинаковым с пространством O(1) и временем O(n).
Другими словами, данная строка с чередующимися элементами (цифрами и буквами), подобная этой, [a1b2c3d4], должна быть преобразована в [abcd1234].

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

Решения

Вопрос 1 Нет, кардан2 ответил Почему.
вопрос 2 Правильный вариант предложили решение

Проблема 1 Правильное решение было предложено в комментариях.

Оригинальная версия:

   

 void ReverseRecursive(struct Node** head_ref)
 {
     struct Node* first;
     struct Node* rest;
      
     /* empty list */
     if (*head_ref == NULL)
        return;   
 
     /* suppose first = {1, 2, 3}, rest = {2, 3} */
     first = *head_ref;  
     rest  = first->next;
 
     /* List has only one node */
     if (rest == NULL)
        return;   
 
     /* reverse the rest list and put the first element at the end */
     recursiveReverse(&rest);
     first->next->next  = first;  
     
     /* tricky step -- see the diagram */
     first->next  = NULL;          
 
     /* fix the head pointer */
     *head_ref = rest;              
 }

Проблема 2 Вариант решения:

using System; class LBS { /* lbs() returns the length of the Longest Bitonic Subsequence in arr[] of size n. The function mainly creates two temporary arrays lis[] and lds[] and returns the maximum lis[i] + lds[i] - 1. lis[i] ==> Longest Increasing subsequence ending with arr[i] lds[i] ==> Longest decreasing subsequence starting with arr[i] */ static int lbs(int[] arr, int n) { int i, j; /* Allocate memory for LIS[] and initialize LIS values as 1 for all indexes */ int[] lis = new int[n]; for (i = 0; i < n; i++) lis[i] = 1; /* Compute LIS values from left to right */ for (i = 1; i < n; i++) for (j = 0; j < i; j++) if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1; /* Allocate memory for lds and initialize LDS values for all indexes */ int[] lds = new int[n]; for (i = 0; i < n; i++) lds[i] = 1; /* Compute LDS values from right to left */ for (i = n - 2; i >= 0; i--) for (j = n - 1; j > i; j--) if (arr[i] > arr[j] && lds[i] < lds[j] + 1) lds[i] = lds[j] + 1; /* Return the maximum value of lis[i] + lds[i] - 1*/ int max = lis[0] + lds[0] - 1; for (i = 1; i < n; i++) if (lis[i] + lds[i] - 1 > max) max = lis[i] + lds[i] - 1; return max; } // Driver code public static void Main() { int[] arr = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 }; int n = arr.Length; Console.WriteLine("Length of LBS is " + lbs(arr, n)); } }
Проблема 3 Вариант решения:

#include <stdio.h> #include <string.h> #include <math.h> // A utility function to swap characters void swap ( char* a, char* b ) { char t = *a; *a = *b; *b = t; } // A utility function to reverse string str[low.high] void reverse ( char* str, int low, int high ) { while ( low < high ) { swap( &str[low], &str[high] ); ++low; --high; } } // Cycle leader algorithm to move all even positioned elements // at the end. void cycleLeader ( char* str, int shift, int len ) { int j; char item; for (int i = 1; i < len; i *= 3 ) { j = i; item = str[j + shift]; do { // odd index if ( j & 1 ) j = len / 2 + j / 2; // even index else j /= 2; // keep the back-up of element at new position swap (&str[j + shift], &item); } while ( j != i ); } } // The main function to transform a string. This function mainly uses // cycleLeader() to transform void moveNumberToSecondHalf( char* str ) { int k, lenFirst; int lenRemaining = strlen( str ); int shift = 0; while ( lenRemaining ) { k = 0; // Step 1: Find the largest prefix subarray of the form 3^k + 1 while ( pow( 3, k ) + 1 <= lenRemaining ) k++; lenFirst = pow( 3, k - 1 ) + 1; lenRemaining -= lenFirst; // Step 2: Apply cycle leader algorithm for the largest subarrau cycleLeader ( str, shift, lenFirst ); // Step 4.1: Reverse the second half of first subarray reverse ( str, shift / 2, shift - 1 ); // Step 4.2: Reverse the first half of second sub-string. reverse ( str, shift, shift + lenFirst / 2 - 1 ); // Step 4.3 Reverse the second half of first sub-string and first // half of second sub-string together reverse ( str, shift / 2, shift + lenFirst / 2 - 1 ); // Increase the length of first subarray shift += lenFirst; } } // Driver program to test above function int main() { char str[] = "a1b2c3d4e5f6g7"; moveNumberToSecondHalf( str ); printf( "%s", str ); return 0; }