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

Ставшая уже традиционной, новая подборка вопросов и задач от SpiceIT.

КДПВ

Среди отобранных задач — вопросы и алогоритмические задачи, задаваемые соискателям на должность разработчика в Samsung. Предлагаем Вам попробовать решить их самостоятельно и оценить, готовы ли Вы подавать резюме в Samsung 🙂

Вопросы

  1. 100 open/closed doors

    There are 100 doors in a row, all doors are initially closed. A person walks through all doors multiple times and toggle (if open then close, if close then open) them in following way:

    In first walk, the person toggles every door.

    In second walk, the person toggles every second door, i.e., 2nd, 4th, 6th, 8th, …

    In third walk, the person toggles every third door, i.e. 3rd, 6th, 9th, …

    ……….

    In 100th walk, the person toggles 100th door.

    Which doors are open in the end?

    Перевод

    В ряду находятся 100 закрытых дверей. Человек, проходит через двери множество раз, меняя их состояние (если открыта — закрывает, если закрыта — открывает), следующим образом:
    За первый проход посещает каждую дверь.
    За второй проход — каждую вторую дверь (2-ю, 4-ю, 6-ю, …).
    За третий проход — каждую третью дверь.

    За сотый проход — сотую дверь.

    Какие двери в конце будут открытыми?

  2. Light bulbs and switches

    There is a room with a door (closed) and three light bulbs. Outside the room there are three switches, connected to the bulbs. You may manipulate the switches as you wish, but once you open the door you can’t change them. Identify each switch with its bulb.

    Перевод

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

    Подсказка

    (Прим. в задаче используется физика в т.ч.)

Задачи

  1. Power of 2

    Write a program to test if a number is power of 2 or not in one line code.

    Перевод

    Напишите программу-однострочник, которая будет проверять, является ли число степенью двойки.
  2. Find an element in a sorted and rotated array

    An element in a sorted array can be found in O(log n) time via binary search. But suppose we rotate an ascending order sorted array at some pivot unknown to you beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. Devise a way to find an element in the rotated array in O(log n) time.

    Перевод

    В отсортированном массиве элемент можно найти за O(log n) времени, используя двоичный поиск. Предположим, что мы повернули массив в произвольной точке, которая Вам заранее неизвестна. Так, например, 1 2 3 4 5 может стать 3 4 5 1 2. Предложите способ поиска элемента в таком массиве за O(log n) времени.
  3. Find a Number X whose sum with its digits is equal to N

    Given a positive number N. We need to find number(s) such that sum of digits of those numbers to themselves is equal to N. If no such number is possible print -1.
    N <= 1000000000.

    Examples:
    Input: N = 21
    Output: X = 15
    Explanation: X + its digit sum
    = 15 + 1 + 5
    = 21

    Input: N = 5
    Output: -1

    Input: N = 100000001
    Output: X = 99999937
    X = 100000000

    Перевод

    Дано положительное целое число N. Нам необходимо найти такое число (числа), чтобы сумма самого числа и его цифр равнялась N. Если таких чисел нет — вывести -1.

    Примеры:

    Вход: N = 21
    Выход: X = 15
    Объяснение: X + сумма его цифр
    = 15 + 1 + 5
    = 21

    Вход: N = 5
    Выход: -1

    Вход: N = 100000001
    Выход: X = 99999937
    X = 100000000

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

Решения

  1. Вопрос 1

    Открытыми останутся двери: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

    Верный ответ дан в комментарии

  2. Вопрос 2

    Если включить одну лампочку, подождать пару минут, включить вторую и зайти в комнату, то первую лампочку можно будет определить по нагреву — она должна быть тёплой. Ответ был дан в комментарии комментарии.
    Тут также приведён замечательный вариант ответа.

  3. Задача 1

    Верные решения были предложены в комментариях. Исходный вариант на C++:

    #include<stdio.h> #include<stdbool.h> #include<math.h>   /* Function to check if x is power of 2*/ bool isPowerOfTwo(int n) {    return (ceil(log2(n)) == floor(log2(n))); }   // Driver program int main() {     isPowerOfTwo(31)? printf("Yes\n"): printf("No\n");     isPowerOfTwo(64)? printf("Yes\n"): printf("No\n");     return 0; }

  4. Задача 2

    Исходное решение предполагает следующее — найти точку поворота, после чего попробовать найти элемент бинарным поиском сначала в первом подмассиве (до точки поворота), потом — во втором:

     /* Program to search an element in a sorted and pivoted array*/ #include <stdio.h>   int findPivot(int[], int, int); int binarySearch(int[], int, int, int);   /* Searches an element key in a pivoted sorted array arrp[]    of size n */ int pivotedBinarySearch(int arr[], int n, int key) {    int pivot = findPivot(arr, 0, n-1);      // If we didn't find a pivot, then array is not rotated at all    if (pivot == -1)        return binarySearch(arr, 0, n-1, key);      // If we found a pivot, then first compare with pivot and then    // search in two subarrays around pivot    if (arr[pivot] == key)        return pivot;    if (arr[0] <= key)        return binarySearch(arr, 0, pivot-1, key);    return binarySearch(arr, pivot+1, n-1, key); }   /* Function to get pivot. For array 3, 4, 5, 6, 1, 2 it returns    3 (index of 6) */ int findPivot(int arr[], int low, int high) {    // base cases    if (high < low)  return -1;    if (high == low) return low;      int mid = (low + high)/2;   /*low + (high - low)/2;*/    if (mid < high && arr[mid] > arr[mid + 1])        return mid;    if (mid > low && arr[mid] < arr[mid - 1])        return (mid-1);    if (arr[low] >= arr[mid])        return findPivot(arr, low, mid-1);    return findPivot(arr, mid + 1, high); }   /* Standard Binary Search function*/ int binarySearch(int arr[], int low, int high, int key) {    if (high < low)        return -1;    int mid = (low + high)/2;  /*low + (high - low)/2;*/    if (key == arr[mid])        return mid;    if (key > arr[mid])        return binarySearch(arr, (mid + 1), high, key);    return binarySearch(arr, low, (mid -1), key); }   /* Driver program to check above functions */ int main() {    // Let us search 3 in below array    int arr1[] = {5, 6, 7, 8, 9, 10, 1, 2, 3};    int n = sizeof(arr1)/sizeof(arr1[0]);    int key = 3;    printf("Index: %dn", pivotedBinarySearch(arr1, n, key));    return 0; } 

  5. Задача 3

    Фактически, для числа X < = 1000000000, сумма цифр не превысит 100, следовательно мы можем написать следующий код:

     #include <cmath> #include <cstdlib> #include <iostream> #include <vector> using namespace std;   // Computing the sum of digits of x int sumOfDigits(long int x) {     int sum = 0;     while (x > 0) {         sum += x % 10;         x /= 10;     }     return sum; }   // Checks for 100 numbers on both left // and right side of the given number to // find such numbers X such that X +  // sumOfDigits(X) = N and updates the answer // vector accordingly void compute(vector<long int>& answer, long int n) {     // Checking for all possibilities of      // the answer     for (int i = 0; i <= 100; i++) {           // Evaluating the value on the left          // side of the given number         long int valueOnLeft = abs(n – i) +                       sumOfDigits(abs(n – i));           // Evaluating the value on the right         // side of the given number         long int valueOnRight = n + i + sumOfDigits(n + i);           // Checking the condition of equality          // on both sides of the given number N          // and updating the answer vector         if (valueOnLeft == n)             answer.push_back(abs(n – i));         if (valueOnRight == n)             answer.push_back(n + i);     } }   // Driver Function int main() {         long int N = 100000001;       vector<long int> answer;     compute(answer, N);       // If no solution exists, print -1     if (answer.size() == 0)         cout << -1;     else {           // If one or more solutions are possible,         // printing them!         for (auto it = answer.begin(); it != answer.end(); ++it)             cout << "X = " << (*it) << endl;     }     return 0; } 

FavoriteLoadingДобавить в избранное

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *