Issue # 10: IT training - current issues and challenges from leading companies

Questions

1. 100 open / closed doors
   

   There are 100 doors in a row, all doors are closed. If you’re close, you’ll be able to go through the doors.
   ')
   In the first walk, the person toggles every door.
   
   In the second walk, the person toggles every second door, ie, the 2nd, 4th, 6th, 8th, ...
   
   In the third walk, the person toggles every third door, ie 3rd, 6th, 9th, ...
   
   ... ... ...
   
   In 100th walk, the person toggles 100th door.
   
   Which doors are open in the end?
   

   Transfer

   There are 100 closed doors in the row. A person passes through the door many times, changing their state (if open - closes, if closed - opens), as follows:
   During the first passage visits each door.
   For the second passage - every second door (2nd, 4th, 6th, ...).
   For the third passage - every third door.
   ...
   For the hundredth passage - the hundredth door.
   
   What doors at the end will be open?
   
2. Light bulbs and switches
   

   There are three light bulbs. Outside the room there are three switches, connected to the bulbs. You can change them. Identify each switch with its bulb.

   Transfer

   There are three lamps in the room, the door to the room is closed. In front of the room are three switches connected to the lamps. You can put the switches in any position, but after you open the door - the position of the switches cannot be changed. Match each switch to the lamp.
   
   
   
   hint

   (Note. In the problem, physics is used, including)
   

Tasks

1. Power of 2
   

   Write a program to test if it’s not a one line code.
   

   Transfer

   Write a one-liner program that will check if the number is a power of two.
   
2. Find an element in a sorted and rotated array
   

   Found in O (log n) time through binary search. But suppose we rotate an ascending order sorted array at some pivot beforehand. So for instance, 1 2 3 4 5 might become 3 4 5 1 2. In the (log n) time.

   Transfer

   In a sorted array, the element can be found in O (log n) time using a binary search. Suppose we rotate an array at an arbitrary point that you do not know in advance. For example, 1 2 3 4 5 can become 3 4 5 1 2. Suggest a way to search for an element in such an array in O (log n) time.
   
3. Find your number with your digits is equal to N
   

   The number of possible numbers is a print of -1.
   N <= 1,000,000,000.
   
   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 = 1,000,000,000
   

   Transfer

   Given a positive integer N. We need to find a number (s) such that the sum of the number itself and its digits is N. If there are no such numbers, output -1.
   
   Examples:
   
   Input: N = 21
   Output: X = 15
   Explanation: X + the sum of its digits
   = 15 + 1 + 5
   = 21
   
   Input: N = 5
   Output: -1
   
   Login: N = 100000001
   Output: X = 99999937
   X = 1,000,000,000
   

Solutions

1. Question 1

   The doors will remain open: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.
   
   The correct answer is given in the comments.
   
   
   
2. Question 2

   If you turn on one light bulb, wait a couple of minutes, turn on the second one and go into the room, then the first light bulb can be determined by heating - it should be warm. The answer was given in the comments comment .
   There is also a great answer.
   
   
   
3. Task 1

   The right solutions were suggested in the comments. Initial version in 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. Task 2

   The initial solution assumes the following - to find the turning point, after which try to find the element by binary search first in the first subarray (to the turning point), then in the second:
   
   

    /* 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. Task 3

   In fact, for the number X <= 1000000000, the sum of the digits will not exceed 100, therefore we can write the following code:
   

    #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; }