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

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

Reading time 5 min
Views 6.2K
Подоспел очередной выпуск 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].



Решения


  1. Вопрос 1
    Нет, kardan2 ответил почему.

  2. Вопрос 2
    Было предложено верное решение

  3. Задача 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;              
    }
    


  4. Задача 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));
        }
    }
    


  5. Задача 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;
    }
    


Tags:
Hubs:
+8
Comments 9
Comments Comments 9

Articles

Information

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