reci 29 мая 2018 в 09:26

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

8 мин

4.3K

Блог компании Spice IT RecruitmentЗанимательные задачкиПрограммирование*

Мы подготовили для Вас новый, 23-й, выпуск ITренировки.

КДПВ

В подборку вошли вопросы, задаваемые претендентам на должность инженера-разработчика на собеседованиях в Intel. География вопросов (как выяснили в прошлом выпуске, это может накладывать отпечаток на содержание вопросов) — расширена (Корея, США). Вопросы традиционно различного уровня сложности — как простые, так и не очень

Вопросы

Water in bathroom

I renovated my bathroom and got myself a new bath tub along with new accessories. I have two taps now — hot one and cold one. The hot tap fills the bath tub faster i.e. in fifteen minutes while it takes eighteen minutes for the cold tap to fill the bath tub.

The drain hole can drain the entirely filled bathtub in ten minutes when the taps are not running.

If I leave both the taps on with the drain plug left out, how long will it take the bath to fill?

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

Если открыть слив — ванна опустеет через 10 минут при закрытых кранах.

Если я оставлю оба крана открытыми, и не заткну слив — сколько потребуется времени для наполнения ванны?
Mark and the traffic

Mark went to visit his mother last weekend which is about 250 miles away from his home. He started 7am in the sunny morning of Saturday and found out that the road was too crowded. There were times that he has completely stationary. He reached his mother's house after lunch.

He had to return on Sunday and he had to travel through the same route again. He left the place at 7 am and found no traffic at all and reached home before lunch time enjoying a smooth drive.

What is the probability that he was at the same point at the same time on both the days he traveled?

Перевод
Марк на выходные поехал навестить свою мать, которая живет за 250 миль от его дома. Он выехал в 7 утра и обнаружил, что дороги переполнены. Временами он даже стоял и прибыл к матери после ланча (прим. в 13:00).
Марку нужно было вернуться в воскресенье тем же маршрутом. Он выехал в 7 утра, отметив попутно, что на дороге нет машин, и приехал домой перед ланчем (прим. в 12:00), наслаждаясь неспешной ездой.

Какова вероятность, что Марк мог оказаться в одной и той же точке в одинаковое время на пути туда и обратно?

Задачи

Print numbers with mobile pad
Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
```
   [ 1 ] [ 2 ] [ 3 ]
   [ 4 ] [ 5 ] [ 6 ]
   [ 7 ] [ 8 ] [ 9 ]
   [ * ] [ 0 ] [ # ]
```
Given a number N, write a program to find out the number of possible numbers of given length.

Examples:
For N=1, number of possible numbers would be 10 (0, 1, 2, 3, …., 9)
For N=2, number of possible numbers would be 36
Possible numbers: 00,08 11,12,14 22,21,23,25 and so on.
Перевод
Имеется мобильная клавиатура, на которой разрешено нажимать кнопки сверху, снизу и по бокам от заданной кнопки (Прим. на заданную кнопку тоже можно нажимать, что следует из примеров). Нижние * и # трогать не следует.
```
   [ 1 ] [ 2 ] [ 3 ]
   [ 4 ] [ 5 ] [ 6 ]
   [ 7 ] [ 8 ] [ 9 ]
   [ * ] [ 0 ] [ # ]
```
Дано число N, напишите программу, вычисляющую количество допустимых чисел заданной длины.

Примеры:
Для N=1, количество чисел — 10 (0, 1, 2, 3, …., 9)
Для N=2, количество чисел — 36 (00,08 11,12,14 22,21,23,25 и т.д.)
Clone binary tree

Given a Binary Tree where every node has following structure.
struct node { int key; struct node *left,*right,*random; }
The random pointer points to any random node of the binary tree and can even point to NULL. Create a program to clone the given binary tree.

Перевод
Дано — бинарное дерево с узлами следующей структуры:
struct node { int key; struct node *left,*right,*random; }

Указатели *random ссылаются на случайный узел дерева, могут содержать NULL. Создайте программу для клонирования этого бинарного дерева.
Book readers

A person is determined to finish the book in ‘k’ days but he never wants to stop a chapter in between. Find the optimal assignment of chapters, such that the person doesn’t read too many extra/less pages overall.

Example 1:
Input: Number of Days to Finish book = 2
Number of pages in chapters = {10, 5, 5}
Output: Day 1: Chapter 1
Day 2: Chapters 2 and 3

Example 2:
Input: Number of Days to Finish book = 3
Number of pages in chapters = {8, 5, 6, 12}
Output: Day 1: Chapter 1
Day 2: Chapters 2 and 3
Day 3: Chapter 4

Перевод
Известно, что человек прочитывает книгу за k дней, при этом не желает останавливаться на середине главы. Найдите оптимальное распределение глав (по дням), чтобы читателю не пришлось перенапрягаться (читать слишком много/мало страниц в день).

Пример 1:
Вход: Дней для прочтения книги = 2
Количество страниц в главах = {10, 5, 5}
Выход: День 1: Глава 1
День 2: Глава 2, Глава 3

Пример 2:
Вход: Дней для прочтения книги = 3
Количество страниц в главах = {8, 5, 6, 12}
Выход: День 1: Глава 1
День 2: Глава 2, Глава 3
День 3: Глава 4

Решения

Вопрос 1
jmdorian верно рассчитал ответ — 45 минут.
Вопрос 2
100 %. В этом комментарии ответили почему.

Задача 1

Исходный вариант решения:

#include <stdio.h>
 
// Return count of all possible numbers of length n
// in a given numeric keyboard
int getCount(char keypad[][3], int n)
{
    if(keypad == NULL || n <= 0)
        return 0;
    if(n == 1)
        return 10;
 
    // left, up, right, down move from current location
    int row[] = {0, 0, -1, 0, 1};
    int col[] = {0, -1, 0, 1, 0};
 
    // taking n+1 for simplicity - count[i][j] will store
    // number count starting with digit i and length j
    int count[10][n+1];
    int i=0, j=0, k=0, move=0, ro=0, co=0, num = 0;
    int nextNum=0, totalCount = 0;
 
    // count numbers starting with digit i and of lengths 0 and 1
    for (i=0; i<=9; i++)
    {
        count[i][0] = 0;
        count[i][1] = 1;
    }
 
    // Bottom up - Get number count of length 2, 3, 4, ... , n
    for (k=2; k<=n; k++)
    {
        for (i=0; i<4; i++)  // Loop on keypad row
        {
            for (j=0; j<3; j++)   // Loop on keypad column
            {
                // Process for 0 to 9 digits
                if (keypad[i][j] != '*' && keypad[i][j] != '#')
                {
                    // Here we are counting the numbers starting with
                    // digit keypad[i][j] and of length k keypad[i][j]
                    // will become 1st digit, and we need to look for
                    // (k-1) more digits
                    num = keypad[i][j] - '0';
                    count[num][k] = 0;
 
                    // move left, up, right, down from current location
                    // and if new location is valid, then get number
                    // count of length (k-1) from that new digit and
                    // add in count we found so far
                    for (move=0; move<5; move++)
                    {
                        ro = i + row[move];
                        co = j + col[move];
                        if (ro >= 0 && ro <= 3 && co >=0 && co <= 2 &&
                           keypad[ro][co] != '*' && keypad[ro][co] != '#')
                        {
                            nextNum = keypad[ro][co] - '0';
                            count[num][k] += count[nextNum][k-1];
                        }
                    }
                }
            }
        }
    }
 
    // Get count of all possible numbers of length "n" starting
    // with digit 0, 1, 2, ..., 9
    totalCount = 0;
    for (i=0; i<=9; i++)
        totalCount += count[i][n];
    return totalCount;
}
 
// Driver program to test above function
int main(int argc, char *argv[])
{
   char keypad[4][3] = {{'1','2','3'},
                        {'4','5','6'},
                        {'7','8','9'},
                        {'*','0','#'}};
   printf("Count for numbers of length %d: %dn", 1, getCount(keypad, 1));
   printf("Count for numbers of length %d: %dn", 2, getCount(keypad, 2));
   printf("Count for numbers of length %d: %dn", 3, getCount(keypad, 3));
   printf("Count for numbers of length %d: %dn", 4, getCount(keypad, 4));
   printf("Count for numbers of length %d: %dn", 5, getCount(keypad, 5));
 
   return 0;
}

Задача 2

Вариант решения с хешированием:

// A hashmap based C++ program to clone a binary tree with random pointers
#include<iostream>
#include<map>
using namespace std;
 
/* A binary tree node has data, pointer to left child, a pointer to right
   child and a pointer to random node*/
struct Node
{
    int key;
    struct Node* left, *right, *random;
};
 
/* Helper function that allocates a new Node with the
   given data and NULL left, right and random pointers. */
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->random = temp->right = temp->left = NULL;
    return (temp);
}
 
/* Given a binary tree, print its Nodes in inorder*/
void printInorder(Node* node)
{
    if (node == NULL)
        return;
 
    /* First recur on left sutree */
    printInorder(node->left);
 
    /* then print data of Node and its random */
    cout << "[" << node->key << " ";
    if (node->random == NULL)
        cout << "NULL], ";
    else
        cout << node->random->key << "], ";
 
    /* now recur on right subtree */
    printInorder(node->right);
}
 
// This function creates clone by copying key and left and right pointers
// This function also stores mapping from given tree node to clone.
Node* copyLeftRightNode(Node* treeNode, map<Node *, Node *> *mymap)
{
    if (treeNode == NULL)
        return NULL;
    Node* cloneNode = newNode(treeNode->key);
    (*mymap)[treeNode] = cloneNode;
    cloneNode->left  = copyLeftRightNode(treeNode->left, mymap);
    cloneNode->right = copyLeftRightNode(treeNode->right, mymap);
    return cloneNode;
}
 
// This function copies random node by using the hashmap built by
// copyLeftRightNode()
void copyRandom(Node* treeNode,  Node* cloneNode, map<Node *, Node *> *mymap)
{
    if (cloneNode == NULL)
        return;
    cloneNode->random =  (*mymap)[treeNode->random];
    copyRandom(treeNode->left, cloneNode->left, mymap);
    copyRandom(treeNode->right, cloneNode->right, mymap);
}
 
// This function makes the clone of given tree. It mainly uses
// copyLeftRightNode() and copyRandom()
Node* cloneTree(Node* tree)
{
    if (tree == NULL)
        return NULL;
    map<Node *, Node *> *mymap = new  map<Node *, Node *>;
    Node* newTree = copyLeftRightNode(tree, mymap);
    copyRandom(tree, newTree, mymap);
    return newTree;
}
 
/* Driver program to test above functions*/
int main()
{
    //Test No 1
    Node *tree = newNode(1);
    tree->left = newNode(2);
    tree->right = newNode(3);
    tree->left->left = newNode(4);
    tree->left->right = newNode(5);
    tree->random = tree->left->right;
    tree->left->left->random = tree;
    tree->left->right->random = tree->right;
 
    //  Test No 2
    //    tree = NULL;
 
    //  Test No 3
    //    tree = newNode(1);
 
    //  Test No 4
    /*    tree = newNode(1);
        tree->left = newNode(2);
        tree->right = newNode(3);
        tree->random = tree->right;
        tree->left->random = tree;
    */
 
    cout << "Inorder traversal of original binary tree is: \n";
    printInorder(tree);
 
    Node *clone = cloneTree(tree);
 
    cout << "\n\nInorder traversal of cloned binary tree is: \n";
    printInorder(clone);
 
    return 0;
}

Задача 3

Вариант решения с направленным ацикличным графом:


// C++ DFS solution to schedule chapters for reading in
// given days
# include <iostream>
# include <cstdlib>
# include <climits>
# include <cmath>
using namespace std;
 
// Define total chapters in the book
// Number of days user can spend on reading
# define CHAPTERS 4
# define DAYS 3
# define NOLINK -1
 
// Array to store the final balanced schedule
int optimal_path[DAYS+1];
 
// Graph - Node chapter+1 is the sink described in the
//         above graph
int DAG[CHAPTERS+1][CHAPTERS+1];
 
// Updates the optimal assignment with current assignment
void updateAssignment(int* path, int path_len);
 
// A DFS based recursive function to store the optimal path
// in path[] of size path_len.  The variable sum stores sum of
// of all edges on current path.  k is number of days spent so
// far.
void assignChapters(int u, int* path, int path_len, int sum, int k)
{
    static int min = INT_MAX;
 
    // Ignore the assignment which requires more than required days
    if (k < 0)
        return;
 
    // Current assignment of chapters to days
    path[path_len] = u;
    path_len++;
 
    // Update the optimal assignment if necessary
    if (k == 0 && u == CHAPTERS)
    {
        if (sum < min)
        {
            updateAssignment(path, path_len);
            min = sum;
        }
    }
 
    // DFS - Depth First Search for sink
    for (int v = u+1; v <= CHAPTERS; v++)
    {
        sum += DAG[u][v];
        assignChapters(v, path, path_len, sum, k-1);
        sum -= DAG[u][v];
    }
}
 
// This function finds and prints optimal read list.  It first creates a
// graph, then calls assignChapters().
void minAssignment(int pages[])
{
    // 1) ............CONSTRUCT GRAPH.................
    // Partial sum array construction S[i] = total pages
    // till ith chapter
    int avg_pages = 0, sum = 0, S[CHAPTERS+1], path[DAYS+1];
    S[0] = 0;
 
    for (int i = 0; i < CHAPTERS; i++)
    {
        sum += pages[i];
        S[i+1] = sum;
    }
 
    // Average pages to be read in a day
    avg_pages = round(sum/DAYS);
 
    /* DAG construction vertices being chapter name &
     * Edge weight being |avg_pages - pages in a chapter|
     * Adjacency matrix representation  */
    for (int i = 0; i <= CHAPTERS; i++)
    {
        for (int j = 0; j <= CHAPTERS; j++)
        {
            if (j <= i)
                DAG[i][j] = NOLINK;
            else
            {
                sum = abs(avg_pages - (S[j] - S[i]));
                DAG[i][j] = sum;
            }
        }
    }
 
    // 2) ............FIND OPTIMAL PATH................
    assignChapters(0, path, 0, 0, DAYS);
 
    // 3) ..PRINT OPTIMAL READ LIST USING OPTIMAL PATH....
    cout << "Optimal Chapter Assignment :" << endl;
    int ch;
    for (int i = 0; i < DAYS; i++)
    {
        ch = optimal_path[i];
        cout << "Day" << i+1 << ": " << ch << " ";
        ch++;
        while ( (i < DAYS-1 && ch < optimal_path[i+1]) ||
                (i == DAYS-1 && ch <= CHAPTERS))
        {
           cout <<  ch << " ";
           ch++;
        }
        cout << endl;
    }
}
 
// This funtion updates optimal_path[]
void updateAssignment(int* path, int path_len)
{
    for (int i = 0; i < path_len; i++)
        optimal_path[i] = path[i] + 1;
}
 
// Driver program to test the schedule
int main(void)
{
    int pages[CHAPTERS] = {7, 5, 6, 12};
 
    // Get read list for given days
    minAssignment(pages);
 
    return 0;
}

Теги:

Хабы:

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

Вопросы

Задачи

Решения

Публикации

Информация

Истории